хэш-таблица против линейного списка

Question

Будет ли случай, когда поиск по ключевому слову в линейном списке будет быстрее, чем в хеш-таблице?

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

Спасибо!

Answer 1

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

Вот пример реального случая, когда все ключи оказались в одной корзине: Ошибка Java 4669519 .

Answer 2

Да, в случаях очень небольшого количества элементов.Подумайте, как работает хеш.Он должен вычислить хеш, чтобы найти сегмент, а затем выполнить поиск по списку в этом сегменте.Кроме того, это может быть сложный многоуровневый хэш и т. Д. Таким образом, вы безубыточны вокруг точки, где поиск по линейному списку является более трудоемким, чем алгоритм поиска хеша.для всегда в начале или в начале списка.В зависимости от того, что вы делаете, это может произойти.

Есть и другие, но это должно помочь вам думать об этом.

Тем не менее, не запутайтесь.Обычно хеш - то, что вы хотите.