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

Ответ 1

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

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

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

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

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

Изменить: взгляните на эту статью, чтобы понять значение нотации Big O.

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

Размер списка
Выполнение алгоритма хеширования
Число коллизий/качество алгоритма хеширования

Ответ 5

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

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

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

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

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

Ответ 6

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

Ответ 7

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

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