哈希表完全指南：从哈希函数、冲突处理到工程实现

大家好，我是程序员思绪

哈希表是工程中最常用的数据结构之一。缓存、索引、去重、计数器和对象映射都离不开它。理想情况下，哈希表能在 O(1) 时间内完成插入、查询和删除；但这个结论隐含了许多条件：哈希函数足够均匀、负载因子受到控制、冲突得到妥善处理，而且键在生命周期内保持稳定。

本文从数组寻址出发，解释哈希函数、冲突处理、扩容和复杂度退化，并实现一个支持扩容的泛型哈希表。读完后，你不仅会使用 HashMap，还能够解释它为何快、何时会慢，以及怎样为业务对象设计可靠的键。

1. 哈希表解决了什么问题

数组可以通过下标直接定位元素，但业务数据的键通常是字符串、订单号或复合对象，不能直接作为数组下标。哈希表在业务键与数组下标之间增加一个映射过程：

#mermaid-svg-lmStyQVpol6Hccs9{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-lmStyQVpol6Hccs9 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-lmStyQVpol6Hccs9 .error-icon{fill:#552222;}#mermaid-svg-lmStyQVpol6Hccs9 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-lmStyQVpol6Hccs9 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-lmStyQVpol6Hccs9 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-lmStyQVpol6Hccs9 .marker.cross{stroke:#333333;}#mermaid-svg-lmStyQVpol6Hccs9 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-lmStyQVpol6Hccs9 p{margin:0;}#mermaid-svg-lmStyQVpol6Hccs9 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-lmStyQVpol6Hccs9 .cluster-label text{fill:#333;}#mermaid-svg-lmStyQVpol6Hccs9 .cluster-label span{color:#333;}#mermaid-svg-lmStyQVpol6Hccs9 .cluster-label span p{background-color:transparent;}#mermaid-svg-lmStyQVpol6Hccs9 .label text,#mermaid-svg-lmStyQVpol6Hccs9 span{fill:#333;color:#333;}#mermaid-svg-lmStyQVpol6Hccs9 .node rect,#mermaid-svg-lmStyQVpol6Hccs9 .node circle,#mermaid-svg-lmStyQVpol6Hccs9 .node ellipse,#mermaid-svg-lmStyQVpol6Hccs9 .node polygon,#mermaid-svg-lmStyQVpol6Hccs9 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-lmStyQVpol6Hccs9 .rough-node .label text,#mermaid-svg-lmStyQVpol6Hccs9 .node .label text,#mermaid-svg-lmStyQVpol6Hccs9 .image-shape .label,#mermaid-svg-lmStyQVpol6Hccs9 .icon-shape .label{text-anchor:middle;}#mermaid-svg-lmStyQVpol6Hccs9 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-lmStyQVpol6Hccs9 .rough-node .label,#mermaid-svg-lmStyQVpol6Hccs9 .node .label,#mermaid-svg-lmStyQVpol6Hccs9 .image-shape .label,#mermaid-svg-lmStyQVpol6Hccs9 .icon-shape .label{text-align:center;}#mermaid-svg-lmStyQVpol6Hccs9 .node.clickable{cursor:pointer;}#mermaid-svg-lmStyQVpol6Hccs9 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-lmStyQVpol6Hccs9 .arrowheadPath{fill:#333333;}#mermaid-svg-lmStyQVpol6Hccs9 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-lmStyQVpol6Hccs9 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-lmStyQVpol6Hccs9 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-lmStyQVpol6Hccs9 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-lmStyQVpol6Hccs9 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-lmStyQVpol6Hccs9 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-lmStyQVpol6Hccs9 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-lmStyQVpol6Hccs9 .cluster text{fill:#333;}#mermaid-svg-lmStyQVpol6Hccs9 .cluster span{color:#333;}#mermaid-svg-lmStyQVpol6Hccs9 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-lmStyQVpol6Hccs9 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-lmStyQVpol6Hccs9 rect.text{fill:none;stroke-width:0;}#mermaid-svg-lmStyQVpol6Hccs9 .icon-shape,#mermaid-svg-lmStyQVpol6Hccs9 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-lmStyQVpol6Hccs9 .icon-shape p,#mermaid-svg-lmStyQVpol6Hccs9 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-lmStyQVpol6Hccs9 .icon-shape .label rect,#mermaid-svg-lmStyQVpol6Hccs9 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-lmStyQVpol6Hccs9 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-lmStyQVpol6Hccs9 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-lmStyQVpol6Hccs9 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}#mermaid-svg-lmStyQVpol6Hccs9 .input>*{fill:#e8f1ff!important;stroke:#2563eb!important;color:#172554!important;}#mermaid-svg-lmStyQVpol6Hccs9 .input span{fill:#e8f1ff!important;stroke:#2563eb!important;color:#172554!important;}#mermaid-svg-lmStyQVpol6Hccs9 .input tspan{fill:#172554!important;}#mermaid-svg-lmStyQVpol6Hccs9 .process>*{fill:#fff7ed!important;stroke:#ea580c!important;color:#7c2d12!important;}#mermaid-svg-lmStyQVpol6Hccs9 .process span{fill:#fff7ed!important;stroke:#ea580c!important;color:#7c2d12!important;}#mermaid-svg-lmStyQVpol6Hccs9 .process tspan{fill:#7c2d12!important;}#mermaid-svg-lmStyQVpol6Hccs9 .result>*{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-lmStyQVpol6Hccs9 .result span{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-lmStyQVpol6Hccs9 .result tspan{fill:#064e3b!important;}

