boost::hash_combine里的魔法

minmin

最近又和朋友讨论到C++里的 hash_combine , 我对它的疑问有两个：

为什么它至今都没被收录到C++标准库里?
boost::hash_combine 源代码里那些魔法数字是怎么回事?

这篇文章再来钻研一下.

为什么hash_combine不在标准库里?

我感觉要支持对任何class做hash, hash_combine 是必不可少的, 它可以让我们把基础类型的hash都合并起来, 比如一个class包含一个 string 和一个 int 成员, 这个class的hash就是他们俩成员hash的合并.

但是我们现在还是只能用 boost 而不是标准库 std 的 hash_combine , 再次挖了一下原因, 如下:

2012年和2014年分别有两个提案, 但2014年的提案被拒了因为他们觉得2012年的方案更好, 但是直到C++17依然没有发布任何相关的代码.

归结于原因就是C++委员会过于追求完美, 至今没有发布一个可用的解决方案.

参考: https://www. open-std.org/jtc1/sc22/ wg21/docs/papers/2017/p0814r0.pdf

boost::hash_combine里的魔法数字又是什么?

那么现在只能用 boost::hash_combine 了, 在没有 boost 的情况下只能照抄一份留在自己库里用, 看看 boost 的源代码:

参考: https://www. boost.org/doc/libs/1_64 _0/boost/functional/hash/hash.hpp

template <typename SizeT>
inline void hash_combine_impl(SizeT& seed, SizeT value)
    seed ^= hasher(value) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

按执行顺序我们一个一个看:

hasher(value) : 就是对我们需要的数的哈希的结果.

我们期望它是一个比较散比较随机的哈希数, 后续其它操作都是对可能不那么随机的哈系数的补充操作.

seed : 可以自选一个初始种子数, 或是前一个hash的结果.

0x9e3779b9 : 这个魔法数字后面细说.

(seed<<6) + (seed>>2) : 这个就是单纯的比特位的洗牌, 加上左挪6位和右挪2位的结果后, 能打散避免在比特位上聚集的数. 比如两个连续的数, 比特位上就差一位, 洗牌后会相差更多.

^= : XOR根据种子和哈希计算后的结果再次翻转他们俩的比特位, 再次打乱数字.

参考: https:// stackoverflow.com/quest ions/35985960/c-why-is-boosthash-combine-the-best-way-to-combine-hash-values

魔法数字: 0x9e3779b9

剩下这个魔法数字是什么, 有什么用呢?

首先它是一个32位随机比特组成的数字. 随机的意思是每一个比特位上出现0和1的概率都应该相等, 或者每个比特之间都没有相关性. 通常我们可以用一个无理数的二进制展开来获得这种数字.

我们用上这么一个随机数的原因是避免种子数比特位上刚好都是0, 这样不管怎么做 hash_combine 结果都是0.

在我们这个案例里, 就是用上了黄金比例这么个无理数:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

哈希里用到黄金比例这个数的最早来源是这里:

http:// burtleburtle.net/bob/ha sh/doobs.html

ub4 hash( k, length, initval)
register ub1 *k;        /* the key */
register ub4  length;   /* the length of the key */
register ub4  initval;  /* the previous hash, or an arbitrary value */
   register ub4 a,b,c,len;