Реализация динамической хеш-таблицы с использованием цепного хеширования
Я пытаюсь реализовать динамическую хэш-таблицу с использованием цепного хеширования (каждый элемент в массиве является связанным списком).
Я хочу знать, в отношении сложности, какая из следующих возможностей лучше:
1. Я должен удвоить размер массива, когда массив заполнен, то есть каждый связанный список имеет хотя бы один элемент.
2. Я должен удвоить размер массива, когда у меня всего N элементов (во всех связанных списках) — где N — размер массива.
Решение
Много диких реализаций хеш-таблиц, включая несколько в стандарте C ++ (unordered_set, unordered_map).
Чтобы ответить на ваш вопрос, лучше удвоить количество бинов (внутренний массив), когда количество элементов достигнет N. И наоборот, будет сложнее и займет больше времени (выяснить, заполнены ли все бины).
Вам нужно сохранить член, который содержит количество элементов.
Вам не нужно беспокоиться о пользователях, использующих плохую хеш-функцию, например { return 0;},
Другие решения
По сложности они все одинаковые. Сложность хеш-таблицы дается в виде среднего амортизированного O (1), потому что коллизии хешей, когда у вас есть хорошие хеш-функции, сводятся к удаче. И наихудшая сложность любой хеш-таблицы — это O (N), что бы вы ни делали.
Тем не менее, полезные реализации изменяют размер в зависимости от коэффициента загрузки, который представляет собой соотношение между общим количеством элементов и количеством сегментов («размер массива»). Ожидание, пока в каждом сегменте будет хотя бы одна запись, слишком часто будет вызывать неоптимальное поведение. Но коэффициент загрузки 1 (N элементов в N сегментах), вероятно, слишком высок; в большинстве реализаций, которые я видел, по умолчанию где-то около 0,7 (7 элементов на 10 сегментов), и, как правило, пользователь может настраивать коэффициент загрузки (см. C ++ и Java оба). Это торговля памятью против скорости, а хеш-таблицы часто основаны на скорости. В общем, только профилирование покажет правильное значение для любой данной программы.
Кроме того, размер не должен удваиваться. типичный vector реализации увеличивают свой размер на 50% или 70% при каждом изменении размера, потому что широкомасштабное тестирование на реальных приложениях показало, что это лучший компромисс между скоростью и памятью, чем удвоение. Само собой разумеется, что аналогичная вещь будет применяться к хеш-таблицам, хотя опять же это подлежит профилированию.