Когда мне следует перефразировать всю хеш-таблицу?

Question

Как мне решить, когда мне следует перефразировать всю хеш-таблицу?

Answer 1

Это во многом зависит от того, как вы решаете столкновения. Если вы используете линейное зондирование, производительность обычно начинает довольно сильно падать с коэффициентом загрузки, намного превышающим 60% или около того. Если вы используете двойное хеширование, коэффициент загрузки в 80-85% обычно довольно разумный. Если вы используете цепочку столкновений, производительность обычно остается приемлемой с коэффициентами нагрузки примерно до 150% или более.

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

Answer 2

Как правило, у вас есть хеш-таблица, содержащая N элементов, распределенных в массиве из M слотов.

Существует процентное значение (называемое «growthFactor»), определенное пользователем при создании хеш-таблицы, которая используется следующим образом:

if (growthRatio < (N/M))
  Rehash();

Перефразирование означает, что размер массива из M слотов должен быть изменен, чтобы он содержал больше элементов (идеальное простое число, превышающее текущий размер (или в 2 раза больше)), и что ваши элементы должны быть распределены в новом большем массиве. *

Такое значение должно быть от 0,6 до 0,8.

Answer 3

Основное правило - изменять размер таблицы, как только она заполнится на 3/4.