如何计算无序集c ++中的冲突

Question

我想计算一些有关我的哈希函数的统计信息（例如最大/平均碰撞量）。我编写了虚拟哈希函数（将所有键映射到1），并等待看到最大/平均碰撞次数等于键的数量。但是对于不同的功能，我有相同的数字。有人可以解释吗？代码：

#include <iostream>
#include <unordered_set>

struct DummyHash
{
    size_t operator()(int key) const
    {
        return static_cast<size_t>(1);
    }
};

int main()
{
    std::unordered_set<int, DummyHash> a;
    std::unordered_set<int> b;
    int c = 10000;

    for (int i = 0; i < c; i++)
    {
        a.insert(i);
    }
    std::cout << "a ended" << std::endl;

    for (int i = 0; i < c; i++)
    {
        b.insert(i);
    }

    std::cout << "b ended" << std::endl;

    std::cout << "a = " << a.max_load_factor() << ' ' << a.load_factor() << ' '
        << a.max_size() << ' ' << a.max_bucket_count() << ' ' << a.bucket_count() << '\n';
    std::cout << "b = " << b.max_load_factor() << ' ' << b.load_factor() << ' '
        << b.max_size() << ' ' << b.max_bucket_count() << ' ' << b.bucket_count() << '\n';
    return 0;
}

结果：

a ended
b ended
a = 1 0.659065 768614336404564650 768614336404564650 15173
b = 1 0.659065 1152921504606846975 1152921504606846975 15173

Answer 1

一种计算发生冲突的存储桶总数（具有多个元素的存储桶）的一种方法：

template<class... Args>
size_t collision_count(std::unordered_set<Args...> const& c) {
    size_t collisions = 0;
    for(auto bucket = c.bucket_count(); bucket--;)
        collisions += c.bucket_size(bucket) > 1;
    return collisions;
}