unordered_map，为什么有的桶不止1个元素，哈希值也不一样？

Question

我正在使用 std::unordered_map 的默认哈希函数并检查是否发生了冲突。下面是代码：

void check(std::map<long, bool> & mp, const string & s, const long v){
    if(mp.count(v) == 0){
        mp[v] = true;
    }else{
        cout<<"collision for "<<s<<endl;
    }
}
int main(){
    std::unordered_map<std::string, long> um;
    std::map<long, bool> map;
    auto hasher = um.hash_function();

    std::string str = "";

long count = 0;

    for (int i = 0; i < 26; ++i)
    {
        str = char(65+i);
        um[str];
        auto value = hasher(str);
        check(map, str, value);

        for (int j = 0; j < 26; ++j)
        {
            str = char(65+i);
            str += char(65+j);
            um[str];
            auto value = hasher(str);
            check(map, str, value);

            for (int k = 0; k < 26; ++k)
            {
                str = char(65+i);
                str += char(65+j);
                str += char(65+k);
                um[str];
                auto value = hasher(str);
                check(map, str, value);

                for (int l = 0; l < 26; ++l)
                {
                    str = char(65+i);
                    str += char(65+j);
                    str += char(65+k);
                    str += char(65+l);
                    um[str];
                    auto value = hasher(str);
                    check(map, str, value);

                    for (int m = 0; m < 26; ++m)
                    {
                        str = char(65+i);
                        str += char(65+j);
                        str += char(65+k);
                        str += char(65+l);
                        str += char(65+m);
                        um[str];
                        auto value = hasher(str);
                        check(map, str, value);
                    }
                }
            }
        }
    }
        for(int i = 0; i < um.bucket_count(); ++i){
        if(um.bucket_size(i) >= 2)cout<<"um_collison happened at "<<i<<"  "<<um.bucket_size(i)<<endl;
    }

    return 0;
}

我遇到的问题是，我发现 collision for 没有输出，但是有很多像 um_collison happened at 17961055 3 这样的输出，我正在使用 g++ 4.9.2，为什么字符串被散列为不同的值，但一些桶仍然有超过 1 个元素？

Answer 1

哈希函数返回的值是一个size_t。假定哈希函数在给定随机输入时至少给出弱伪随机（即 "pairwise independent" 或类似）输出。但是，散列函数的输出并不直接用作给定输入的 bin 编号。这将需要 std::unordered_map 在 64 位机器上有 2^64 个 bins...这太多内存了。

取而代之的是，根据当前的元素数量，有一定数量的箱子，比如 B。映射通常采用散列器的输出，对 B 取模，以将项目映射到箱子。因此，具有不同哈希值的项目可以进入同一个容器。一旦散列 table 变得太紧，根据一些启发式算法，通常 B 会增加并且项目将重新散列以减少冲突次数。也就是说，我们重新计算所有哈希值，然后取模 B' 而不是更大的 B'。但它究竟如何工作是一个实现细节。

unordered_map，为什么有的桶不止1个元素，哈希值也不一样？

unordered_map, why some buckets have more than 1 element even hashed values are all different?

c++

hash

unordered-map

c++11