是

否

业务键user:10086

计算 hash得到整数散列值

映射到桶下标index = hash & (capacity – 1)

访问对应桶

桶内是否存在相等的键?

返回或更新 value

报告不存在或插入新节点

这个过程包含两个不同概念：

• 哈希值是哈希函数根据键计算出的整数；
• 桶下标是根据哈希值和数组容量计算出的位置。

哈希值不等于桶下标。数组容量有限，不同哈希值必然可能映射到同一个桶，这就是哈希冲突。

2. 一个好的哈希函数需要什么

哈希函数的任务不是保证“永不冲突”，因为把无限或巨大键空间映射到有限数组时，冲突在数学上不可避免。它真正要做的是让键尽可能均匀地分散到各个桶中。

一个实用的哈希函数通常具备以下性质：

需要区分数据结构使用的普通哈希与密码学哈希。哈希表通常追求速度和分布均匀；密码学哈希还要求抗碰撞、抗原像攻击等安全属性。除非要抵御恶意输入，否则在内存哈希表中使用 SHA-256 往往没有必要。

2.1 为什么还要扰动高位

当容量为 2 的幂时，可以用位运算代替取模：

index = hash & (capacity – 1)

若容量是 16，掩码就是二进制 0000 1111，桶下标只取决于哈希值低 4 位。假如一批键的差异集中在高位，它们仍可能落入同一个桶。因此 Java HashMap 会将原哈希值的高位与低位异或，让高位信息参与寻址：

static int spread(int hash) {
return hash ^ (hash >>> 16);
}

扰动不能修复一个质量极差的 hashCode()，但能降低“高位变化丰富、低位变化不足”造成的碰撞。

3. 冲突处理：链地址法与开放寻址法

3.1 链地址法

链地址法让数组中的每个桶保存一个节点集合。发生冲突时，新键进入同一桶的链表或树中。

