我之前对 HashMap 有很多错误的理解，特别是在 hash 函数对性能的影响上。最近我对 HashMap 的了解稍稍深入了一些，所以写了这篇笔记，对之前的错误理解修正总结。

“透明”的 hash 函数

首先从 hash 函数说起。 在我之前的理解中，hash 的用处就是：

• 能根据一个任何（支持被 hash）类型的值计算出一个无符号整数
• 对于两个相同的值，hash 出的值必须相等
• 对于两个不同的值，hash 出的值必须有极大概率（接近 100%）不同，也就是碰撞概率要低

确实，上面这三点是任何一个 hash 函数都需要具备的。按照这种理解，可以发现一个有趣的事情：

如果一个 HashMap 的键刚好是一个 64 位无符号整数，或者是 能 cast 为 64 位无符号整数的类型，那它岂不是不需要进行 hash 操作就可以满足上面的三点？

大量的数据都符合这一条件，例如 UID（从 0 起不断增大的无符号整数）和时间戳。

大概很多人都有过这种想法，举个例子：NoHashHasher。我之前在逛 r/rust 的时候发现了这个库。简单来说，就是针对整数构造一个 hash 函数，将输入的值直接输出。也就是说，我们可以零成本地利用整数作为 HashMap 的键，在能得到 HashMap 平均 O(1) 的查找效率的同时不需要将性能浪费在 hash 函数上！

然而事实并非如此，用整数省略 hash 过程可能会让 HashMap 的性能低很多，这与 HashMap 的内部实现有关。

HashMap（HashSet） 的实现

HashMap 和 HashSet 之间唯一的区别就是，HashSet 只存键，HashMap 存键和值（每个键和对应的值是放在一起的，完全可以看作一个 tuple），所以下面都用 HashSet 描述。HashSet 的实现有很多，这里简单描述三个。

C++ STL 中的 unordered_set

STL 没有实现标准，但是对 HashTable 的实现都大同小异，比如 GCC 的实现。

简单来说，就是一块长度为 n 个指针的内存作为 HashSet 的索引，每个指针都指向一个链表，链表里之后要存放的是元素的 hash 值和元素本身。操作时，计算要操作元素的 hash 值，用得到的值模除 n，得到这个元素应该放在这个索引中的哪个位置指向的链表中，然后去链表中执行相应的操作。扩容时，只需要为新节点分配内存，不需要动旧节点的位置。

上面的描述简化了 rehash、链表前导元素等很多细节，不过这些不重要，hash 值模除索引的长度 和 扩容时不需要移动旧节点 是关键。

robin_hood::unordered_set

这是一个很常用的 HashTable 实现，因为性能好，很多人用它代替 STL 的实现。Rust 在 1.36 版本之前的标准库 HashMap 实现也是这个。

robin_hood::unordered_set 有 node 和 flat 两种布局，node 是类似于 STL 版本的链表实现，flat 顾名思义是 probing table 的布局，把元素直接放进一个连续的，类似 vector 的结构。在不考虑容量时 vector 几乎每一项性能都肯定比链表强，因此这个表的实现当然比 STL 版本性能好。

用 STL 版本类比，robin_hood 版就相当于把链表放进了 vector，因此“链表”的最大长度是有限的，只要有任意一个“hash 值模除分段（也就是上面的“链表”）个数“对应的段满了就需要扩容，扩容时需要把每一段增大并依次向内存后部平移，因此开销很大。

上面的描述同样简化了很多细节，不过这些也不重要，hash 值模除分段个数 和 扩容时需要移动旧节点，开销大 是关键。

SwissTable

这是一个新的高性能 HashTable 实现，Rust 在 1.36 版本之后的标准库实现就是这个。

与 robin_hood::unordered_map 的 flat 布局类似，SwissTable 也把值存在连续的内存中，但在查找时并不直接到存放元素的内存部分查，而是建立一个“索引”标识每个内存位置的状态，先到“索引”中查找。

通过这个实现可以理解 hash 值对表性能的影响为什么很大，所以要详细描述一下。当然还是忽略如 Group 之类的无关细节。

建立 HashSet 时，SwissTable 创建了两个类似 vector 的结构，一个是索引表，一个是数据表。两个表的长度一致，对应位置数据之间是相关联的。数据表中存放的是插入 HashSet 的数据本身，索引表中存放的是 1 bit 标识这个位置是否是空位，以及数据 hash 值的后 7 bit，加起来正好是 1 字节。表被分成 n 段，每段中存放的是 hash 值的前 57 bit 模除 n 后结果相同的值。

