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

Question

Я пишу общую хэш-карту в C ++, которая использует цепочку для обработки коллизий.

Скажите, если у меня есть хэш-карта с 11 корзинами, и я вставляю 8 элементов. Хеш-функция распределяет его следующим образом:

bucket[0] = empty
bucket[1] = 2 elements
bucket[2] = empty
bucket[3] = 1 element
bucket[4] = 1 element
bucket[5] = 3 elements
bucket[6] = empty
bucket[7] = 1 element
bucket[8] = empty
bucket[9] = empty
bucket[10] = empty

Расчет разброса по ведрам составляет 5/8 = 0,625. Но как рассчитать спред с учетом глубины сегментов?

Я хочу знать это, потому что: Скажем, если я добавил 20 элементов, и у каждого сегмента 1 элемент, а у последнего сегмента 11 элементов.

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

Заранее спасибо!

Answer 1

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

Answer 2

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

Answer 3

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

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