C++ 正在使用 [](int i){return i;} 作为 unordered_set 散列函数的好习惯吗？

Question

#include <iostream>
#include <unordered_set>
using namespace std;

int main() 
{
    auto hash = [](int i) {return i; };
    unordered_set<int, decltype(hash)> s(4000, hash);
    for (int i = 0; i < 4000; i++)
        s.emplace(i * 4027);
    cout<<s.bucket_size(0)<<endl;//4000 here ,all the keys fell into the same bucket .
    return 0;
}

http://ideone.com/U1Vs1P

我发现ideone编译器使用素数4027(4000之后的第一个素数，4000是unordered_set的大小)作为除数来划分哈希值，并使用余数来确定 key 应该在哪个桶中落入，在本例中为 0。

我在 visual studio 2015 上运行了这段代码，只需将 4027 更改为 4096，它也将 4000 返回给我。似乎 vs 使用 4000 之后的 2 的第一个幂作为除数。

我的问题是，我有几个独特的整数(可能有数百个)，它们都在 [0,4000) 区间内。

我想将它们存储在哈希表中，以便我可以非常快速地插入和删除这些键。

而且我不想浪费内存，我不想只为几个整数保留一个 4000 长的 vector 。

我尝试了默认的 unordered_set ，但是它的哈希函数太慢了。

所以我想我可以使用 [](int i){return i;} 作为我的哈希函数。只要我知道我的 key 将以这种方式分发(我的 key 可能非常紧凑，比如 301,303,304,306,308 ) .

但这是好的做法吗？恐怕这会导致其他编译器出现冲突问题。

Answer 1

And I don't want to waste memory ,I don't want to keep a 4000 long vector for just a few ints .

这就是哈希表是。这是内存与性能的权衡。如果您想要一个可以为搜索、插入、和 移除提供 O(1) 性能的容器，那么代价就是高内存成本。

基于节点的set具有较低的内存开销，但是O(log(n)) 的搜索操作和大量的动态分配，但相对较快的插入和移除(忽略搜索时间)。基于数组的 flat_set(又名:排序的 vector)为您提供尽可能小的内存(以及非常快的开始到结束迭代)，但是 O(log(n )) 搜索和插入/删除操作对于大型集合来说可能非常慢。

说到这些，天下没有免费的午餐。

处理这种事情的唯一方法是确保桶的数量相对于元素的数量足够大。这将有助于最大程度地减少碰撞。

如果您知道哈希表的实现和您使用的哈希函数，您可以总是构造一系列代表最坏情况的数字。但是哈希表没有针对最坏情况进行优化；它们针对大​​多数元素不会发生冲突的一般情况进行了优化。

也就是说，您始终可以让哈希函数对数字执行一些任意数学运算。添加一个任意的固定常量，做一些位移，或者任何你觉得有用的东西。但同样，这不会阻止某人构建最坏的情况。因此，只有当您的实际代码 经常发生冲突并且如果不删除一些重要的东西就无法消除它们时，您才应该为这样的事情烦恼。