哈希表是计算机科学中最重要的数据结构之一，它的平均常数时间查找性能使其成为缓存、字典、集合等组件的默认选择。C++标准库中的无序关联容器（unordered_set、unordered_map等）从C++11开始引入，但它们的性能在很长一段时间里并不理想，甚至被诟病为“比std::map还慢”。从C++11到C++23，标准库实现者不断优化哈希表的设计，这场演进揭示了高性能数据结构设计的许多重要原理。
参考：https://bgnno.cn/category/original.html
哈希表的基本原理是简单的：用一个哈希函数将键映射到桶数组的索引，然后将键值对存储在对应的桶中。当哈希冲突发生时（多个键映射到同一个桶），有多种处理策略：链地址法（每个桶是一个链表或数组）、开放寻址法（冲突时探测下一个可用位置）、以及罗宾汉哈希、杜鹃哈希等更高级的方法。
C++标准库的要求给哈希表设计带来了独特的挑战。标准要求插入操作不会使现有的迭代器失效（除非rehashing），这意味着链地址法几乎是唯一的选择——开放寻址法在插入时可能移动已有的元素，从而使指向这些元素的迭代器失效。标准还要求支持透明的查找（C++14之后），即允许用与键不同的类型进行查找，只要哈希函数和相等比较能够处理这种转换。
C++11时代的典型实现（如GCC的libstdc++和LLVM的libc++）采用了一种称为“单链表桶”的简单设计：每个桶是一个单向链表的头节点，链表的节点动态分配。这种设计在负载因子较低时工作良好，但随着元素增多，链表遍历的开销变得显著。更糟糕的是，每个节点都需要单独的内存分配，这导致内存碎片化和缓存局部性差。
参考：https://bgnno.cn/category/game.html
节点内存分配的优化是第一个改进方向。现代实现使用池分配器：不是为每个节点单独调用new，而是从一个大块内存中分配节点，节点释放时放回池中。这减少了内存碎片，提高了分配和释放的速度。GCC的libstdc++从某个版本开始使用_Hashtable_alloc策略，允许自定义节点分配器，默认实现使用池分配。
哈希策略的改进同样关键。传统的哈希表在负载因子超过阈值时进行rehash（重新分配桶数组并重新插入所有元素），但rehash是O(n)操作，可能导致服务延迟尖峰。更好的策略是增量rehash：在插入时逐步移动元素，而不是一次性完成。Java的HashMap采用了这种策略，但C++标准库的实现者需要更谨慎，因为迭代器失效规则的限制。
开放寻址法的回归值得关注。虽然标准不强制要求链地址法，但开放寻址法的迭代器失效问题曾经是主要障碍。C++20引入的reserve和rehash函数给了实现者更多灵活性：如果用户明确调用reserve预分配足够的桶，开放寻址法就可以避免大部分重新哈希。一些实验性实现（如Facebook的Folly库中的F14哈希表）证明了开放寻址法在C++中的可行性，其性能显著优于标准库实现。
SIMD加速的哈希查找是另一个突破。Folly的F14哈希表采用了一种聪明的设计：将桶分为多个组（每组14个槽位，F14因此得名），每个组的元数据（哈希码的高位）存储在单独的数组中，查找时用SIMD指令同时比较多个槽位的元数据。这种设计在现代CPU上可以达到极高的查找性能，因为SIMD可以并行处理14个或更多的比较操作。
参考：https://bgnno.cn/category/anime.html
absl::flat_hash_map（来自Google的Abseil库）则采用了另一种策略：交换表。它将元数据和值分开存储，元数据使用特殊的编码来标记空槽、已占用槽和已删除槽。查找时，先计算哈希值，然后在桶组内进行线性探测，直到找到匹配的键或遇到空槽。由于元数据紧凑（每个槽位只需一个字节），整个元数据组可以轻易放入CPU缓存中，从而加速查找。
这些第三方实现的成功促使标准库实现者跟进。GCC的libstdc++在某个版本后引入了新的哈希表实现（称为std::unordered_map的“新标准布局”），采用了类似F14的设计，但为了保持ABI兼容性，仍然保留了旧实现的接口。LLVM的libc++也在积极改进其哈希表实现，引入开放寻址法作为可选的策略。
除了实现层面的优化，哈希函数的选择也至关重要。C++11标准库的默认哈希函数std::hash对于整数类型只是简单的恒等映射，对于字符串则依赖于标准库实现（GCC使用MurmurHash的变体，LLVM使用CityHash）。这导致了著名的“哈希碰撞攻击”漏洞：如果攻击者能够构造大量哈希值相同的键，哈希表的性能会退化到O(n)，导致拒绝服务攻击。C++20引入了std::hash的新规定，要求哈希函数在编译期可定义，但对防止碰撞攻击没有强制要求。
一个更根本的问题是标准库哈希表的性能保证过于宽松。标准只要求平均常数时间的查找，但没有规定最坏情况下的复杂度。这意味着一个实现可以完全基于链表（退化到O(n)查找）而仍然符合标准。在实际中，开发者常常需要依赖第三方库（如absl、Folly、boost）来获得可预测的高性能哈希表。
C++23的std::flat_map和std::flat_set提供了另一种选择：基于有序向量的关联容器。它们不是哈希表，而是排序数组，查找使用二分查找（O(log n)），但内存占用更紧凑、缓存局部性更好。对于元素数量较少（例如几百个）的场景，flat_map的性能可以超过unordered_map，因为它不需要处理哈希冲突和动态内存分配。
展望未来，C++标准库的哈希表设计将继续演进。可能的改进方向包括：
ABI兼容性的突破：目前标准库哈希表的ABI是固定的，限制了许多优化。C++26可能允许实现者在某些条件下采用新的ABI。
异构查找的进一步优化：允许使用不同类型的键进行查找，避免构造临时键对象。
并发哈希表的标准化：目前标准库的所有容器都不是线程安全的，需要外部同步。标准的并发哈希表将填补这一空白。
编译期哈希表：利用C++的constexpr能力，在编译期构建和查找哈希表。
对于普通开发者来说，理解这些底层设计有助于做出更好的选择：当元素数量少时，考虑使用flat_map或甚至std::vector（排序后二分查找）；当元素数量多时，考虑第三方高性能哈希表；只有当标准库的unordered_map足够好时，才使用它。
参考：https://bgnno.cn