#mermaid-svg-2A6dUnHsip7nlSFI{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-2A6dUnHsip7nlSFI .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-2A6dUnHsip7nlSFI .error-icon{fill:#552222;}#mermaid-svg-2A6dUnHsip7nlSFI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-2A6dUnHsip7nlSFI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-2A6dUnHsip7nlSFI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-2A6dUnHsip7nlSFI .marker.cross{stroke:#333333;}#mermaid-svg-2A6dUnHsip7nlSFI svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-2A6dUnHsip7nlSFI p{margin:0;}#mermaid-svg-2A6dUnHsip7nlSFI .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-2A6dUnHsip7nlSFI .cluster-label text{fill:#333;}#mermaid-svg-2A6dUnHsip7nlSFI .cluster-label span{color:#333;}#mermaid-svg-2A6dUnHsip7nlSFI .cluster-label span p{background-color:transparent;}#mermaid-svg-2A6dUnHsip7nlSFI .label text,#mermaid-svg-2A6dUnHsip7nlSFI span{fill:#333;color:#333;}#mermaid-svg-2A6dUnHsip7nlSFI .node rect,#mermaid-svg-2A6dUnHsip7nlSFI .node circle,#mermaid-svg-2A6dUnHsip7nlSFI .node ellipse,#mermaid-svg-2A6dUnHsip7nlSFI .node polygon,#mermaid-svg-2A6dUnHsip7nlSFI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-2A6dUnHsip7nlSFI .rough-node .label text,#mermaid-svg-2A6dUnHsip7nlSFI .node .label text,#mermaid-svg-2A6dUnHsip7nlSFI .image-shape .label,#mermaid-svg-2A6dUnHsip7nlSFI .icon-shape .label{text-anchor:middle;}#mermaid-svg-2A6dUnHsip7nlSFI .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-2A6dUnHsip7nlSFI .rough-node .label,#mermaid-svg-2A6dUnHsip7nlSFI .node .label,#mermaid-svg-2A6dUnHsip7nlSFI .image-shape .label,#mermaid-svg-2A6dUnHsip7nlSFI .icon-shape .label{text-align:center;}#mermaid-svg-2A6dUnHsip7nlSFI .node.clickable{cursor:pointer;}#mermaid-svg-2A6dUnHsip7nlSFI .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-2A6dUnHsip7nlSFI .arrowheadPath{fill:#333333;}#mermaid-svg-2A6dUnHsip7nlSFI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-2A6dUnHsip7nlSFI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-2A6dUnHsip7nlSFI .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-2A6dUnHsip7nlSFI .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-2A6dUnHsip7nlSFI .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-2A6dUnHsip7nlSFI .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-2A6dUnHsip7nlSFI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-2A6dUnHsip7nlSFI .cluster text{fill:#333;}#mermaid-svg-2A6dUnHsip7nlSFI .cluster span{color:#333;}#mermaid-svg-2A6dUnHsip7nlSFI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-2A6dUnHsip7nlSFI .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-2A6dUnHsip7nlSFI rect.text{fill:none;stroke-width:0;}#mermaid-svg-2A6dUnHsip7nlSFI .icon-shape,#mermaid-svg-2A6dUnHsip7nlSFI .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-2A6dUnHsip7nlSFI .icon-shape p,#mermaid-svg-2A6dUnHsip7nlSFI .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-2A6dUnHsip7nlSFI .icon-shape .label rect,#mermaid-svg-2A6dUnHsip7nlSFI .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-2A6dUnHsip7nlSFI .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-2A6dUnHsip7nlSFI .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-2A6dUnHsip7nlSFI :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}#mermaid-svg-2A6dUnHsip7nlSFI .bucket>*{fill:#e8f1ff!important;stroke:#2563eb!important;color:#172554!important;}#mermaid-svg-2A6dUnHsip7nlSFI .bucket span{fill:#e8f1ff!important;stroke:#2563eb!important;color:#172554!important;}#mermaid-svg-2A6dUnHsip7nlSFI .bucket tspan{fill:#172554!important;}#mermaid-svg-2A6dUnHsip7nlSFI .node>*{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-2A6dUnHsip7nlSFI .node span{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-2A6dUnHsip7nlSFI .node tspan{fill:#064e3b!important;}

桶数组 capacity = 8

bucket 0: null

bucket 1

bucket 2: null

bucket 3

bucket 4: null

bucket 5: null

bucket 6: null

bucket 7: null

key=A, value=17

key=E, value=42

key=C, value=25

key=K, value=31

key=Z, value=9

查询时先定位桶，再逐个比较桶内节点。链地址法的优点是删除简单、对较高负载更宽容，缺点是节点对象带来额外内存开销，链式访问对 CPU Cache 不够友好。

