Проверка хеш-таблиц

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

Для линейного зондирования я понимаю, как работает зондирование, и мой инструктор подразумевал, что он хочет, чтобы размер шага был равен 1. Дело в том, что дубликаты не допускаются. Так что я должен «искать» значение, прежде чем вставить его, верно? Но что, если таблица используется до такой степени, что все ячейки либо «заняты», либо «удалены»? Затем, чтобы найти конкретный ключ и убедиться, что его нет в таблице, мне придется выполнить поиск по всей таблице. Это означает, что операция поиска (и, соответственно, операция вставки) выполняется за O(n).

Это не кажется правильным, и я думаю, что я что-то неправильно понял.

Я знаю, что мне не придется сталкиваться с той же проблемой при квадратичном зондировании, поскольку таблица должна быть по крайней мере наполовину пустой, и она будет проверять только определенное количество элементов. И для двойного хэширования я не уверен, как это будет работать, потому что мне также нужно будет выполнить поиск в таблице, чтобы доказать, что ключ, который нужно вставить, отсутствует. Но откуда мне знать, как остановить поиск, если ни одна из ячеек «никогда не занята»?

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


hashmap algorithm hash-function hashcode hash-collision
person Desmond Lee    schedule 09.03.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

Между прочим, я был поражен, увидев, что первый анализ этой проблемы был фактически проведен математиком Рамануджаном в 1913 году, чьи результаты подразумевали, что «полное смещение элементов, т. е. стоимость построения, для линейной пробной хеш-таблицы, полной составляет около N ^ (3/2)». (см. здесь)

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

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

person Simon    schedule 09.03.2013