Что быстрее, поиск по хэшу или бинарный поиск?

Question

Когда задан статический набор объектов (статический в том смысле, что однажды его загрузили, он редко, если вообще меняется), в который требуется повторный параллельный поиск с оптимальной производительностью, что лучше, HashMap или массив с двоичным поиском используя какой-то пользовательский компаратор?

Является ли ответ функцией типа объекта или структуры? Хэш и / или Равная производительность функции? Уникальность хеша? Размер списка? Hashset размер / установленный размер?

Размер набора, на который я смотрю, может быть от 500 до 10 метров, если эта информация полезна.

Пока я ищу ответ C #, я думаю, что истинный математический ответ не в языке, поэтому я не включаю этот тег. Однако, если есть какие-то специфичные для C # вещи, о которых нужно знать, эта информация желательна.

Answer 1

Я бы сказал, что это зависит главным образом от производительности методов хеширования и сравнения. Например, при использовании строковых ключей, которые очень длинные, но случайные, сравнение всегда даст очень быстрый результат, но хеш-функция по умолчанию обработает всю строку.

Но в большинстве случаев хэш-карта должна быть быстрее.

Answer 2

Здесь описывается, как создаются хэши и потому что юниверс ключей достаточно большой, а хэш-функции построены так, чтобы быть «очень инъективными», так что коллизии редко случаются O (1) на самом деле ... это что-то, основанное на некоторых вероятностях. Но разумно сказать, что время доступа к хешу почти всегда меньше времени O (log_2 (n))

Answer 3

Это зависит от того, как вы обрабатываете дубликаты для хеш-таблиц (если вообще). Если вы хотите разрешить дублирование хеш-ключа (без хеш-функции идеально), для поиска первичного ключа остается O (1), но поиск «правильного» значения может быть дорогостоящим. Ответ, теоретически, в большинстве случаев, хэши быстрее. YMMV в зависимости от того, какие данные вы положили туда ...

Answer 4

Это больше комментарий к ответу Билла, потому что в его ответе так много откликов, хотя он и неправильный. Поэтому я должен был опубликовать это.

Я вижу много дискуссий о том, какова сложность поиска в хеш-таблице наихудшего случая и что считается амортизированным анализом / что нет. Пожалуйста, проверьте ссылку ниже

Сложность выполнения хеш-таблицы (вставка, поиск и удаление)

сложность наихудшего случая - O (n), а не O (1), в отличие от того, что говорит Билл. И, следовательно, его сложность O (1) не амортизируется, так как этот анализ может использоваться только для наихудших случаев (так говорит и его собственная ссылка в Википедии)

https://en.wikipedia.org/wiki/Hash_table

https://en.wikipedia.org/wiki/Amortized_analysis

Answer 5

Ответ зависит. Давайте подумаем, что количество элементов n очень велико. Если вы хороши в написании лучшей хеш-функции, которая уменьшает коллизии, тогда хеширование является лучшим. Обратите внимание, что Хеш-функция выполняется только один раз при поиске и направляется в соответствующий сегмент. Так что это не большие накладные расходы, если n высокий.
Проблема в Hashtable: Но проблема в хеш-таблицах заключается в том, что если хеш-функция не годится (происходит больше коллизий), то поиск не является O (1). Он стремится к O (n), потому что поиск в сегменте - это линейный поиск. Может быть хуже, чем двоичное дерево. проблема в двоичном дереве: В двоичном дереве, если дерево не сбалансировано, оно также стремится к O (n). Например, если вы вставили 1,2,3,4,5 в двоичное дерево, это был бы скорее список. Итак, Если вы видите хорошую методологию хеширования, используйте хеш-таблицу Если нет, то лучше использовать двоичное дерево.

Answer 6

Конечно, хеш самый быстрый для такого большого набора данных.

Один из способов ускорить его, поскольку данные редко изменяются, - это программно сгенерировать специальный код для выполнения первого уровня поиска в виде гигантского оператора switch (если ваш компилятор может с ним справиться), а затем переход выкл, чтобы найти полученное ведро.