在操作元素时：

1. 计算需要操作的元素的 hash 值
2. 取 hash 值的前 57 bit 模除 n 得到应该在表的第几分段
3. 前往索引表的这个分段，查找所存储的值与 hash 值的后 7 bit 一致，以及另外那 1 bit 标识不是空位的位置
4. 这时，hash 值的前 57 bit 取模后的值，以及后 7 bit 都已经与需要操作的元素对应了，直接到数据表的对应位置操作数据即可

SwissTable 的设计实在是太精妙了，虽然在这篇文章的主题以外，但还是推荐去看一下 SwissTable 的实现，它能将操作所需的几乎所有数据都放进 L1 缓存，并且通过分组操作实现 SIMD 加速。

跑题了，总之 SwissTable 的重点是 用 hash 的前 57 bit 确定分组位置，后 7 bit 确定元素位置，以及与 robin_hood flat 实现一样的 扩容时需要移动旧节点，开销大。

准备工作完成，终于可以来解答为什么“透明”的 hash 函数不一定好了。

不是所有整数都是平等的

利用之前提到“透明”的 hash 函数，假设有这些数据要插入一个分段数刚好是 100 的 HashTable 中：

100、300、1400、2500、40600、79137500

这些值看似都符合最早提到的对 hash 值的要求，然而模除后所有的余数都是 0，全部都碰撞了。当然这只是极端情况，一般来说 HashTable 的分段数都是 2 的幂。 举这个例子是为了说明：只有当作为键的数模除表分段数 n 的结果在 0 到 n 间均匀散布时， HashTable 的效率才是最高的。不经过 hash 处理的数据很难达到这个要求。

那假如要插入的数据如下（都是 8 位无符号整数）：

0、1、2、3、4、5、6、7、...、255

这组数据确实符合唯一且分布均匀的要求，只要把把这些 8 位无符号整数 cast 成 64 位无符号整数就可以直接作为 hash 值使用？

对于 STL 中的 std::unordered_set 和 robin_hood::unordered_set，确实可以直接作为 hash 值使用。但是对于 SwissTable 就不可以了。把上面这些数加上前导 0 扩充到 64 位，取前 57 位拿来模除，后 7 位放进索引表，会出现一个问题：这些数的前 57 位要么是 0，要么是 1，只有这两种情况，再次出现了非常严重的碰撞。

有什么解决方法吗？当然有：

n = (n >> 1) | (n << 7)

但这也不完美，因为这样 (n >> 1) 就成了索引表中的数据，0 和 1，2 和 3，4 和 5，...，254 和 255 在索引表中的数据变成了一样的，产生了碰撞。

总结

综上，同样的 hash 值，在不同的 HashMap 实现中的性能可能相差巨大。就算是根据统一思路实现的 HashMap，在实现细节上有细微差距，也会导致性能相差悬殊，举个例子：Rust 1.36 后标准库中的 HashTable 采用了 SwissTable，但两者在实现上有一点非常小的区别：原版 SwissTable 将低 7 位放入索引表，而 Rust 实现是将高 7 位放入索引表。这一点微小的不同，就可能会让你本来调教好的“透明” hash 出现严重的碰撞。大量的碰撞意味着大量的扩容，在时间和空间上都会造成浪费。

当然，如果你的数据是：

• 已经 hash 过的数
• 或是保证在 0 到 18446744073709551615(uint64::MAX) 间均匀分布

用“透明” hash 完全没有问题。

所以，除非完全搞懂了要用的 HashMap 实现，否则不要用“透明” hash。对于现代的处理器，对数字进行 hash 几乎可以说是 free 的。

hash 的作用到底是什么？

• 能根据一个任何（支持被 hash）类型的值计算出一个无符号整数
• 对于两个相同的值，hash 出的值必须相等
• 对于两个不同的值，hash 出的值必须有极大概率（接近 100%）不同，也就是碰撞概率要低
• hash 出的值要分布均匀，从而避免在数据结构上的碰撞

最后推荐一个视频：CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” 这是 SwissTable 作者之一在 CppCon 2017 分享如何从 std::unordered_set 一步步优化最后得到 SwissTable，知识密度很高，非常棒的分享。