哈希表的高级优化技术
·
一、动态扩容（解决负载因子过高导致的冲突激增）
为什么需要？
哈希表的数组大小固定时，随着元素增多，「负载因子」（已用槽位 / 总槽位）会变大，冲突概率急剧上升（链表变长或探测链变长），导致操作效率从 O (1) 退化到 O (n)。
动态扩容就是通过扩大数组容量，降低负载因子，保证效率稳定。
核心思路：
- 设定负载因子阈值（如 0.75）：当元素数量 ÷ 数组长度 > 阈值时触发扩容。
- 扩容策略：通常将数组长度扩大为原来的 2 倍（便于哈希值重新计算，利用位运算优化）。
- 重新哈希：扩容后，所有原有元素需要重新通过哈希函数计算新位置，放入新数组中（这个过程叫「rehash」）。
简单代码实现（Python 风格）：
class SimpleHashMap:
def __init__(self):
self.size = 4 # 初始数组大小（2的幂，便于扩容）
self.slots = [[] for _ in range(self.size)] # 链地址法：每个槽位是链表
self.count = 0 # 当前元素数量
self.load_factor_threshold = 0.75 # 负载因子阈值
def hash_func(self, key):
# 简单哈希函数：取模（实际会更复杂，如扰动函数）
return key % self.size
def resize(self):
"""扩容：数组大小翻倍，重新哈希所有元素"""
old_slots = self.slots
self.size *= 2 # 2倍扩容
self.slots = [[] for _ in range(self.size)] # 新数组
self.count = 0 # 重置计数，重新添加
# 重新哈希所有旧元素到新数组
for slot in old_slots:
for key, value in slot:
self.put(key, value) # 复用put方法
def put(self, key, value):
# 检查是否需要扩容
if self.count / self.size > self.load_factor_threshold:
print(f"负载因子过高（{self.count/self.size}），触发扩容到{self.size*2}")
self.resize()
# 计算哈希位置，插入元素（链地址法）
index = self.hash_func(key)
# 先检查是否已有该key，有则更新
for i, (k, v) in enumerate(self.slots[index]):
if k == key:
self.slots[index][i] = (key, value)
return
# 无则新增
self.slots[index].append((key, value))
self.count += 1
def get(self, key):
index = self.hash_func(key)
for k, v in self.slots[index]:
if k == key:
return v
return None # 未找到
代码理解：
size是数组长度，初始为 4，扩容时翻倍（4→8→16...）。put方法中，先判断负载因子（count/size）是否超过 0.75，超过则调用resize。resize是核心：创建新数组，将旧数组中的所有元素重新计算哈希位置，放入新数组（解决旧数组拥挤问题）。- 效果：通过降低负载因子，保证每个链表的平均长度较短，查找 / 插入效率维持在 O (1) 附近。
这么多东西我怕大家理解不了，所有接下来我们逐步来理解这个代码。
（一）初始结构（空哈希表）
代码初始化时的结构如下：
size = 4（数组长度为4）
slots = [ [], [], [], [] ] # 4个空链表（槽位）
count = 0（元素数量为0）
load_factor_threshold = 0.75（负载因子阈值）
图示：
索引: 0 → []
索引: 1 → []
索引: 2 → []
索引: 3 → []
（二）插入元素过程（put 方法）
我们通过插入几个元素来演示整个过程：
1. 插入 (key=10, value="A")
- 计算哈希值：
hash_func(10) = 10 % 4 = 2→ 对应索引 2 - 索引 2 的链表为空，直接添加 →
slots[2] = [(10, "A")] count变为 1
图示：
索引: 0 → []
索引: 1 → []
索引: 2 → [(10, "A")] ← 新增元素
索引: 3 → []
2. 插入 (key=18, value="B")
- 计算哈希值：
18 % 4 = 2→ 同样对应索引 2（发生冲突） - 索引 2 的链表已有元素，直接追加到链表 →
slots[2] = [(10, "A"), (18, "B")] count变为 2
图示：
索引: 0 → []
索引: 1 → []
索引: 2 → [(10, "A"), (18, "B")] ← 冲突元素追加到链表
索引: 3 → []
3. 插入 (key=5, value="C")
- 计算哈希值：
5 % 4 = 1→ 对应索引 1 - 索引 1 的链表为空，直接添加 →
slots[1] = [(5, "C")] count变为 3
此时负载因子 = 3/4 = 0.75（等于阈值，暂不扩容）
图示
索引: 0 → []
索引: 1 → [(5, "C")] ← 新增元素
索引: 2 → [(10, "A"), (18, "B")]
索引: 3 → []
4. 插入 (key=22, value="D") → 触发扩容
- 当前
count=3，size=4，插入前检查负载因子：3/4 = 0.75（等于阈值） - 插入后
count会变为 4，负载因子 = 4/4=1.0 > 0.75 → 触发扩容 - 扩容过程：
size变为 8（4×2）- 创建新的
slots数组（8 个空链表） - 重新哈希所有旧元素到新数组：
- (10, "A") → 10 % 8 = 2 → 新索引 2
- (18, "B") → 18 % 8 = 2 → 新索引 2（仍冲突）
- (5, "C") → 5 % 8 = 5 → 新索引 5
图示（扩容后）：
新size=8
索引: 0 → []
索引: 1 → []
索引: 2 → [(10, "A"), (18, "B")] ← 重新哈希后的元素
索引: 3 → []
索引: 4 → []
索引: 5 → [(5, "C")] ← 重新哈希后的元素
索引: 6 → []
索引: 7 → []
- 最后插入新元素 (22, "D")：
- 22 % 8 = 6 → 新索引 6 →
slots[6] = [(22, "D")] count变为 4
- 22 % 8 = 6 → 新索引 6 →
最终图示：
索引: 0 → []
索引: 1 → []
索引: 2 → [(10, "A"), (18, "B")]
索引: 3 → []
索引: 4 → []
索引: 5 → [(5, "C")]
索引: 6 → [(22, "D")] ← 新增元素
索引: 7 → []
（三）查找元素过程（get 方法）
查找 key=18 的过程：
- 计算哈希值：
18 % 8 = 2→ 定位到索引 2 - 遍历索引 2 的链表：
[(10, "A"), (18, "B")] - 找到 key=18，返回对应值 "B"
（四）核心逻辑总结
- 哈希表结构：数组（
slots）+ 链表（每个槽位的冲突元素） - 插入流程：
- 计算 key 的哈希值 → 定位到数组索引
- 若索引处已有该 key，更新值；否则添加到链表
- 检查负载因子，超过阈值则扩容（数组翻倍 + 重新哈希）
- 扩容目的：通过增大数组容量降低负载因子，避免链表过长导致效率下降
二、红黑树优化（解决链表过长导致的效率退化）
为什么需要？
链地址法中，如果哈希函数设计不好（或遭遇恶意攻击，如故意传入大量哈希冲突的 key），某个槽位的链表可能变得极长（比如长度 1000），此时查找效率会从 O (1) 退化到 O (n)。
红黑树优化：当链表长度超过阈值时，将链表转为「红黑树」（一种平衡二叉树），使查找 / 插入效率提升到 O (log n)。
核心思路：
- 阈值设定：链表长度≤8 时用链表（插入快），>8 时转为红黑树（查找快）。
- 退化机制：当红黑树节点数减少到 6 时，转回链表（红黑树维护成本高，节点少的时候链表更高效）。
- 红黑树优势：平衡二叉树，左右子树高度差不超过 1，保证查询、插入、删除都是 O (log n)。
10 （根节点）
/ \
5 15 （第二层：左右子树高度均为2）
/ \ /
3 7 12 （第三层：左右子树高度差≤1）
/
1 （第四层：左子树高度为1，右子树为空，高度差1）
树的高度指的是从某个节点到其最深叶子节点的最长路径上的边数（也有定义为节点数，需根据具体场景区分，通常算法中以 “边数” 为准）。
- 叶子节点的高度：叶子节点没有子节点，所以高度为 0。
- 根节点的高度：整棵树的高度，即从根到最深叶子的最长路径边数。
A （高度2）
/ \
B C（高度1）
/
D （高度0）
- 节点 D 是叶子，高度 = 0；
- 节点 B 的子节点是 D（高度 0），所以 B 的高度 = 0+1=1；
- 节点 C 没有子节点（或只有空节点），高度 = 0；
- 根节点 A 的子节点 B（高度 1）和 C（高度 0），最长路径是 A→B→D，边数为 2，所以 A 的高度 = 2。
在平衡二叉树中，高度差指的是一个节点的左子树高度与右子树高度的差值（通常定义为 “左高 - 右高”）。
平衡二叉树的核心要求是：所有节点的高度差的绝对值 ≤ 1。
A （高度2）
/ \
B C（高度1）
/
D （高度0）
- 节点 B 的左子树是 D（高度 0），右子树为空（高度 - 1，空树高度通常记为 - 1），高度差 = 0 - (-1)=1；
- 节点 C 的左、右子树都为空，高度差 =(-1) - (-1)=0；
- 根节点 A 的左子树 B（高度 1），右子树 C（高度 0），高度差 = 1 - 0=1；
此时所有节点的高度差绝对值都≤1，这棵树是平衡的。
如果某棵树出现节点高度差绝对值＞1，就需要通过旋转（如 AVL 树的左旋、右旋）来调整结构，使其重新平衡。例如：
A （左子树高度2，右子树高度0，高度差=2 → 不平衡）
/
B （左子树高度1，右子树高度0，高度差=1）
/
C （左子树高度0，右子树高度0，高度差=0）
根节点 A 的高度差为 2，违反平衡条件，需要旋转调整。
简单代码示意（突出判断逻辑，简化红黑树实现）：
class SlotNode:
"""链表节点（同时可作为红黑树节点的基础）"""
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None # 链表指针
# 红黑树相关属性（简化）
self.left = None # 左子树
self.right = None # 右子树
self.color = "red" # 红黑树节点颜色
class HashMapWithTree:
def __init__(self):
self.size = 4
self.slots = [None for _ in range(self.size)] # 每个槽位：初始是None，后续是链表或红黑树
self.count = 0
self.tree_threshold = 8 # 链表转树的阈值
def hash_func(self, key):
return key % self.size
def put(self, key, value):
index = self.hash_func(key)
slot = self.slots[index]
# 情况1：槽位是空的，直接插入新节点（链表）
if slot is None:
self.slots[index] = SlotNode(key, value)
self.count += 1
return
# 情况2：槽位是链表或红黑树，先查找是否有key
# （简化：假设当前是链表，判断长度）
current = slot
length = 1
while current.next:
current = current.next
length += 1
# 检查是否需要转红黑树
if length >= self.tree_threshold:
print(f"链表长度{length}，转为红黑树")
# 实际中会调用链表转红黑树的方法（此处简化）
self.slots[index] = self.list_to_tree(slot)
# 插入新节点（链表逻辑，红黑树插入更复杂）
current.next = SlotNode(key, value)
self.count += 1
def list_to_tree(self, head):
"""简化：仅示意，实际红黑树构建需要平衡操作"""
# 这里只是返回一个标记为树的节点（真实实现需按红黑树规则插入所有节点）
print("链表转红黑树（实际会构建平衡树）")
return head # 实际返回红黑树根节点
代码理解：
- 核心是
put方法中的长度判断：当链表长度达到 8，触发list_to_tree转换。 - 红黑树的复杂在于「平衡维护」（插入后通过旋转和变色保证平衡），初学者无需深究细节，只需知道其作用是将长链表的 O (n) 操作优化为 O (log n)。
- 为什么是 8？Java 的 HashMap 源码中，这个值是基于「泊松分布」计算的：正常哈希下，链表长度超过 8 的概率极低（约千万分之一），只有恶意攻击或极差的哈希函数才会触发，此时转树能有效防御。
这么多东西我怕大家理解不了，所有接下来我们逐步来理解这个代码。
（一）初始结构（空哈希表）
self.size = 4 # 数组长度为4
self.slots = [None, None, None, None] # 4个槽位，初始为空
self.tree_threshold = 8 # 链表转红黑树的阈值
图示：
索引0: None
索引1: None
索引2: None
索引3: None
（二）插入元素过程（链表阶段）
当插入元素时，哈希表先用链表存储冲突元素，直到链表长度达到阈值。
1. 插入前 7 个冲突元素（链表长度 < 8）
假设插入的元素哈希值都为2（全部冲突到索引 2）：
- 插入 (10, A) → 索引 2:
10 → None（长度 1） - 插入 (18, B) → 索引 2:
10 → 18 → None（长度 2） - ...（继续插入 5 个元素）
- 插入第 7 个元素后 → 索引 2:
10 → 18 → 26 → ... → 第7个元素（长度 7）
图示（索引 2 的链表）：
10 → 18 → 26 → 34 → 42 → 50 → 58 （长度7，未达阈值8，仍为链表）
2. 插入第 8 个冲突元素（触发转红黑树）
插入第 8 个哈希值为 2 的元素（66, H）：
- 此时链表长度变为 8，达到
tree_threshold - 触发
list_to_tree方法，将链表转为红黑树
图示（索引 2 的结构变化）：
# 转换前（链表）：
10 → 18 → 26 → 34 → 42 → 50 → 58 → 66 （长度8）
# 转换后（红黑树，简化示意）：
34 (黑节点)
/ \
18 50 (红节点)
/ \ / \
10 26 42 58 (黑节点)
\
66 (红节点)
（三）核心逻辑图解
整个哈希表的结构变化如下：
- 未达阈值时（链表存储）：
索引0: None
索引1: None
索引2: [10 → 18 → 26 → ... → 58] （链表，长度7）
索引3: None
- 达到阈值后（红黑树存储）：
索引0: None
索引1: None
索引2: [红黑树结构] （原链表转换而来）
索引3: None
（四）为什么要这样设计？
- 链表优势：插入简单（只需修改指针），适合元素少的情况。
- 红黑树优势：当元素多（>8）时，查询 / 插入效率从链表的 O (n) 提升到 O (log n)。
- 阈值 8：基于概率统计，正常哈希下链表长度超过 8 的概率极低，只有哈希冲突严重时才触发转树，平衡了效率和实现复杂度。
三、布谷鸟哈希（解决开放寻址法的探测链过长问题）
为什么需要？
开放寻址法中，当负载因子较高时，探测链会很长（找一个空槽需要遍历多个位置），效率下降。
布谷鸟哈希：使用 2 个哈希函数和 2 个数组，通过「踢出 - 重新放置」的方式减少冲突，实现快速插入和查找。
核心思路：
- 两个哈希函数：
hash1(key)和hash2(key)，分别对应两个数组table1和table2。 - 插入规则：
- 先尝试将 key 放入
table1[hash1(key)]，如果为空则插入； - 若冲突，尝试放入
table2[hash2(key)]，如果为空则插入； - 若仍冲突，随机踢出其中一个位置的元素（比如
table1中的），将新 key 放入，然后把被踢出的元素重新用另一个哈希函数放置（重复此过程，直到找到空槽或触发扩容）。
- 先尝试将 key 放入
- 查找规则：只需检查
table1[hash1(key)]和table2[hash2(key)]两个位置，最多两次查找，效率 O (1)。
简单代码实现：
class CuckooHash:
def __init__(self, size=4):
self.size = size
self.table1 = [None] * size # 第一个表
self.table2 = [None] * size # 第二个表
self.max_attempts = 5 # 最大踢出次数，避免无限循环
def hash1(self, key):
return key % self.size
def hash2(self, key):
return (key // self.size) % self.size # 第二个哈希函数（简单示例）
def resize(self):
"""扩容：解决踢不出的情况"""
old_table1 = self.table1
old_table2 = self.table2
self.size *= 2
self.table1 = [None] * self.size
self.table2 = [None] * self.size
# 重新插入所有旧元素
for key in old_table1:
if key is not None:
self.put(key)
for key in old_table2:
if key is not None:
self.put(key)
def put(self, key):
# 先尝试插入table1
pos1 = self.hash1(key)
if self.table1[pos1] is None:
self.table1[pos1] = key
return
# 再尝试插入table2
pos2 = self.hash2(key)
if self.table2[pos2] is None:
self.table2[pos2] = key
return
# 冲突，开始踢元素（先踢table1的）
current_key = key
current_pos = pos1
current_table = self.table1 # 当前操作的表
for _ in range(self.max_attempts):
# 踢出当前位置的元素，放入新key
kicked_key = current_table[current_pos]
current_table[current_pos] = current_key
# 被踢出的元素用另一个哈希函数重新放置
if current_table is self.table1:
# 从table1被踢，用hash2尝试table2
new_pos = self.hash2(kicked_key)
new_table = self.table2
else:
# 从table2被踢，用hash1尝试table1
new_pos = self.hash1(kicked_key)
new_table = self.table1
# 检查新位置是否为空
if new_table[new_pos] is None:
new_table[new_pos] = kicked_key
return
# 仍冲突，继续踢
current_key = kicked_key
current_pos = new_pos
current_table = new_table
# 超过最大尝试次数，触发扩容
print("踢不出元素，触发扩容")
self.resize()
self.put(key) # 扩容后重新插入
def get(self, key):
# 只需查两个位置
if self.table1[self.hash1(key)] == key:
return True
if self.table2[self.hash2(key)] == key:
return True
return False # 不存在
代码理解：
- 核心是
put方法的「踢人逻辑」：当两个位置都冲突时，通过踢出已有元素并重新放置，避免开放寻址法的长探测链。 - 查找效率极高：无论数据量多少，最多检查两个位置，实现 O (1) 查找。
- 为什么需要
max_attempts？极端情况下可能出现两个元素互相踢对方（死循环），此时通过扩容解决。
这么多东西我怕大家理解不了，所有接下来我们逐步来理解这个代码。
（一）初始结构（两个空表）
代码初始化时，会创建两个大小相同的数组（哈希表）：
self.size = 4 # 初始大小为4
self.table1 = [None, None, None, None] # 第一个表
self.table2 = [None, None, None, None] # 第二个表
self.hash1(key) = key % 4 # 第一个哈希函数
self.hash2(key) = (key // 4) % 4 # 第二个哈希函数（简单示例）
图示（两个表初始状态）：
table1: [None, None, None, None] # 索引0-3
table2: [None, None, None, None] # 索引0-3
（二）插入元素过程（分情况演示）
我们通过插入几个 key，逐步看布谷鸟哈希如何处理插入和冲突。
1. 插入 key=10（无冲突）
- 计算两个哈希位置：
hash1(10) = 10 % 4 = 2→ table1[2]hash2(10) = (10//4) % 4 = 2 % 4 = 2→ table2[2]
- 先尝试插入 table1 [2]，发现为空，直接放入：
图示：
table1: [None, None, 10, None] # 10放在table1[2]
table2: [None, None, None, None]
2. 插入 key=20（无冲突）
- 计算两个哈希位置：
hash1(20) = 20 % 4 = 0→ table1[0]hash2(20) = (20//4) % 4 = 5 % 4 = 1→ table2[1]
- 先尝试插入 table1 [0]，为空，直接放入：
图示：
table1: [20, None, 10, None] # 20放在table1[0]
table2: [None, None, None, None]
3. 插入 key=6（冲突，首次踢人）
- 计算两个哈希位置：
hash1(6) = 6 % 4 = 2→ table1 [2]（已有 10，冲突）hash2(6) = (6//4) % 4 = 1 % 4 = 1→ table2 [1]（为空）
- 尝试 table2 [1]，为空，直接放入：
图示：
table1: [20, None, 10, None]
table2: [None, 6, None, None] # 6放在table2[1]
4. 插入 key=14（冲突，需要踢人）
- 计算两个哈希位置：
hash1(14) = 14 % 4 = 2→ table1 [2]（有 10，冲突）hash2(14) = (14//4) % 4 = 3 % 4 = 3→ table2 [3]（为空）
- 尝试 table2 [3]，为空，直接放入：
图示：
table1: [20, None, 10, None]
table2: [None, 6, None, 14] # 14放在table2[3]
5. 插入 key=2（冲突，多次踢人）
- 计算两个哈希位置：
hash1(2) = 2 % 4 = 2→ table1 [2]（有 10，冲突）hash2(2) = (2//4) % 4 = 0 % 4 = 0→ table2 [0]（为空）
- 尝试 table2 [0]，为空，直接放入：
图示：
table1: [20, None, 10, None]
table2: [2, 6, None, 14] # 2放在table2[0]
6. 插入 key=34（冲突，触发踢人循环）
- 计算两个哈希位置：
hash1(34) = 34 % 4 = 2→ table1 [2]（有 10，冲突）hash2(34) = (34//4) % 4 = 8 % 4 = 0→ table2 [0]（有 2，冲突）
- 两个位置都冲突，开始踢人：
- 先踢 table1 [2] 的 10，将 34 放入 table1 [2]；
- 被踢的 10 需要重新放置，用 hash2 计算位置：
hash2(10)=2→ table2 [2]（为空），放入 10。
图示（踢人后）：
table1: [20, None, 34, None] # 34踢走10，占据table1[2]
table2: [2, 6, 10, 14] # 被踢的10放入table2[2]
7. 插入 key=38（冲突，踢人失败触发扩容）
- 计算两个哈希位置：
hash1(38) = 38 % 4 = 2→ table1 [2]（有 34，冲突）hash2(38) = (38//4) % 4 = 9 % 4 = 1→ table2 [1]（有 6，冲突）
- 开始踢人：
- 踢 table1 [2] 的 34，放入 38；
- 34 用 hash2 计算位置：
hash2(34)=0→ table2 [0]（有 2，冲突），踢走 2； - 2 用 hash1 计算位置：
hash1(2)=2→ table1 [2]（有 38，冲突），踢走 38； - 38 用 hash2 计算位置：
hash2(38)=1→ table2 [1]（有 6，冲突），踢走 6； - 6 用 hash1 计算位置：
hash1(6)=2→ table1 [2]（有 38，冲突）... 循环超过max_attempts=5。
- 触发扩容：size 变为 8，重新插入所有元素。
（三）查找过程（get 方法）
查找任意 key 时，只需检查两个位置：
- 例：查找 key=10 → 检查
table1[hash1(10)=2]和table2[hash2(10)=2]，在 table2 [2] 找到，返回 True。 - 例：查找 key=99 → 检查
table1[99%8]和table2[(99//8)%8]，都没有，返回 False。
（四）核心逻辑总结
- 双表双哈希：用两个表和两个哈希函数，每个 key 有两个可能的位置。
- 踢人机制：冲突时踢走已有元素，被踢元素用另一个哈希函数重新找位置。
- 快速查找：最多检查两个位置，实现 O (1) 查找效率。
- 扩容保障：避免踢人循环，通过扩容降低冲突概率。
总结：初学者如何理解？
- 动态扩容：核心是「通过扩大容量降低冲突概率」，记住「负载因子 0.75」和「2 倍扩容 + rehash」这两个关键动作。
- 红黑树优化：核心是「长链表转平衡树，将 O (n) 优化为 O (log n)」，重点理解为什么需要（防攻击、提效），而非红黑树的具体实现。
- 布谷鸟哈希：核心是「双哈希 + 双表 + 踢人机制」，实现 O (1) 查找，适合对查询速度要求极高的场景。
更多推荐
21
0- 0
已为社区贡献4条内容
所有评论(0)