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

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

Под «хмелем» я имею в виду:

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

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


java hashmap formula algorithm
person Chris Dargis    schedule 10.02.2012    source источник
comment
Вы реализовали хэш-карту или использовали ее?   -  person The Nail    schedule 11.02.2012
comment
Реализована пользовательская версия класса хэш-карты Java.   -  person Chris Dargis    schedule 11.02.2012
comment
Интересно, а что ты переделал?   -  person The Nail    schedule 11.02.2012
comment
асимптотически это порядок log(n).   -  person ElKamina    schedule 11.02.2012
comment
Не могли бы вы определить, что вы подразумеваете под прыжком? Hops имеет смысл для дерева или варианта списка пропуска, а не для хеш-таблицы. Коллизии в хеш-таблице больше зависят от хеш-функции, а не от реализации таблицы (если таблица все равно сделана правильно).   -  person Affe    schedule 11.02.2012
comment
@Affe: Конечно, извини.   -  person Chris Dargis    schedule 11.02.2012
comment
Что ж, если вы придумаете способ аналитически оценивать коллизии в произвольной хэш-функции, вы, вероятно, можете выбрать советников PhD :) Но это, вероятно, задача для эмпирической проверки.   -  person Affe    schedule 11.02.2012

Ответы (5)


arrow_upward
1
arrow_downward

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

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

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

person Pete Kirkham    schedule 11.02.2012

arrow_upward
1
arrow_downward

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

person Doug Currie    schedule 10.02.2012
comment
Так же зависит от макс. коэффициент загрузки хеш-таблицы. - person Fred Foo; 11.02.2012
comment
Да, это так. Я ищу способ рассчитать среднее количество прыжков при поиске элемента. - person Chris Dargis; 11.02.2012

arrow_upward
1
arrow_downward

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

person perreal    schedule 11.02.2012

arrow_upward
1
arrow_downward

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

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

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

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

person Stephen C    schedule 11.02.2012

arrow_upward
0
arrow_downward

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

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

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

person The Nail    schedule 10.02.2012
comment
Я вычисляю свой собственный хэш-код и пытаюсь измерить его качество. - person Chris Dargis; 11.02.2012