Хэш-таблица: Должен ли я увеличить количество элементов при столкновениях?

Question

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

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

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

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

Answer 1

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

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

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