Как подсчитать столкновения клавиш при использовании boost :: unordered_map?

Question

У меня есть структура данных с 15 беззнаковыми значениями, я определил хеш-функцию с помощью hash_combine следующим образом:

 friend std::size_t hash_value(const TUPLE15& given)
    {
      std::size_t seed = 0;

      boost::hash_combine(seed, val1);
      boost::hash_combine(seed, val2);
      ...
      return seed;
    }

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

Answer 1

Как насчет сравнения количества кортежей с количеством уникальных хеш-значений?

set<size_t> hash_values;
BOOST_FOREACH(const TUPLE15& tuple, tuples)
    hash_values.insert(hash_value(tuple));
size_t collisions = tuple_map.size() - hash_values.size();

или

size_t collisions = 0;
for (size_t bucket = 0; bucket != tuples.bucket_count(); ++bucket)
    if (tuples.bucket_size(bucket) > 1)
        collisions += tuples.bucket_size(bucket) - 1;