Хеш-таблицы могут действительно быть O (1)?
Это, кажется, общеизвестно, что хеш-таблицы могут достигнуть O (1), но это никогда не имело смысла мне. Кто-то может объяснить это? Вот две ситуации, которые приходят на ум:
A. Значение является интервалом, меньшим, чем размер хеш-таблицы. Поэтому значение является своим собственным хешем, таким образом, нет никакой хеш-таблицы. Но если бы было, то это было бы O (1) и все еще было бы неэффективно.
B. Необходимо вычислить хеш значения. В этой ситуации порядок является O (n) для размера искавших данных. Поиск мог бы быть O (1) после того, как Вы делаете O (n) работа, но это все еще выходит к O (n) в моих глазах.
И если у Вас нет идеального хеша или большой хеш-таблицы, существует, вероятно, несколько объектов на блок. Так, это опускается до маленького линейного поиска в какой-то момент так или иначе.
Я думаю, что хеш-таблицы являются потрясающими, но я не получаю O (1) обозначение, если это, как просто не предполагается, теоретически.
Статья Википедии для хеш-таблиц последовательно ссылки постоянное время поиска и полностью игнорирует стоимость хеш-функции. Это - действительно справедливая мера?
Править: Для суммирования то, что я изучил:
Это технически верно, потому что хеш-функция не требуется, чтобы использовать всю информацию в ключе и так могла быть постоянным временем, и потому что достаточно большая таблица может понизить коллизии до почти постоянного времени.
Это верно на практике, потому что со временем это просто удается, пока хеш-функция и размер таблицы выбраны для уменьшения коллизий, даже при том, что это часто означает не использовать постоянную хеш-функцию времени.
3 ответа
Здесь есть две переменные, m и n, где m - длина входных данных, а n - количество элементов в хэше.
Заявление о производительности поиска O (1) делает по крайней мере два предположения:
- Ваши объекты могут сравниваться на равенство за время O (1).
- Будет несколько конфликтов хеширования.
Если ваши объекты имеют переменный размер и проверка равенства требует просмотра всех битов, производительность станет O (m). Однако хеш-функция не обязательно должна быть O (m) - она может быть O (1). В отличие от криптографического хеша, хеш-функция для использования в словаре не должна просматривать каждый бит во входных данных, чтобы вычислить хеш. Реализации могут смотреть только на фиксированное количество бит.
Для достаточно большого количества элементов количество элементов станет больше, чем количество возможных хэшей, и тогда вы получите коллизии, вызывающие повышение производительности выше O (1), например O (n) для простого обхода связанного списка (или O (n * m), если оба предположения неверны).
На практике, хотя утверждение O (1), хотя технически неверно, приблизительно верно для многих ситуаций реального мира, и, в частности, тех ситуаций, в которых выполняются вышеприведенные предположения.
Вы должны вычислить хэш, так что порядок O (n) для размера просматриваемых данных. Поиск может быть O (1) после того, как вы выполните O (n) работу, но в моих глазах это все равно выходит O (n).
Что? Для хеширования одного элемента требуется постоянное время. Почему это должно быть что-то еще? Если вы вставляете n элементов, тогда да, вам нужно вычислить n хэшей, а это занимает линейное время ... чтобы найти элемент, вы вычисляете один хеш то, что вы ищете, а затем найдите подходящее ведро с этим. Вы не пересчитываете хеши всего, что уже находится в хеш-таблице.
И если у вас нет идеального хеша или большой хеш-таблицы, вероятно, есть несколько элементов в ведре, поэтому в какой-то момент он все равно превращается в небольшой линейный поиск.
Не обязательно. Сегменты не обязательно должны быть списками или массивами, они могут быть любого типа контейнера, например сбалансированного BST. Это означает O (log n) худший случай. Но именно поэтому важно выбрать хорошую функцию хеширования, чтобы не помещать слишком много элементов в одну корзину. Как указал Кенни TM, в среднем вы все равно получите O (1) времени, даже если время от времени вам придется копаться в ведре.
Компромисс хеш-таблиц, конечно же, связан с пространственной сложностью. Вы обмениваете пространство на время, что, кажется, является обычным случаем в вычислительной науке.
Вы упомянули об использовании строк в качестве ключей в одном из своих комментариев.Вас беспокоит количество времени, необходимое для вычисления хэша строки, потому что она состоит из нескольких символов? Как еще раз заметил кто-то другой, вам не обязательно смотреть на все символы для вычисления хэша, хотя, если бы вы это сделали, это могло бы дать лучший хеш. В этом случае, если в вашем ключе в среднем m символов, и вы использовали их все для вычисления своего хэша, то, я полагаю, вы правы, этот поиск займет O (m ) . Если m >> n , то у вас может быть проблема. В этом случае вам, вероятно, будет лучше с BST. Или выберите более дешевую функцию хеширования.
Хэш фиксированного размера - поиск подходящего хеш-сегмента требует фиксированной стоимости. Это означает, что это O (1).
Вычисление хеш-функции не должно быть особенно затратной операцией - здесь мы не говорим о криптографических хеш-функциях. Но это кстати. Само вычисление хеш-функции не зависит от количества n элементов; хотя это может зависеть от размера данных в элементе, это не то, что относится к n . Таким образом, вычисление хеша не зависит от n и также равно O (1).