Java 8 之后的 HashMap 在桶内节点过多且数组容量达到条件时，会把链表转换为红黑树，将单桶查询从 O(k) 改善为 O(log k)。这里的 k 是该桶中的元素数。树化是一种极端碰撞下的保护措施，不代表哈希表整体操作天然是 O(log n)。

3.2 开放寻址法

开放寻址法把所有元素直接存入数组。目标位置被占用时，按照探测序列寻找下一个可用槽位。线性探测的规则最直观：

index_i = (initialIndex + i) mod capacity

#mermaid-svg-OjAXyDaHdf5C4PTC{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-OjAXyDaHdf5C4PTC .error-icon{fill:#552222;}#mermaid-svg-OjAXyDaHdf5C4PTC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-OjAXyDaHdf5C4PTC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-OjAXyDaHdf5C4PTC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-OjAXyDaHdf5C4PTC .marker.cross{stroke:#333333;}#mermaid-svg-OjAXyDaHdf5C4PTC svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-OjAXyDaHdf5C4PTC p{margin:0;}#mermaid-svg-OjAXyDaHdf5C4PTC .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC .cluster-label text{fill:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC .cluster-label span{color:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC .cluster-label span p{background-color:transparent;}#mermaid-svg-OjAXyDaHdf5C4PTC .label text,#mermaid-svg-OjAXyDaHdf5C4PTC span{fill:#333;color:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC .node rect,#mermaid-svg-OjAXyDaHdf5C4PTC .node circle,#mermaid-svg-OjAXyDaHdf5C4PTC .node ellipse,#mermaid-svg-OjAXyDaHdf5C4PTC .node polygon,#mermaid-svg-OjAXyDaHdf5C4PTC .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-OjAXyDaHdf5C4PTC .rough-node .label text,#mermaid-svg-OjAXyDaHdf5C4PTC .node .label text,#mermaid-svg-OjAXyDaHdf5C4PTC .image-shape .label,#mermaid-svg-OjAXyDaHdf5C4PTC .icon-shape .label{text-anchor:middle;}#mermaid-svg-OjAXyDaHdf5C4PTC .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-OjAXyDaHdf5C4PTC .rough-node .label,#mermaid-svg-OjAXyDaHdf5C4PTC .node .label,#mermaid-svg-OjAXyDaHdf5C4PTC .image-shape .label,#mermaid-svg-OjAXyDaHdf5C4PTC .icon-shape .label{text-align:center;}#mermaid-svg-OjAXyDaHdf5C4PTC .node.clickable{cursor:pointer;}#mermaid-svg-OjAXyDaHdf5C4PTC .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-OjAXyDaHdf5C4PTC .arrowheadPath{fill:#333333;}#mermaid-svg-OjAXyDaHdf5C4PTC .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-OjAXyDaHdf5C4PTC .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-OjAXyDaHdf5C4PTC .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-OjAXyDaHdf5C4PTC .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-OjAXyDaHdf5C4PTC .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-OjAXyDaHdf5C4PTC .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-OjAXyDaHdf5C4PTC .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-OjAXyDaHdf5C4PTC .cluster text{fill:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC .cluster span{color:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-OjAXyDaHdf5C4PTC .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-OjAXyDaHdf5C4PTC rect.text{fill:none;stroke-width:0;}#mermaid-svg-OjAXyDaHdf5C4PTC .icon-shape,#mermaid-svg-OjAXyDaHdf5C4PTC .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-OjAXyDaHdf5C4PTC .icon-shape p,#mermaid-svg-OjAXyDaHdf5C4PTC .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-OjAXyDaHdf5C4PTC .icon-shape .label rect,#mermaid-svg-OjAXyDaHdf5C4PTC .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-OjAXyDaHdf5C4PTC .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-OjAXyDaHdf5C4PTC .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-OjAXyDaHdf5C4PTC :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}#mermaid-svg-OjAXyDaHdf5C4PTC .check>*{fill:#fff7ed!important;stroke:#ea580c!important;color:#7c2d12!important;}#mermaid-svg-OjAXyDaHdf5C4PTC .check span{fill:#fff7ed!important;stroke:#ea580c!important;color:#7c2d12!important;}#mermaid-svg-OjAXyDaHdf5C4PTC .check tspan{fill:#7c2d12!important;}#mermaid-svg-OjAXyDaHdf5C4PTC .done>*{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-OjAXyDaHdf5C4PTC .done span{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-OjAXyDaHdf5C4PTC .done tspan{fill:#064e3b!important;}

