Пробные хеш-таблицы

Question

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

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

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

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

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

Answer 1

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

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

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

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