为什么std :: hash <int>似乎是身份函数

Question

#include <iostream>

int main() {
    std::hash<int> hash_f;
    std::cout << hash_f(0) << std::endl;
    std::cout << hash_f(1) << std::endl;
    std::cout << hash_f(2) << std::endl;
    std::cout << hash_f(3) << std::endl;
}

我用"g ++ main.cpp -std = c ++ 11"编译,结果是:

0
1
2
3

为什么会这样？我不使用任何库,我没有专门的散列函数.

附录:我想为int的unordered_set的unordered_set定义散列,其中集合的散列是其组件散列的总和,但如果它只是标识它并不酷,因为{2,4}的散列是相同的{1,5}的哈希值.避免这种情况的最简单方法可能是使用std :: hash double函数.

Answer 1

它似乎是它的身份,它允许作为其独特的..来自cpp参考

实际的散列函数是依赖于实现的,除了上面指定的那些之外,不需要满足任何其他质量标准.值得注意的是,一些实现使用简单(标识)散列函数将整数映射到自身.换句话说,这些散列函数被设计为与无序关联容器一起使用,但不是作为加密散列.....

Answer 2

哈希函数int→ int标识似乎是完全合理的,并且不清楚为什么你会对此感到惊讶.执行任何进一步的计算将毫无意义.事实上,这是该术语的每个意义上的完美哈希.

std::hash应该记住,应该(几乎唯一)识别值,而不是加密它们.

只有当你想要散列大于散列本身的类型(比方说uint9999999_t)时,才需要做一些工作来将值"压缩"到散列的大小.

Answer 3

其他答案很好地涵盖了身份函数背后的基本原理。要解决您的附录：

我想将 unordered_set 的散列定义为其组件散列的总和，但如果它只是身份，那并不酷，因为 {2,4} 的散列与 {1,5} 的散列相同。避免这种情况的最简单方法可能是使用 std::hash 函数。

如您所见，使用+运算符组合散列并不是最好的主意。为了更加健壮，您可以使用 XOR ( ^) 运算符，或者从所采用的方法中获取灵感，例如通过boost::hash_combine（此 SO 帖子中的详细信息）：

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

例如，对于您的两个整数对 (1,5 / 2,4) 和一个seed0，这可以解决

uint32_t seed = 0;
seed ^= 1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= 5 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 3449077526

uint32_t seed = 0;
seed ^= 2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= 4 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 3449077584