是

是

否

键 K 的初始位置 = 3

槽 3 已占用?

槽 4 已占用?

槽 5 已占用?

将 K 放入槽 5

开放寻址的数据连续，通常有更好的局部性，也避免了每个节点单独分配对象。但随着负载因子升高，探测序列会迅速变长；线性探测还容易形成连续聚集。删除时不能简单清空槽位，否则后续查询会过早停止，通常需要设置“墓碑”标记或移动元素。

4. 负载因子为什么决定性能

负载因子表示元素数量与桶数组容量之比：

loadFactor = size / capacity

负载因子越低，冲突通常越少，但空桶占用的内存越多；负载因子越高，空间利用率更好，但单桶节点数或探测次数会上升。链地址哈希表常用 0.75 作为空间和时间的经验折中，但它不是适用于所有实现的定律。

当 size > capacity × thresholdFactor 时，通常需要扩容：

#mermaid-svg-QaLCPke8mhh3HsX5{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-QaLCPke8mhh3HsX5 .error-icon{fill:#552222;}#mermaid-svg-QaLCPke8mhh3HsX5 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-QaLCPke8mhh3HsX5 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-QaLCPke8mhh3HsX5 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-QaLCPke8mhh3HsX5 .marker.cross{stroke:#333333;}#mermaid-svg-QaLCPke8mhh3HsX5 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-QaLCPke8mhh3HsX5 p{margin:0;}#mermaid-svg-QaLCPke8mhh3HsX5 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 .cluster-label text{fill:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 .cluster-label span{color:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 .cluster-label span p{background-color:transparent;}#mermaid-svg-QaLCPke8mhh3HsX5 .label text,#mermaid-svg-QaLCPke8mhh3HsX5 span{fill:#333;color:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 .node rect,#mermaid-svg-QaLCPke8mhh3HsX5 .node circle,#mermaid-svg-QaLCPke8mhh3HsX5 .node ellipse,#mermaid-svg-QaLCPke8mhh3HsX5 .node polygon,#mermaid-svg-QaLCPke8mhh3HsX5 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-QaLCPke8mhh3HsX5 .rough-node .label text,#mermaid-svg-QaLCPke8mhh3HsX5 .node .label text,#mermaid-svg-QaLCPke8mhh3HsX5 .image-shape .label,#mermaid-svg-QaLCPke8mhh3HsX5 .icon-shape .label{text-anchor:middle;}#mermaid-svg-QaLCPke8mhh3HsX5 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-QaLCPke8mhh3HsX5 .rough-node .label,#mermaid-svg-QaLCPke8mhh3HsX5 .node .label,#mermaid-svg-QaLCPke8mhh3HsX5 .image-shape .label,#mermaid-svg-QaLCPke8mhh3HsX5 .icon-shape .label{text-align:center;}#mermaid-svg-QaLCPke8mhh3HsX5 .node.clickable{cursor:pointer;}#mermaid-svg-QaLCPke8mhh3HsX5 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-QaLCPke8mhh3HsX5 .arrowheadPath{fill:#333333;}#mermaid-svg-QaLCPke8mhh3HsX5 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-QaLCPke8mhh3HsX5 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-QaLCPke8mhh3HsX5 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-QaLCPke8mhh3HsX5 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-QaLCPke8mhh3HsX5 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-QaLCPke8mhh3HsX5 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-QaLCPke8mhh3HsX5 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-QaLCPke8mhh3HsX5 .cluster text{fill:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 .cluster span{color:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-QaLCPke8mhh3HsX5 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-QaLCPke8mhh3HsX5 rect.text{fill:none;stroke-width:0;}#mermaid-svg-QaLCPke8mhh3HsX5 .icon-shape,#mermaid-svg-QaLCPke8mhh3HsX5 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-QaLCPke8mhh3HsX5 .icon-shape p,#mermaid-svg-QaLCPke8mhh3HsX5 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-QaLCPke8mhh3HsX5 .icon-shape .label rect,#mermaid-svg-QaLCPke8mhh3HsX5 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-QaLCPke8mhh3HsX5 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-QaLCPke8mhh3HsX5 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-QaLCPke8mhh3HsX5 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}#mermaid-svg-QaLCPke8mhh3HsX5 .normal>*{fill:#e8f1ff!important;stroke:#2563eb!important;color:#172554!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .normal span{fill:#e8f1ff!important;stroke:#2563eb!important;color:#172554!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .normal tspan{fill:#172554!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .resize>*{fill:#fff7ed!important;stroke:#ea580c!important;color:#7c2d12!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .resize span{fill:#fff7ed!important;stroke:#ea580c!important;color:#7c2d12!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .resize tspan{fill:#7c2d12!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .done>*{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .done span{fill:#ecfdf5!important;stroke:#059669!important;color:#064e3b!important;}#mermaid-svg-QaLCPke8mhh3HsX5 .done tspan{fill:#064e3b!important;}

