在 C++ STL 中，unordered_set 和 unordered_map 之所以能够实现接近常数时间的检索效率，完全归功于它们的底层数据结构：哈希表（Hash Table）。今天，我们就来系统地梳理一下哈希的核心概念以及它是如何解决现实问题的。
1. 哈希概念
在传统的顺序结构或平衡树（如红黑树）中，元素在容器中的位置与其关键码（Key）之间没有直接的对应关系。因此，在查找元素时，通常需要进行多次关键码的比较（顺序查找时间复杂度为 O(N)，平衡树为 O(log N)）。
哈希（Hash），又称散列，是一种映射思想。它通过一个特定的函数，使元素的存储位置与它的关键码（Key）之间建立起一种直接的映射关系。基于这种方法构造的结构就叫哈希表。当我们需要查找某个元素时，只需将 Key 带入映射函数计算，就能直接得到该元素的存储位置，理想情况下的时间复杂度可以达到惊人的 O(1)。
当向该结构中：
- 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
- 搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
2. 哈希冲突
理想很丰满，现实很骨感。当我们把各种不同的数据映射到一个有限的存储空间时，必然会遇到一个问题：两个不同的 Key，经过哈希函数的计算后，得到了相同的存储位置。
这种现象就被称为哈希冲突（Hash Collision），或者叫哈希碰撞。由于底层数组的容量总是有限的，而需要存储的数据组合是无限的，因此哈希冲突是不可避免的，我们只能尽量减少冲突，并设计一套合理的机制来解决已经发生的冲突。
3. 哈希函数
引起哈希冲突的一个重要原因在于哈希函数设计不合理。一个优秀的哈希函数应该具备两个特点：计算简单、计算算出的地址能均匀分布在整个空间中。
常见哈希函数
3.1 直接定址法--(常用)
直接定址法是最简单、最直观的哈希函数设计方式。
原理：取关键字（Key）的某个线性函数值作为散列地址。计算公式：
Hash(Key) = A * Key + B（A 和 B 为常数）优点：计算极其简单，并且绝对不会产生哈希冲突（每个 Key 都有唯一对应的专属位置）。缺点：非常挑数据的分布。它要求事先知道关键字的分布情况，如果关键字的数据跨度非常大且非常稀疏（比如只有 1、5、10000 三个数据），就会造成极大的空间浪费。适用场景：关键字分布集中且连续的场景。
经典案例：查找字符串中第一个只出现一次的字符。我们可以直接开辟一个大小为 256 的数组，用字符的 ASCII 码值作为数组下标（即
Hash(char) = char）来统计每个字符出现的次数。
3.2 除留余数法--(常用)
除留余数法是计算机科学中最被广泛使用、也是 C++ STL 底层最常采用的哈希机制之一。
原理：设哈希表中允许的最大地址数为
m，取一个不大于m，但最接近或者等于m的质数（素数）p作为除数，将关键字对p取模。计算公式：Hash(Key) = Key % p（p <= m）为什么除数p最好是质数？：如果除数是合数，容易因为数据的某些规律性导致哈希值集中在特定的几个桶里。质数能最大程度地消除数据本身的规律性，让哈希值更均匀地散布。优点：适用范围极广，不挑数据分布，能有效将大范围的 Key 映射到固定大小的小空间中。：必然会产生哈希冲突，必须配合闭散列或开散列（哈希桶）来处理冲突。
