Смотря что у атакующего. Если у него 6-6-5-4-4, то не выгодно перебрасывать 4-ку, потому что она уже даёт 1 ранение. Если перебросить, то шанс 1/6, что будет ещё +1 ранение, но шанс 2/3, что будет -1 ранение.
В общем случае 4-6 нет смысла перебрасывать, потому что шанс не менее 50%, что выпадет меньше.
дело в том, что если хэш влазит в регистр, то он полностью эквивалентен индексу.
И что вас смущает? В этом суть хеширования. Мы любые данные (например, ключ), которые "не влазят" в регистр, превращаем в хеш, который уже влазит, чтобы дальше операции сравнения сводились к сравнению хешей, а не исходных данных побайтово. (Конечно, я имею в виду кейс, когда хеширование используется для ускорения поиска, а не для других целей).
nrgian, И хеш мы не считаем, а считываем, то есть учитываем обращение к памяти. Хотя тут вы правы, нужно же ещё посчитать хеш. Я имел в виду, что считываем мы ключ.
Ладно, у нас есть ключ, мы к нему обратились, то есть закешировали, доступ к нему относительно быстрый. Поэтому, далеко не бегая, вычисляем всё на месте - пробегаемся по ключу и считаем хеш. Не забываем, что у нас есть команды процессора (например, старый набор SSE4), и где-то по цене за 0.2 такта на байт мы пробегаемся по небольшому ключу-строке. И нам даже не обязательно все байты проверять, можно ограничиться первыми 50ю байтами к примеру. Вы же помните, что хеш не обязан быть уникальным. В общем, можем добавить еще одно "чтение" к общим затратам. Итого соотношение времени 3 к 5.
Многовато?
А что там с коллизиями на такой длине?
С коллизиями там всё очень хорошо. Шанс коллизии 1/2^64. Именно поэтому, если у нас около 100 ключей для поиска, то имеет смысл размер хеш-таблицы сделать 128 или 256, а индекс у нас - первые (или последние) 8 бит хеша, которые дадут шанс коллизии 1/256, но с учетом размера массива это норм.
nrgian, это вы интересно считаете. А ничего, что ваше "сложение и умножение" может выполняться за пол такта, а чтение - за 150 тактов? С учётом всех L-кешей, конечно. И вообще, все три операции умещаются в одну команду процессора. Точнее, что с чем складываем и умножаем раскидывается по другим регистрам сначала, а вот откуда мы берем смещения - это внезапно ещё больше чтения. То есть нужно прочитать дополнительно: а) переменную с индексом (смещение) б) переменную с указателем на массив (базу). Итого - три чтения, которыми я и предлагаю ограничиться для примерной оценки действия на x86 процессорах, но уже более близкой к правде.
А что хеш-таблица? Также а) считываем сам хеш б) считываем адрес массива. Небольшое вычисление - берем первые N бит хеша и превращаем в число, я даже это считать не буду за операцию. Дальше по сути операция чтения по индексу, т.к. у нас есть смещение. Правда, попадаем мы не на само значение, а на массив коллизий, где нам нужно простым перебором найти нужный элемент. Но массив этот, как правило, состоит из 1-2 элементов. И даже если чуть больше, то он уже у нас весь закеширован в L-кешах, что делает доступ на порядок быстрее. Так что в общем случае это по сути та же операция чтения. Хорошо, если вам угодно, то будем считать это две операции чтения, предположив, что там ещё 10 чтений из кеша.
Итого 3 чтения против 4 чтений. Большая разница?
Это я ещё не учитываю, что в качестве искомых "значений" снова оказываются указатели (на объекты DOM). И другие накладные расходы, которые одинаковы для обоих случаев, на фоне которых способ доступа уже почти не играет роли.
Даже если скорость по хешу в 2-3 раза дольше, по условиям вопроса у нас 4 взятия по индексу. Кстати, плюс ещё 4 поиска по тому же хешу, ведь children - свойство объекта, не забываем про него. Так что если бы querySelector искал класс по хешу из единой хеш-таблицы документа, это наверняка было бы быстрее.
Muranx, не нужно агриться. Если не нравится комментарий, просто проигнорируйте.
К слову, если люди захотят, они тут будут болтать без вашего участия даже. Если это хоть краем будет касаться темы вопроса, то ваши возмущения по форме и содержанию не возымеют никакого эффекта.
RAX7, я делал одиночные запуски: 9 из 10 в пользу query. Запускал тест через setTimeout после формирования DOM, менял тесты местами - результат тот же. Что ещё может искажать одиночные результаты?
Антон Спирин, интересно. То есть движок хеширует класс элемента на этапе добавления в DOM?
Если так, то O(1) быстрее, чем O(3). Ну, точнее так нельзя формулировать, но суть понятна, надеюсь.
В общем случае 4-6 нет смысла перебрасывать, потому что шанс не менее 50%, что выпадет меньше.
1-2 стоит перебрасывать всегда.
А вот 3-ка проблемная.