Что быстрее найти элемент в хеш-таблице или в отсортированном списке?

Question

Что быстрее найти элемент в хеш-таблице или в отсортированном списке?

Answer 1

Сложность алгоритма хорошая вещь, которую нужно знать, и хеш-таблицы известны как O (1) в то время как отсортированный вектор (в вашем случае я думаю, что лучше использовать отсортированный массив, чем список) обеспечит O (log n) время доступа.

Но вы должны знать, что обозначение сложности дает вам время доступа для N, переходящего в бесконечность. Это означает, что если вы знаете, что ваши данные будут продолжать расти , то обозначение сложности даст вам подсказку по выбранному алгоритму.

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

Например, в другой проблеме: сортировка массива. Для несколько записей пузырьковая сортировка, в то время как O (N ^ 2) может быть быстрее, чем .. быстрая сортировка, в то время как это O (n log n) .

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

Редактировать: загляните в эту статью, чтобы понять значение обозначения Big O .

Answer 2

Предполагая, что под «отсортированным списком» вы подразумеваете «произвольно доступную, отсортированную коллекцию». Список обладает тем свойством, что вы можете проходить его только по элементам, что приведет к сложности O (N).

Самый быстрый способ найти элемент в отсортированной индексируемой коллекции - это N-арный поиск O (logN), в то время как хеш-таблица без коллизий имеет сложность поиска O (1).

Answer 3

Если алгоритм хеширования не является чрезвычайно медленным (и / или плохим), хеш-таблица будет быстрее.

ОБНОВЛЕНИЕ: Как отметили комментаторы, вы также можете получить снижение производительности из-за слишком большого количества коллизий не потому, что ваш алгоритм хеширования плох, а просто потому, что хеш-таблица недостаточно велика. Большинство реализаций библиотеки (по крайней мере на языках высокого уровня) автоматически увеличивают вашу хэш-таблицу за кулисами, что приведет к более медленной, чем ожидалось, производительности на вставке, которая вызывает рост, но если вы используете свою собственную, это определенно рассмотреть.

Answer 4

Операция get в SortedList равна O(log n), а та же операция в HashTable - O(1). Итак, обычно , HashTable будет намного быстрее. Но это зависит от ряда факторов:

• Размер списка
• Производительность алгоритма хеширования
• Количество коллизий / Качество алгоритма хеширования

Answer 5

Это полностью зависит от количества данных, которые вы сохранили.

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

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

Таким образом, в общем случае отсортированный список будет быстрее для небольших наборов данных. (Для очень маленьких наборов данных, которые часто изменяются и / или редко ищутся, отсортированный список un может быть даже быстрее, поскольку он позволяет избежать лишних затрат на выполнение сортировки.) Поскольку набор данных становится большим, увеличение времени поиска в списке затмевает фиксированные издержки хэширования, и хеш-таблица становится быстрее.

Где эта точка останова будет меняться в зависимости от вашей конкретной хеш-таблицы и реализаций поиска по отсортированному списку. Выполните тесты и сравните производительность на нескольких наборах данных типичного размера, чтобы увидеть, какие из них действительно будут эффективнее в вашем конкретном случае. (Или, если код уже работает «достаточно быстро», не надо. Просто используйте тот, который вам удобнее, и не беспокойтесь об оптимизации чего-то, что не нужно оптимизировать.)

Answer 6

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

Answer 7

HashTable будет более эффективным для списка, содержащего более 10 элементов. Если в списке менее 10 элементов, издержки из-за алгоритма хэширования будут больше.

В случае, если вам нужен быстрый словарь, но вам также нужно хранить элементы в упорядоченном порядке, используйте OrderedDictionary. (.Net 2.0 и выше)