否

是

插入新键值对

size 加 1

size 是否超过阈值?

插入完成

创建更大的桶数组

遍历旧表中的所有节点

按新容量重新计算桶下标

将节点迁移到新桶

替换旧数组并更新阈值

扩容不能只把旧数组复制到新数组。桶下标依赖容量，容量变化后，元素需要重新分布。一次扩容要搬迁 n 个元素，成本是 O(n)；但容量按倍数增长时，多次插入的平均成本仍可摊还为 O(1)。

若已知大致元素数量，应在创建哈希表时预估容量，减少扩容和瞬时内存峰值。以负载因子 0.75 为例，计划放入 expectedSize 个元素时，所需容量至少约为：

requiredCapacity = ceil(expectedSize / 0.75)

实际库可能还会把容量向上调整到 2 的幂，并限制最大容量。

5. 从零实现一个链地址哈希表

下面的 Java 实现支持 put、get、remove 和自动扩容。它用于展示核心机制，不包含迭代器、并发控制和红黑树化等标准库特性。

import java.util.Objects;

public final class SimpleHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;

private Node<K, V>[] table;
private int size;
private int threshold;

@SuppressWarnings("unchecked")
public SimpleHashMap() {
table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
}

public V get(K key) {
int hash = spread(Objects.hashCode(key));
Node<K, V> node = table[index(hash, table.length)];

while (node != null) {
if (node.hash == hash && Objects.equals(node.key, key)) {
return node.value;
}
node = node.next;
}
return null;
}

public V put(K key, V value) {
int hash = spread(Objects.hashCode(key));
int bucket = index(hash, table.length);

for (Node<K, V> node = table[bucket]; node != null; node = node.next) {
if (node.hash == hash && Objects.equals(node.key, key)) {
V oldValue = node.value;
node.value = value;
return oldValue;
}
}

table[bucket] = new Node<>(hash, key, value, table[bucket]);
size++;
if (size > threshold) {
resize();
}
return null;
}

public V remove(K key) {
int hash = spread(Objects.hashCode(key));
int bucket = index(hash, table.length);
Node<K, V> previous = null;
Node<K, V> current = table[bucket];

while (current != null) {
if (current.hash == hash && Objects.equals(current.key, key)) {
if (previous == null) {
table[bucket] = current.next;
} else {
previous.next = current.next;
}
size—;
return current.value;
}
previous = current;
current = current.next;
}
return null;
}

public int size() {
return size;
}

@SuppressWarnings("unchecked")
private void resize() {
Node<K, V>[] oldTable = table;
Node<K, V>[] newTable = (Node<K, V>[]) new Node[oldTable.length << 1];

for (Node<K, V> head : oldTable) {
Node<K, V> current = head;
while (current != null) {
Node<K, V> next = current.next;
int bucket = index(current.hash, newTable.length);
current.next = newTable[bucket];
newTable[bucket] = current;
current = next;
}
}

table = newTable;
threshold = (int) (newTable.length * LOAD_FACTOR);
}

