Хэш-таблица всегда O (n) время поиска?

Question

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

Почему люди говорят, что это O (1) поиск в среднем, и только O (n) для наихудшего случая?

Answer 1

Цель использования хеша состоит в том, чтобы иметь возможность индексировать в таблицу непосредственно, точно так же, как массив. В идеальном случае есть только один предмет на ведро, и мы легко достигаем O (1).

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

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

Answer 2

В lamens условиях с некоторой стороны машет:

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

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

В худшем случае у вас есть одно ведро и n предметов в одном ковше. В этом случае это в основном похоже на поиск списка, линейно. И поэтому, если значение окажется последним, вам нужно выполнить n сравнений, чтобы найти его. Или, по порядку n: O (n).

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

Answer 3

Говоря

Скажем, у нас есть 100 ведер и 1000000 элементов.

вы в основном лишая Hashmap от его реальной власти перепевов, а также не принимая во внимание начальную емкость HashMap в соответствии с необходимостью. Hashmap более эффективен в тех случаях, когда каждая запись получает свое собственное ведро. Малый процент столкновения может быть достигнут за счет большей емкости хэшмапа. Каждое столкновение означает, что вам нужно пройти соответствующий список.

Answer 4

Ниже приведены точки, которые следует учитывать при имплантации Хэш-таблицы.

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

2. Хорошая функция хэширования гарантирует, что записи хорошо распределены в ведрах хеш-таблицы. Это приведет к тому, что список будет коротким.

Выше позаботится о том, чтобы время доступа оставалось постоянным.