Среднее количество прыжков на хэш-карте

Question

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

Под «прыжками» я подразумеваю:

Для обработки столкновений:Если два или более элемента hashCodes отображаются в один и тот же индекс в хэш-таблице, я создал «связанный список» по этому индексу.Таким образом, если в хэш-таблице есть 4 элемента, которые сопоставлены с индексом «i», то индекс «i» содержит связанный список из 4 элементов.«Прыжки» в этом смысле «ходят» или «прыгают» по этому связанному списку.

По сути, в каждом индексе карты есть другая структура данных.

Answer 1

Чтобы быть полностью явным, число «прыжков» по ​​списку в хеш-таблице, которая использует списки для обработки коллизий, идентично количеству хеш-коллизий в таблице, которое будет числом, которое hash(item) % size of table оценивает как то же значение для предоставленных данных. Для хеш-таблиц, которые используют запасные слоты в таблице, также вносят свой вклад сталкивающиеся элементы, которые были удалены из таблицы.

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

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

Answer 2

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

Answer 3

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

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

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

---

Если вы попытаетесь рассчитать / оценить / измерить количество «прыжков», вы столкнетесь с такими вещами, как начальный HashMap размер, порядок вставки ключа, эффект изменения размера и т. *

Answer 4

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

Answer 5

См. Документацию Java HashMap :

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

Другими словами, это зависит от качества хэш-функции, реализованной для элементов, которые вы в ней храните.