private static int spread(int hash) {
return hash ^ (hash >>> 16);
}

private static int index(int hash, int capacity) {
return hash & (capacity – 1);
}

private static final class Node<K, V> {
private final int hash;
private final K key;
private V value;
private Node<K, V> next;

private Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
}

这段代码有几个容易忽略的细节：

• 比较键时先比较缓存的哈希值，再调用 equals，可以减少昂贵的对象比较；
• 新节点采用头插法，插入单桶链表是 O(1)；
• 迁移节点前先保存 next，否则修改链表指针后会丢失旧链的剩余部分；
• 容量始终是 2 的幂，因此可以用 hash & (capacity – 1) 定位桶；
• null 返回值无法区分“键不存在”和“键对应的值为 null”，生产级 API 还需要 containsKey。

6. equals 与 hashCode 契约

对任意两个对象 a 和 b，Java 的核心约束是：

如果 a.equals(b) 为 true，那么 a.hashCode() 必须等于 b.hashCode()。

反过来不成立：哈希值相同的对象不一定相等。哈希表先用哈希值缩小范围，最终仍靠 equals 确认键是否相同。

public record UserKey(long tenantId, long userId) {
// record 会基于所有组件生成一致的 equals 和 hashCode
}

最危险的错误是把可变对象作为键，并在插入后修改参与哈希计算的字段：

Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey(1001);
map.put(key, "order");

key.setId(2002); // hashCode 发生变化
String value = map.get(key); // 可能查不到原来的条目

节点还在原来的桶中，但查询会根据新哈希值访问另一个桶，形成逻辑上的“失联数据”。键应优先使用不可变类型；若业务对象会变化，应提取不可变标识作为键。

7. 复杂度为什么是“平均 O(1)”

设表中有 n 个元素、m 个桶，负载因子为 α = n / m。哈希分布近似均匀时，链地址法单桶平均包含 α 个元素。若扩容策略让 α 保持在常数范围，查询平均成本就是常数级。

哈希表不保证按键排序，也不擅长范围查询。以下需求应考虑其他结构：

• 需要按键有序遍历或查询区间：平衡搜索树；
• 需要前缀匹配：Trie 或基数树；
• 需要按优先级反复取最值：堆；
• 需要磁盘上的大规模索引：B+ 树或 LSM Tree；
• 只需判断可能存在并允许少量误判：布隆过滤器。

8. 安全与并发中的隐藏问题

8.1 哈希洪泛攻击

如果攻击者能构造大量碰撞键，普通链地址哈希表可能从 O(1) 退化为 O(n)，大量请求会消耗 CPU。常见缓解方式包括：

• 为字符串哈希引入进程级随机种子；
• 限制请求参数数量和大小；
• 桶过长时树化；
• 对不可信输入采用具备抗碰撞设计的哈希函数。

8.2 普通哈希表不是线程安全容器

并发写入不仅可能覆盖数据，还可能让读线程观察到不一致的结构状态。不要尝试仅在外层“偶尔加锁”修补普通 HashMap。Java 中有并发读写需求时，应根据操作语义使用 ConcurrentHashMap，并优先使用它提供的原子组合操作：

counts.merge(word, 1L, Long::sum);
cache.computeIfAbsent(key, this::loadValue);

即使容器线程安全，“先检查再执行”的跨调用逻辑仍可能发生竞态。所需操作必须整体具备原子性，或者在更高层建立同步边界。

9. 工程排查清单

当哈希表出现内存过高、延迟抖动或数据异常时，可以按以下顺序检查：

