Реализация хеш-таблицы

Question

Меня недавно спросили «как бы вы реализовали hastable». Я знаю, что алгоритм хеширования важен, так как чем меньше коллизий, тем лучше производительность WRT, но какой алгоритм / структуру данных следует использовать для предоставления амортизированного постоянного времени {O (1)} для вставки / удаления / поиска?

Answer 1

Хеш-таблицы имеют две основные возможности:

1. Открытая адресация , которая представляет собой простой массив [динамический массив действительно, если вы может позволить вашему столу расти на лету. Как только конфликт встретился - вам нужно использовать вторую хеш-функцию, чтобы найти следующую запись, на которую будет отображен элемент. Обратите внимание, что у этого решения есть некоторые проблемы [которые могут быть решены], когда ваша хеш-таблица также позволяет удалять. [Специальная отметка для "удаленных" блюд]
2. Цепочка - в этом решении каждая запись в массиве представляет собой связанный список - содержит все элементы, хэшированные для этой записи. Здесь - все элементы, сопоставленные определенному значению, находятся в списке.

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

РЕДАКТИРОВАТЬ: анализ сложности:
Предположим, что коэффициент загрузки p для некоторых p < 1.

1. Вероятность "коллизии" в каждом доступе равна p Таким образом, среднее значение доступа к массиву равно: Sigma(i * p^(i-1) * (1-p)) for each i in [1,n] Это дает вам: Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST. [взгляните на правильность Sigma (i * p ^ (i-1)) <1 / (p-1) ^ 2 в вольфрам альфа </a>]. Таким образом, получается в среднем постоянное количество обращений к массиву. Также: вам может понадобиться перефразировать все элементы после достижения коэффициента загрузки, что приведет к O(n) доступам к массиву. В результате n * O(1) ops [добавление n элементов] и 1 * O(n) op [перефразировка], поэтому вы получите: (n * O(1) + 1 * O(n)) / n = O(1) время моторизации.
2. Очень похоже на (1), но анализ выполняется при доступе к списку. Каждой операции требуется ровно один доступ к массиву и число вариантов доступа к списку - с тем же анализом, что и раньше.