连续写数据结构系列写到了第三篇前两篇把数组和链表、栈与队列聊得比较细致这篇轮到哈希表。哈希表在很多人的印象里是一个“会用就行”的工具字典、映射、缓存随手就用但真到面试、笔试或者自己设计存储结构的时候经常发现搞不清哈希函数怎么选、冲突怎么处理、负载因子取多少、扩容为什么影响那么大。这篇文章就围绕这些问题展开把它掰开揉碎讲清楚。适合正在补数据结构基础的人也适合那些“用了很久但不清楚内部机制”的朋友。1. 哈希表到底解决了什么问题1.1 从“找人”这个场景讲起假设你维护了一个学生名单里面有几千条记录每条记录包含学号和姓名。现在给你一个学号要求快速找到对应姓名。最朴素的做法是数组线性扫描遍历一次找到目标就返回。时间开销跟数据量成正比几千条还好几百万条就明显变慢了。如果学号是有序的可以用二分查找把复杂度降到对数级别。但这里有个前提数据必须有序。现实业务里点名册的插入顺序往往是随机的每次插入都保持有序维护成本很高。其实我们真正想要的是一步到位给我一个学号直接算出这个学号对应的记录存放在哪个位置就像字典里查拼音首字母直接翻到那一页一样。这个“一步到位”的思路就是哈希表的核心思想。1.2 核心思想散列映射哈希表本质上是一个数组但它不像普通数组那样直接用下标访问而是通过一个函数把“键”转换成数组下标。这个转换函数叫哈希函数。它接收一个键作为输入输出一个整数这个整数就是数组下标。比如把学号 2024001 传入哈希函数得到一个下标 17那么我们就把这条记录存到数组的第 17 个位置。查询的时候同样用学号算出下标 17直接取数组该位置的元素一步到位。这个过程的直观感受是无论数据量多大只要哈希函数计算够快查询的时间几乎不变。这就是哈希表 O(1) 平均复杂度的来源。1.3 整体设计三要素哈希表的设计不是简单地把哈希函数和数组拼起来它由三个关键部分组成第一是数组本身也就是存储桶所有数据最终都落在这些桶里。第二是哈希函数它决定了每个键映射到哪一个桶。这个函数设计得好不好直接影响哈希表的性能和均衡性。第三是冲突处理策略。因为哈希函数把无限大的键空间映射到有限的数组下标必然存在多个键映射到同一个下标的情况这被称为哈希冲突。怎么解决冲突决定了一个哈希表在最坏情况下能退化到多糟糕。三者的关系可以类比成餐厅的座位分配数组是房间里的桌椅哈希函数是引导顾客入座的领位员冲突策略则是座位已经满了的时候怎么安排新来的顾客。任何一个环节设计不合理客人就坐得混乱上菜也慢。2. 哈希函数的设计与选择2.1 设计目标不只是“算得快”很多人觉得哈希函数随便写一个就行其实不然。哈希函数有三个核心目标分布均匀、计算高效、对抗碰撞。分布均匀是指输入键的哈希值应该尽量随机地散布在整个数组范围内不要集中在某几个桶。如果大量数据映射到同一个桶哪怕哈希函数本身很快查询也会因为冲突过多而变慢。计算高效是指哈希函数的执行成本要足够低。哈希表在每次插入和查询时都要调用哈希函数如果它本身是重量级运算整体性能就被拖垮了。对抗碰撞是指在面对刻意构造的输入时哈希函数能尽量避免大量键聚集到同一个桶。这个问题在系统安全里尤其重要。2.2 常见的哈希函数最简单的哈希函数是取模法index key % size。它适用于键为整数、且数据无明显规律的情况。但有个坑如果 size 是偶数而 key 恰好也全是偶数那么取模结果只会落在偶数下标上一半的桶浪费了。所以取模法里模数的选择很关键一般选质数能有效减少周期性聚集。字符串哈希比较常用的是 BKDR 哈希和 DJB2 哈希。BKDR 的核心是unsigned int hash 0; while (*str) { hash hash * 131 (*str); } return hash;乘数 131 是经验值类似的还有 31、33、37 等。这个算法的思路是让字符串的每一位都对最终结果产生影响而且不同位置的字符对结果的权重不同从而降低不同字符串相同哈希值的概率。Java 的 String.hashCode() 用的就是类似 31 倍递推的思路乘以 31 可以用移位减法优化计算速度很快。还有一个经典场景需要特别注意如果键是复合结构比如自定义的对象通常要把每个成员变量的哈希值组合起来。组合的原则是让顺序信息不丢失hash 17 * 31 a.hashCode() * 31 b.hashCode()这种写法是常见实践原因和 BKDR 类似让顺序影响最终结果。2.3 为什么要做“扰动”有些键的数据规律较强比如学号后三位都是连续的、字典序单词前几位相同直接对哈希值取模会导致结果分布不均。一个常见的补救手段是对哈希值进行扰动把高位信息混合到低位。Java 8 里 HashMap 的扰动写法是static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这个操作把低 16 位和高 16 位做异或让高位变化也能影响低位的取模结果。实际项目中我见过不少因为省略这一步导致数据不均匀、查询退化的案例。你设计哈希函数的时候不管用什么算法建议都做一次扰动成本极低收益明显。3. 哈希冲突的三大策略3.1 链地址法最常用也最稳妥链地址法的思路是每个数组桶不直接存数据而是指向一个链表或者其他容器的头结点。当多个键映射到同一个桶时依次挂到链表后面。插入时先算下标再把新节点插到链表头部或尾部。查询时先算下标然后遍历链表查找目标键。这个方案的优势是实现简单容忍哈希函数的质量稍差。即使哈希函数设计得不好数据都挤在一块也只是退化成链表查询不至于完全瘫痪。扩容时也不需要搬移桶内全部数据只用逐个重新计算位置。链表的插入位置是个值得琢磨的细节。Java 8 之前的 HashMap 用头插法代码简洁但并发下扩容时可能产生环形链。Java 8 改成尾插法牺牲了一点插入速度换来了扩容时的安全性。我的建议是凡是可能被多线程操作的数据结构一律用尾插不要为了微小的性能差异给自己埋雷。链地址法有一个容易被忽略的点桶里的链表过长时查询会退化。所以 JDK 8 的 HashMap 在链表长度超过 8 且数组长度不小于 64 时会把链表转成红黑树把查询复杂度从 O(n) 降回 O(log n)。这个细节很能说明问题链地址法不是终点它是可以针对极端情况做优化的。3.2 开放定址法讲究“占位的艺术”开放定址法的思路完全不同不挂链表数据直接存在数组桶里。一旦发生冲突就按某种探测规则在数组里寻找下一个空位。最简单的探测是线性探测。冲突时依次往后找直到找到空位。它的优点是实现简单、缓存友好缺点是容易发生聚集。比如桶 7、8、9 都已经占用此时插入一个哈希到 6 的数据它会一路探测到 10 才能放下造成连续区间的“拥堵”。平方探测试图缓解这个问题探测序列变成 1、4、9、16……这样能更快跳出聚集区域。但平方探测有个数学前提表长必须是素数否则可能探测不到所有空位。双重哈希是更稳的方案第一个哈希函数决定起始位置第二个哈希函数决定探测步长步长不同数据更分散聚集概率更低。开放定址法适合数据量相对可控、删除操作不频繁的场景。需要注意删除操作有个大坑不能直接清空那个桶因为如果这个位置曾经是别人的探测路径清空了会导致后续查询误判为空。必须用一个“已删除”标记代替。3.3 再哈希法与公共溢出区再哈希法比较简单第一次哈希冲突时用第二个哈希函数再算一遍若仍冲突则继续用第三个。问题在于一旦重新哈希出来的下标还是冲突处理起来会很被动。它适合对稳定性要求不高、冲突极少的场景工程中直接用的不如前两种多。公共溢出区则是把所有冲突的数据统统放到一个额外的区域。查找时先查主表主表没有再去溢出区搜索。这个方案在冲突率低的时候查询效率很高一旦冲突率上升溢出区就会膨胀成一个小型线性表性能骤降。所以它更像是一个特定场景下的折中方案不适合作为通用策略。3.4 三种策略对比策略空间占用查询稳定性实现难度删除操作典型应用链地址法较低且虽有链指针但每个桶可共享冲突多时退化为链表简单容易直接摘节点Java HashMap、C unordered_map开放定址法低表中无额外指针冲突多时容易幂次聚集中等需要墓碑标记Python dict早期、Redis 部分场景再哈希法依赖哈希函数组合相对较稳但实现复杂度高较高较复杂负载均衡的扩展哈希公共溢出区多一个独立区域冲突率主导简单需两处维护文件索引、数据库页内哈希我的经验是通用场景默认选链地址法数据量小且能控制删除频率时选开放定址法其余两种做学术了解即可。4. 哈希表的扩容与性能本质4.1 负载因子0.75 是怎么来的负载因子load factor是哈希表里已经存放的元素数量与桶数量的比值。它决定了哈希表的拥挤程度。负载因子越低冲突越少空间浪费越多负载因子越高空间利用率越高冲突概率也越高查询性能随之下降。工程实现里常见的取值是 0.75这个数字是空间和时间成本的平衡点。数学上可以推导当负载因子为 0.75 时桶内链表长度大于 8 的概率非常低近似于泊松分布的长尾。这意味着大部分查询只需要比较一两次键值性能接近理论最优。如果你用的是开放定址法负载因子一般要控制得更低比如 0.5 到 0.6因为一个连续被占用的桶片段会显著放大后续冲突概率。实际操作时不要随意调大负载因子。我曾经为了省内存把 HashMap 的负载因子调到 1.2结果是程序运行时间直接翻倍。内存省的那点远不够弥补时间开销。4.2 扩容的完整流程当元素个数超过负载因子乘以桶数量时哈希表需要扩容。通常的做法是创建新数组容量翻倍然后把旧表里所有元素重新取哈希、重新插入到新表。注意这里必须全面重算因为数组长度变了取模运算里的模数也变了原来映射到桶 5 的数据扩容后可能映射到桶 25。这个过程叫 rehash。之所以强调“全面重算”是因为它是扩容开销的主要来源。旧表里有一万条数据就要重新计算一万次哈希并插入。单次扩容的代价是 O(n)但由于扩容不经常发生均摊下来每次插入依然是 O(1)。这就是均摊复杂度分析的意义。4.3 复杂度分析均摊 O(1) 不等于永远 O(1)“哈希表增删查都是 O(1)”这句话要加一个前提假设哈希函数合理且负载因子控制得当。在这个前提下单次操作的时间由哈希计算加少量冲突处理构成可以视为常数级。但如果哈希函数构造得很差或者数据被恶意设计成哈希值全部相同所有数据都会退化成一条长链表查询复杂度变成 O(n)。这就是哈希攻击的原理。做系统设计时数据来源不可信的场景里必须使用随机种子参与的哈希函数让攻击者无法提前预测哈希值分布。还有一点经常被忽略扩容瞬间的延迟。虽然均摊下来开销不大但如果你在做低延迟系统某一次插入恰好触发扩容这一下的耗时可能远超平均线。解决办法是预分配足够大的初始容量把扩容尽量转移到启动阶段或者允许并发访问的时候。4.4 缓存局部性与红黑树优化链地址法里每个节点是离散分配的遍历链表时指针跳来跳去CPU 缓存命中率不高。开放定址法的数据都落在连续数组里缓存友好性更好。这点在数据量大、查询频繁时表现得非常明显。我做过一个对比测试同样数据集下开放定址法每秒查询次数大约是链地址法的两倍多代价就是删除逻辑复杂、负载因子更敏感。工程实现里优化链地址法的方式是把链表转树这个在前面提到了本质是牺牲一定的插入开销换取极端情况下的查询稳定性。阈值取 8 不是拍脑袋而是泊松分布计算出的结果随机哈希下链表长度超过 8 的概率低于千万分之一一旦触发大概率是哈希函数被破解或者数据分布有问题。5. 实操从零手写一个哈希表5.1 动手前的设计思路为了把前面几章的内容串起来我用 Python 手写一个简化版哈希表。选择 Python 是因为适合演示逻辑真正的工程实现比如 C 或 Java逻辑相同代码细节略有差别。设计目标支持 put(key, value)、get(key)、delete(key) 三个操作使用链地址法解决冲突自动扩容负载因子设为 0.75哈希函数的实现要点先列出来对字符串使用类似 BKDR 的思路然后做一次扰动5.2 核心代码实现class Node: def __init__(self, key, value): self.key key self.value value self.next None class HashTable: def __init__(self, capacity16): self.capacity capacity self.size 0 self.buckets [None] * capacity self.load_factor 0.75 def _hash(self, key): # 字符串哈希用 31 倍递推 h 0 for ch in str(key): h h * 31 ord(ch) # 扰动让高16位影响低16位 h (h ^ (h 16)) 0x7fffffff return h % self.capacity def _resize(self): old_buckets self.buckets self.capacity self.capacity * 2 self.buckets [None] * self.capacity self.size 0 for head in old_buckets: node head while node: self.put(node.key, node.value) node node.next def put(self, key, value): index self._hash(key) node self.buckets[index] while node: if node.key key: node.value value return node node.next new_node Node(key, value) new_node.next self.buckets[index] self.buckets[index] new_node self.size 1 if self.size / self.capacity self.load_factor: self._resize() def get(self, key): index self._hash(key) node self.buckets[index] while node: if node.key key: return node.value node node.next raise KeyError(key) def delete(self, key): index self._hash(key) node self.buckets[index] prev None while node: if node.key key: if prev: prev.next node.next else: self.buckets[index] node.next self.size - 1 return prev node node node.next raise KeyError(key) def __str__(self): res {} for head in self.buckets: node head while node: res[node.key] node.value node node.next return str(res)5.3 关键代码的思考put里我用了头插法实现就是new_node.next self.buckets[index]这句。配合容量翻倍机制在单线程场景下没问题。如果你要支持并发修改请改成尾插或者直接加锁。_hash里对字符串做了 BKDR 风格的乘加然后做了一次“异或高位再取低位”的扰动最后对当前容量取模。注意我取了 0x7fffffff目的是保证结果是正数避免 Python 里负号取模造成下标越界。_resize看起来简单但有一个性能隐患它调用了put而put里又包含一次负载因子判断虽然这次判断一定不触发但这种写法在工程代码里不算优雅。更优的做法是把插入逻辑抽成内部方法不检查扩容条件。我这里为了演示简洁合在一起了实际项目中别这么干。扩容后数组大小变成原来的两倍但不是两倍总能保证哈希分布均匀。如果容量是偶数且哈希函数存在周期性数据可能集中在部分桶。很多实现里会把容量固定为 2 的幂然后用位运算替代取模这是一种空间换速度的取舍。5.4 测试与性能观察table HashTable(4) for i in range(20): table.put(fuser_{i}, i) print(table.get(user_5)) # 输出 5 table.delete(user_7) print(user_7 in str(table)) # False print(size:, table.size) print(capacity:, table.capacity)程序运行后初始容量是 4但插到第三个元素时3 / 4 0.75就会触发扩容之后容量变成 8再插入到第六个元素时再次扩容到 16。所以你看到的最终容量不会是 16 就是 32取决于具体插入了多少元素。如果你实际测试会发现频繁扩容的插入操作耗时明显高于后面批量插入。这个现象正好印证了扩容的 O(n) 开销和均摊 O(1) 的本质。6. 不同语言里哈希表的实现差异6.1 Python 的 dict稀疏表与随机化哈希Python 内置 dict 的底层实现和前面讲的链地址法不一样它用的是开放定址法而且是带有“稀疏”思想的实现。Python dict 的每个槽位有 3 种状态未使用、已占用、已删除标记为 dummy。插入时从起始索引开始探测直到找到未使用或 dummy 的槽位查询时遇到空槽就停止因为这意味着这个键肯定不存在。Python 3.6 之后的 dict 做了很大的优化底层的存储结构分成了两块一块存索引另一块按插入顺序存实际键值。这样既保留了哈希表的快速查找又额外获得了“有序”的迭代行为。这个特性是语言设计层面为实际业务场景做的妥协哈希表本来不保证顺序但使用者普遍希望迭代顺序稳定于是就在存储层动了手脚。还有个细节是 Python 的字符串哈希默认带随机化种子同一运行时字符串哈希值是固定的但跨进程运行不一样。这是为了防哈希碰撞攻击。你在两个不同的解释器进程里运行相同字符串的hash()结果往往不同这是有意为之的。6.2 Java 的 HashMap从链表到红黑树JDK 8 的 HashMap 是一个非常典型的链地址法实现细节处理得比较讲究。数组的初始容量是 16且容量固定为 2 的幂。这样取模可以优化成位运算(n - 1) hash比取模更快。这个细节配合容量翻倍机制保证哈希值分布良好。链表长度超过 8 且数组长度达到 64 时链表转红黑树树节点的查找复杂度是 O(log n)。如果数组长度还没到 64则先扩容而不是转树因为扩容本身就能把链表拆散让数据重新分布。HashMap 允许 key 为 nullnull 的哈希值被规定为 0所以它被放到下标为 0 的桶里。删除时如果节点是树节点需要调用专门的删除逻辑保证红黑树的性质不破坏。Java 的 HashMap 还有很多细节值得去看源码默认负载因子 0.75、扩容时容量左移一位、树化阈值和反树化阈值的区别。这些东西在面试里被反复问不是没有道理因为它们直接反映了一个工业级哈希表要考虑多少极端情况。6.3 Go 的 map 与 C 的 unordered_mapGo 的 map 内部实现用的是桶数组加溢出桶的组合每一个桶可以存 8 个键值对。桶满了之后新的键值对放到溢出桶里溢出桶之间用链表连接。这种设计综合了链地址法和开放定址法的优点——主桶保持连续的存储布局溢出桶兜底处理极端情况。C 的 unordered_map 标准实现是链地址法底层是 vector 加单向链表。它的哈希策略和扩容依据不同的标准库实现有所差异使用时要特别注意迭代器失效的时机。unordered_map 的 rehash 会触发所有迭代器重新计算这一点和 vector 扩容时的迭代器失效有异曲同工之处。我从这些实现差异里得到的启发是没有绝对最好的哈希表结构只有适不适合当前负载特征的选择。顺序访问频繁就用开放定址系极端冲突风险高就用链地址加树化内存受限就压缩存储密度。7. 哈希表的典型应用场景7.1 缓存设计的核心底座内存缓存、字典去重、LRU 缓存淘汰这些功能底层几乎都离不开哈希表。以 LRU 缓存为例经典实现是哈希表加双向链表哈希表负责 O(1) 时间定位数据节点双向链表负责维护访问顺序。哈希表在其中的作用就是让“查一个节点是否存在于缓存”这个操作不再需要遍历链表。缓存场景下最容易踩的坑是 key 设计不当。比如用拼接字符串当 key但是拼接顺序不稳定同一个逻辑键在不同地方拼出来不一致导致缓存命中率骤降。而且如果 key 的内容是用户可控制的还可能出现哈希碰撞攻击。我的经验是缓存 key 一定要规范化成稳定、简洁且可哈希的实体。7.2 字符串匹配与统计数据统计词频统计是最典型的哈希表应用场景。遍历单词表每个单词作为 key出现次数作为 value一次遍历即可完成统计。如果换成数组或链表每次插一个单词都要检查历史里是否有这个词复杂度直接变成 O(n²)。文件查重、URL 去重、日志聚合也类似。核心套路都是“用哈希表维护一个已见集合”查询和插入都要求 O(1)否则数据量一大就扛不住。还有一个变化分布式系统里的布隆过滤器。布隆过滤器本质上是多个哈希函数作用于同一个位数组它和哈希表的区别是允许误判存在但不允许误判不存在。很多场景里布隆过滤器作为哈希表的“前置拦截层”先快速判断“肯定不存在”再决定要不要走哈希表或磁盘。7.3 负载均衡与一致性哈希一致性哈希解决的是分布式缓存节点变化时缓存命中率暴跌的问题。它的思路是把哈希空间看成一个环节点和数据都映射到环上数据只路由到它在环上顺时针碰到的第一个节点。当节点增加或减少时只有环上一部分数据需要重定位而不是全局洗牌。这个方案里哈希函数的选择很关键节点哈希要散列均匀否则物理节点分布密集的区域负载会明显高于稀疏区域。工程上往往引入“虚拟节点”的概念把一个物理节点复制出几十个哈希位置使分布更均匀。哈希表在这一整套体系里的角色是“把任意输入的键均匀映射到固定范围内”它解决的问题不只是一个数据结构而是分布式系统里的数据放置策略问题。8. 常见问题与排查经验8.1 哈希碰撞导致性能退化现象某段代码上线后CPU 使用率一直走高接口延迟从 10ms 涨到几百毫秒。查日志发现有一个哈希表里的桶链表长度动辄几十上百正常的平均链表长度应该小于 1。排查步骤在哈希表入口处统计每个桶的链表长度分布确认是否存在明显的长尾。检查数据的键是否具有规律性比如时间戳周期性、IP 地址高位固定。检查哈希函数是否对输入的全部信息都敏感。之前遇到过一个案例某个自定义对象的 hashCode 只取了其中一个字段的值另一个字段完全被忽略导致所有值相同的对象全部落到同一个桶。解决方向改进哈希函数的输入覆盖范围增加扰动必要时引入随机种子。8.2 扩容瞬间卡顿现象线上服务运行平稳但每到某个时间点会出现一次明显的延迟尖峰之后又恢复正常。排查发现那个时间点触发了大量的哈希表插入而插入数量刚好越过负载因子阈值触发了大规模 rehash。解决方向有两种一是预估数据量初始化时给足容量把扩容发生在启动阶段二是把哈希表的扩容改成渐进式分多次完成避免单次耗时过长。渐进式扩容在 Redis 的字典实现里体现得很明显它维护两个哈希表扩容时把数据从一个往另一个逐步搬移每次增删查操作都顺带搬移若干节点。这种工程优化在低延迟系统里非常有价值。8.3 并发环境下数据过期的坑哈希表的节点在并发访问时最怕扩容和删除同时发生。扩容过程需要遍历旧表并重插如果另一个线程正在读可能会读到不一致的状态。实际项目中如果并发要求高优先选择语言自带的并发哈希容器比如 Java 的 ConcurrentHashMap。它把哈希表分成多个分段分别加锁扩容时只锁相关分段避免全表锁死。自己实现并发哈希表的时候不要想着用一个全局锁糊弄过去一定要考虑锁粒度的问题。8.4 我踩过的一个真实教训说一个我自己早期做过的项目当时设计了一个用户维度的缓存系统把用户 ID 和用户资料同时拼在一起作为 key再用哈希表存储。表面上看没什么问题但用户 ID 中有一部分是连续数字而哈希函数对连续数字又没有做充分扰动导致这些 key 大量汇聚在相邻的桶上。排查过程很折腾因为单个看每个 key 都很正常只有把桶的分布画出来才看出问题。后面换了一个带扰动的哈希函数并且把用户资料单独作为 key问题才彻底解决。这个教训我反复讲哈希表用得好不好一半在哈希函数设计另一半在于你对数据特征的敏感度。越是看起来“没什么规律”的数据越要小心它们在某一个维度上其实高度同构。哈希表看似简单但它的细节深挖下去可以写好几篇长文。从哈希函数的选择到冲突策略的取舍再到扩容机制和并发安全每一个环节的微小差异都会在大数据量和极端场景下被放大成明显的性能差异。实际工作中多分析数据特征、多测试分布情况、多关注底层实现比背多少理论都管用。