#mermaid-svg-AB41YaUzPeZVzJ6o{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-AB41YaUzPeZVzJ6o .error-icon{fill:#552222;}#mermaid-svg-AB41YaUzPeZVzJ6o .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-AB41YaUzPeZVzJ6o .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-AB41YaUzPeZVzJ6o .marker{fill:#333333;stroke:#333333;}#mermaid-svg-AB41YaUzPeZVzJ6o .marker.cross{stroke:#333333;}#mermaid-svg-AB41YaUzPeZVzJ6o svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-AB41YaUzPeZVzJ6o p{margin:0;}#mermaid-svg-AB41YaUzPeZVzJ6o .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o .cluster-label text{fill:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o .cluster-label span{color:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o .cluster-label span p{background-color:transparent;}#mermaid-svg-AB41YaUzPeZVzJ6o .label text,#mermaid-svg-AB41YaUzPeZVzJ6o span{fill:#333;color:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o .node rect,#mermaid-svg-AB41YaUzPeZVzJ6o .node circle,#mermaid-svg-AB41YaUzPeZVzJ6o .node ellipse,#mermaid-svg-AB41YaUzPeZVzJ6o .node polygon,#mermaid-svg-AB41YaUzPeZVzJ6o .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-AB41YaUzPeZVzJ6o .rough-node .label text,#mermaid-svg-AB41YaUzPeZVzJ6o .node .label text,#mermaid-svg-AB41YaUzPeZVzJ6o .image-shape .label,#mermaid-svg-AB41YaUzPeZVzJ6o .icon-shape .label{text-anchor:middle;}#mermaid-svg-AB41YaUzPeZVzJ6o .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-AB41YaUzPeZVzJ6o .rough-node .label,#mermaid-svg-AB41YaUzPeZVzJ6o .node .label,#mermaid-svg-AB41YaUzPeZVzJ6o .image-shape .label,#mermaid-svg-AB41YaUzPeZVzJ6o .icon-shape .label{text-align:center;}#mermaid-svg-AB41YaUzPeZVzJ6o .node.clickable{cursor:pointer;}#mermaid-svg-AB41YaUzPeZVzJ6o .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-AB41YaUzPeZVzJ6o .arrowheadPath{fill:#333333;}#mermaid-svg-AB41YaUzPeZVzJ6o .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-AB41YaUzPeZVzJ6o .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-AB41YaUzPeZVzJ6o .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-AB41YaUzPeZVzJ6o .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-AB41YaUzPeZVzJ6o .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-AB41YaUzPeZVzJ6o .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-AB41YaUzPeZVzJ6o .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-AB41YaUzPeZVzJ6o .cluster text{fill:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o .cluster span{color:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-AB41YaUzPeZVzJ6o .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-AB41YaUzPeZVzJ6o rect.text{fill:none;stroke-width:0;}#mermaid-svg-AB41YaUzPeZVzJ6o .icon-shape,#mermaid-svg-AB41YaUzPeZVzJ6o .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-AB41YaUzPeZVzJ6o .icon-shape p,#mermaid-svg-AB41YaUzPeZVzJ6o .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-AB41YaUzPeZVzJ6o .icon-shape .label rect,#mermaid-svg-AB41YaUzPeZVzJ6o .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-AB41YaUzPeZVzJ6o .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-AB41YaUzPeZVzJ6o .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-AB41YaUzPeZVzJ6o :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

是

否

哈希表问题

键和值数量是否异常?

检查生命周期、淘汰策略和内存泄漏

是否频繁扩容?

预估初始容量并检查批量写入

桶分布是否偏斜?

审查 hashCode、键模式和恶意输入

是否存在并发访问?

核对容器类型与复合操作原子性

分析键值对象大小和 GC 压力

重点关注以下指标：元素数量、容量、负载因子、最大桶长度、扩容次数、对象分配率和 GC 停顿。只看平均查询耗时，往往会掩盖少数超长桶或扩容造成的尾延迟。

10. 总结

哈希表的高性能来自“散列定位 + 有界冲突”的组合，而不是魔法般的绝对 O(1)。哈希函数决定分布，冲突策略决定同桶元素如何组织，负载因子和扩容策略决定时间与空间的平衡，键的不可变性则保证逻辑正确。

在工程中使用哈希表时，记住四条原则：为预期规模设置合理容量；让相等对象拥有相同哈希值；不要修改键中参与哈希的字段；面对并发和不可信输入时使用专门的容器与防护机制。做到这些，哈希表才会从“能用”变成稳定、可预测的基础设施。