Размер массива хеш-таблицы?

Question

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

Answer 1

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

Answer 2

Это зависит от вашей потребности в памяти / скорости. Для схем цепочки я рекомендую использовать размер хеш-таблицы как 1/2..1/4 от количества ключей. Это ~1-2 сравнения за поиск, если вы сохраняете каждый список ссылок отсортированным по ключам.

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

Таким образом, вам не нужно сравнивать указатель на "is linklist заканчивается", вам нужно просто сравнить ключи только так (списки отсортированы):

for(node *p = table[hash]; p->key < search_key; p = p->next);
return p->key == search_key? p : NULL;