становится слишком много столкновений с hash_combine

Question

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

std::size_t seed = 0; 

for (int i = 0; i < myvec.size(); ++i) 
    boost::hash_combine(seed, myvec[i]); 

return seed; 

Когда myvec имеет размера 3 и я заполняю хэш с 1M элементами 1: 100 x 1: 100 x 1: 100 (поэтому каждый элемент myvec является целым числом от 1 до 100). Я получаю около 330 000 столкновений.

Нормально ли это иметь много столкновений и что я могу сделать, чтобы этого избежать?

Answer 1

Вы правы. Функция Boost's hash_combine не подходит для этого набора данных. Вы можете проверить с помощью this code, который показывает почти 600 000 столкновений за миллион тестовых записей.

Вот простое исправление:

for (int i = 0; i < myvec.size(); ++i) 
    boost::hash_combine(seed, myvec[i] * 2654435761); 

Магическое число является простым близко к 2^32 * (SQRT (5) -1)/2 - см Knuth для объяснения того, почему это работает в развернуть интервалы.