Как хеширование имеет o (1) время поиска?

Ответ 1

Ну, это немного ложь - это может занять больше времени, но обычно этого не происходит.

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

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

Поиск данных одинаковый. Если мы хотим найти значение x, нам нужно только выяснить h (x), в котором указывается, где x находится в хеш-таблице. Таким образом, мы можем искать любое значение хэша в O (1).

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

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

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

Ответ 2

Поиск занимает O (1) раз, если в хэш-таблице нет конфликтов, поэтому неверно sya, что поиск в хэш-таблице принимает O (1) или постоянное время.

Посмотрите, как работает Hashtable в MSDN?

ИЗМЕНИТЬ

mgiuca объясняет это красиво, и я просто добавляю еще одну технику избегания коллоидов, которая называется Chaining.

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