为什么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

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

补充说明：我想为一个unordered_set的集合定义哈希值，其中一个集合的哈希值是其组成部分哈希值之和。但如果仅仅是标识，那就不够好了，因为{2,4}的哈希值与{1,5}的哈希值相同。避免这种情况最简单的方法可能是使用std :: hash双重函数。

- François

---

为什么你认为它不会是恒等函数？ - user253751

对于每个输入，f(x) = x 是完美独特的。 :) - erip

身份标识对于整数的简单哈希来说是显而易见的选择。（显然，这对于加密哈希来说是一个很差的选择——需要使用单向函数。） - Toby Speight

相关链接：https://dev59.com/smct5IYBdhLWcg3wsPd5/ 和 https://dev59.com/PG865IYBdhLWcg3wSMgw/ - dyp

我并不真正理解你的附言。无论如何，请勿事后更改问题。 - Lightness Races in Orbit

Answer 1

看起来它的身份是独特的，因此被允许。 来自 cpp reference。

实际哈希函数是与实现相关的，并且不需要满足除上述指定的任何其他质量标准。 值得注意的是，一些实现使用微不足道（identity）哈希函数，将整数映射到其本身。 换句话说，这些哈希函数旨在与无序关联容器一起使用，但不作为加密哈希函数。 ....

- nayana

Answer 2

似乎将哈希函数 int→int 定义成恒等函数是完全合理的，你为什么会感到惊讶呢？进行任何进一步的计算都是没有意义的。实际上，这是一个完美哈希，可以用所有方面的意义来描述。

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

只有当你想要哈希大于哈希本身类型的类型（比如 uint9999999_t）时，你需要对该值进行一些“压缩”工作以使其适应哈希大小。

- Lightness Races in Orbit

---

对于一个输入，其范围受int最小值和int最大值的限制，例如（-1000，+1000），分布将不是最优的。 - dyp

@dyp：如果你有这样的输入，为什么要将其存储为int呢？你可以随时使用适用于你的应用程序的自定义范围感知哈希函数，但我看不出默认实现在这方面做任何假设的理由。 - Lightness Races in Orbit

添加一个 INT_MAX 的单个条目，你就会遇到同样的问题，只不过你必须使用 int。对我来说，是否默认实现应该尝试补偿输入数据中的常见偏差是有争议的；因此，对我来说问题是，“为什么不尝试这样做的论据是什么？” - dyp

@dyp：我认为你无法提出任何“常见的偏差”。你在没有数据的情况下追求优化！如果默认实现针对情况_X_进行了优化，那么它对于情况_Y_突然变得次优。让默认执行明智、显而易见的事情，如果需要，再用自己特定的哈希函数替换它。 - Lightness Races in Orbit

进行任何进一步的计算都是毫无意义的。实际上，从各个方面来看，这是一个完美的哈希。但这完全忽略了其中的权衡，即在模表大小之后的身份哈希（这才是最重要的）在最坏情况下极易发生冲突（即使使用质数桶），而节省强哈希的CPU时间，将接近递增的值折叠到桶中，比强哈希更均匀地分布，并且（非常微小的好处）如果按照递增键的顺序进行查找，则具有更好的缓存局部性。 - Tony Delroy

Answer 3

其他答案已经很好地涵盖了身份函数背后的原理。针对您的补充说明：

我想将无序集合的哈希定义为其组件哈希的总和，但如果仅是身份函数，则并不完美，因为{2,4}的哈希与{1,5}的哈希相同。避免这种情况最简单的方法可能是使用std::hash函数。

正如您所看到的，使用+运算符来组合哈希值并不是一个好主意。为了更加健壮，您可以使用XOR（^）运算符，或者从采用boost::hash_combine的方法中获取灵感（在此SO帖子中详细说明）：

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

作为例子，对于你的两个整数对（1,5 / 2,4），以及种子值为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

- mindriot

---

为什么你不能只使用：seed ^= x？为什么你需要+ 0x9e3779b9 +（seed << 6）+（seed >> 2）？ - François

你可以选择简单的异或操作（就像我写的那样）；但是请查看上面我链接的SO文章，了解Boost方法背后的一些原理。 - mindriot

一个简单的实际例子：在这种情况下，将两个0的哈希组合起来将是0 ^ 0，这又是0。但你可以争论说两个0应该产生与单个0不同的哈希值。另一个理由是，连续的两个哈希值应该相距很远。 - mindriot

非常感谢，同时也很抱歉，我无法选择两个答案，我应该为补充问题提出另一个问题并选择您的答案。 - François

没关系，就这样吧。 - mindriot