为什么 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" 编译，然后结果是：

为什么会这样？我不使用任何库，也没有专门的哈希函数。

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

Answer 1

这似乎是它的身份，它被允许作为它独特的.. 来自 cpp reference

The actual hash functions are implementation-dependent and are not required to fulfill any other quality criteria except those specified above. Notably, some implementations use trivial (identity) hash functions which map an integer to itself. In other words, these hash functions are designed to work with unordered associative containers, but not as cryptographic hashes, for example. ....

Answer 2

散列函数int→int恒等似乎是完全合理的，不清楚你为什么对此感到惊讶。执行任何进一步的计算将毫无意义。事实上，从任何意义上来说，这都是一个完美哈希。

记住，std::hash 应该（几乎唯一地）识别值，而不是加密它们。

只有当您想要散列大于散列本身的类型（例如，uint9999999_t）时，您才需要做一些工作以将值 "compress" 转换为散列的大小.

Answer 3

其他答案很好地涵盖了恒等函数背后的基本原理。处理您的附录：

I wanted to define the hash of an unordered_set as the sum of its components hashs, but if it's just identity it's not cool because the hash of {2,4} is the same than the hash of {1,5}. The simplest way to avoid that is may be to use the std::hash function.

如您所见，使用 + 运算符组合哈希并不是最好的主意。为了更健壮，您可以使用 XOR (^) 运算符，或从所采取的方法中汲取灵感，例如 boost::hash_combine (details in this SO post):

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

例如，对于您的两个整数对 (1,5 / 2,4) 和一个 seed 0，这可以得出

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

为什么 std::hash<int> 好像是恒等函数

Why std::hash<int> seems to be identity function

c++

debugging

identity

c++11

stdhash