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

Question

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

Answer 1

Сложность алгоритма - это хорошая вещь, которую нужно знать, а хэш-таблицы, как известно, O(1) в то время как отсортированный вектор (в вашем случае, я думаю, лучше использовать отсортированный массив, чем список) предоставит O (логарифм 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) в то время как та же операция с хэш-таблицей является O(1).Итак, обычно, тот HashTable было бы намного быстрее.Но это зависит от ряда факторов:

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

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