Имеет ли смысл изменить размер хеш-таблицы? И когда?

Question

В реализации My Hash Table есть функция изменения размера таблицы, когда нагрузка достигает около 70%. My Hash Table реализован с отдельной цепочкой для коллизий.

Имеет ли смысл, что я должен изменить размер хеш-таблицы в любой момент или я должен просто оставить ее как есть? В противном случае, если я увеличу размер (почти вдвое, фактически я следую этому: http://planetmath.org/encyclopedia/GoodHashTablePrimes.html), когда нагрузка составляет 70%, я должен изменить его размер, когда нагрузка становится 30% или ниже?

Answer 1

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

Почему это относится к вопросу?Потому что, когда вы уменьшаете хеш-таблицу степени двух, вы можете оставить все записи в нижней половине, где они есть, и просто добавить связанный список в слоте i (из верхней половины) в связанный список в слоте i - n/2.

Answer 2

Если память дешевая, оставьте ее в покое. Если память дорогая, измените размер при истерии, как вы предложили. Когда закончите, профилируйте результат, чтобы убедиться, что он работает хорошо и не сделал ничего глупого.

Answer 3

Пишете ли вы хеш-таблицу для общего пользования или для этого есть какая-то конкретная цель? Я предлагаю не изменять размер меньше для общей реализации. Это сделает вашу таблицу простой и не позволит памяти трепетать в условиях, когда таблица часто заполняется и очищается. Если вы столкнетесь с условием, что размер хеш-таблицы должен быть уменьшен, увеличьте его в этот момент времени.