-
第10章 哈希表
第10章 哈希表
10.1 引言
在前面的章节中，我们学习了多种线性和树形数据结构：数组和链表支持顺序访问，但随机查找需遍历元素，时间复杂度为O(n)；二叉搜索树和堆通过有序性将查找优化至O(log n)，但依赖元素间的比较和树结构的动态维护。然而，在许多实际场景中，我们需要一种能直接通过“键”（Key）快速定位数据的结构——例如，根据“学号”查询学生信息、根据“单词”查询词典释义、根据“用户名”验证登录密码。这种“键-值（Key-Value）”映射的需求，催生了哈希表（Hash Table）这一高效数据结构。
哈希表的核心思想是：通过一个哈希函数（Hash Function） 将“键”转化为数组的索引（哈希地址），从而实现“键→地址→值”的直接访问。在理想情况下，哈希表的插入、查找和删除操作的时间复杂度均为O(1)，远超数组和树结构。这一特性使得哈希表成为数据库索引、缓存系统、集合与映射实现（如Python的dict和set）的底层核心技术。
本章将从哈希表的基本原理出发，详细讲解哈希函数的设计方法、哈希冲突的解决策略，通过Python实现一个可实用的哈希表，并结合工程案例展示其在实际问题中的应用，最终帮助读者建立“键值映射”的思维框架，理解哈希表“用空间换时间”的设计哲学。
10.2 哈希表的基本原理
10.2.1 哈希表的定义
定义10.1 哈希表（Hash Table）：一种通过哈希函数将“键”映射到存储地址，从而实现键值对（Key-Value Pair）高效存储与访问的数据结构。其核心组成包括：
键（Key）：用于唯一标识数据的索引（如“学号”“单词”），需支持哈希函数计算；
值（Value）：与键关联的具体数据（如“学生信息”“单词释义”）；
哈希函数（Hash Function）：将键映射为哈希地址的函数，记为hash(key) = index；
哈希地址（Hash Address）：哈希函数的输出，即键值对在底层数组中的存储索引；
哈希表底层数组（Table）：用于存储键值对的连续内存空间，数组大小通常记为m。
示例：在学生信息管理系统中，用“学号”作为键，“姓名+成绩”作为值。若哈希函数为hash(学号) = 学号 % 100（取学号后两位作为索引），则学号为“20230123”的学生，其哈希地址为20230123 % 100 = 23，信息将存储在数组下标为23的位置。
10.2.2 哈希函数：从键到地址的映射
哈希函数是哈希表的“灵魂”，其设计直接决定哈希表的性能。一个理想的哈希函数应满足以下三个条件：
1.计算简单：哈希函数本身的计算时间应尽可能短（如取模、移位等基本运算），避免成为性能瓶颈；
2.分布均匀：将不同的键映射到不同的哈希地址，最大限度减少冲突（理想情况下，每个键的哈希地址唯一）；
3.定义域适配：哈希地址需落在底层数组的索引范围内（即0 ≤ hash(key) < m，m为数组大小）。
常见哈希函数设计方法
-
直接定址法
原理：直接使用键或键的线性变换作为哈希地址，即hash(key) = a·key + b（a、b为常数）。
示例：某公司员工工号范围为1000~1099，存储员工信息时，可令hash(key) = key - 1000，哈希地址为0~99，直接映射到底层数组。
适用场景：键为整数且取值连续、范围不大的场景，可实现零冲突。 -
除留余数法
原理：用键除以一个整数m（称为“模”），取余数作为哈希地址，即hash(key) = key % m。
关键：m的选择对分布均匀性影响极大，通常取小于或等于数组大小的最大质数（质数的因子少，可减少冲突）。
字符串哈希的实现：若键为字符串（如“apple”），需先将其转化为整数，再应用除留余数法。常用方法是按字符ASCII码累加或多项式展开：
python
def str_hash(s: str, m: int) -> int:
"""将字符串s映射为[0, m-1]的哈希地址（多项式哈希）"""
hash_code = 0
for c in s:
# 31为常用质数，减少冲突（Java的String.hashCode()也用31）
hash_code = hash_code * 31 + ord(c)
return hash_code % m # 取模得到哈希地址
# 示例：计算"apple"的哈希地址（m=100）
print(str_hash("apple", 100)) # 输出：(0*31+97)*31+112)*31+112)*31+108)*31+101) % 100 → 假设结果为45
适用场景：键的取值范围大且不连续（如整数、字符串），是实际工程中最常用的哈希函数。
3. 数字分析法
原理：对键的各位数字进行分析，选择分布均匀的若干位作为哈希地址。
示例：某高校学生学号格式为“入学年份（4位）+学院代码（2位）+班级号（2位）+序号（2位）”（如2023050312）。若需存储某学院学生信息，可选择“班级号+序号”（后4位）作为哈希地址，因这4位在学院内分布均匀。
适用场景：键为数字且各位数字的分布特征已知（如身份证号、学号）。
4. 平方取中法
原理：将键平方后，取中间几位作为哈希地址。平方运算可使键的各位数字对结果产生均匀影响，减少冲突。
示例：键为1234，平方后为1522756，取中间3位“227”作为哈希地址。
适用场景：键的各位数字分布不均匀，需通过平方增强随机性。
10.2.3 哈希冲突：不可避免的“碰撞”
定义10.2 哈希冲突：不同的键通过哈希函数计算得到相同的哈希地址，即key1 ≠ key2但hash(key1) = hash(key2)。
冲突的必然性：根据“鸽巢原理”，若底层数组大小为m，插入n > m个键值对，则至少有两个键的哈希地址相同。因此，哈希冲突无法完全避免，需通过冲突解决机制处理。
10.3 哈希冲突的解决方法
哈希冲突的解决方法主要分为两大类：开放定址法（冲突时在数组内寻找新位置）和链地址法（冲突时在数组外通过链表存储）。
10.3.1 开放定址法：数组内寻址
基本思想：当hash(key)处发生冲突时，按照某种规则在数组中探测其他空位置（称为“探测序列”），将键值对存储在第一个找到的空位置。
-
线性探测（Linear Probing）
探测规则：若hash(key)冲突，则依次探测hash(key)+1, hash(key)+2, ..., m-1, 0, 1, ...，直到找到空位置或遍历完数组。
示例：数组大小m=10，哈希函数hash(key)=key%10，插入键值对(12, A)（地址2）、(22, B)（地址2冲突→探测3）、(32, C)（地址2冲突→探测3冲突→探测4），存储结构如下：
数组索引：0 1 2 3 4 5 6 7 8 9
存储内容：- - A B C - - - - -
（“-”表示空位置，A、B、C分别为键12、22、32的值）
优缺点：
优点：实现简单，数据存储在连续内存，缓存友好（CPU缓存命中率高）；
缺点：易产生“聚集现象”（冲突的键值对集中在某一区域，如上述地址2、3、4），导致后续插入/查找需多次探测，效率下降。 -
二次探测（Quadratic Probing）
探测规则：若hash(key)冲突，则探测hash(key)±1², hash(key)±2², hash(key)±3², ...（平方步长），避免线性探测的线性聚集。
示例：同上例，插入(32, C)时，地址2冲突→探测2+1²=3（冲突）→探测2-1²=1（空位置），存储结构如下：
数组索引：0 1 2 3 4 5 6 7 8 9
存储内容：- C A B - - - - - -
优缺点：
优点：缓解线性聚集，但可能产生“二次聚集”（不同键的探测序列重叠）；
缺点：无法保证一定找到空位置（除非数组大小为质数且装填因子α≤0.5）。 -
双重哈希（Double Hashing）
探测规则：使用两个哈希函数，hash1(key)计算初始地址，hash2(key)计算探测步长（步长>0且与数组大小互质），探测序列为hash1(key) + i·hash2(key) % m（i=1,2,...）。
示例：hash1(key)=key%10，hash2(key)=7-(key%7)（7为质数，步长与10互质），插入(32, C)：
hash1(32)=2，hash2(32)=7-(32%7)=7-4=3，探测序列为2+1×3=5（空位置），存储结构如下：
数组索引：0 1 2 3 4 5 6 7 8 9
存储内容：- - A B - C - - - -
优缺点：
优点：步长随键动态变化，几乎无聚集现象，冲突处理效果最优；
缺点：实现复杂，需设计两个哈希函数。
10.3.2 链地址法（拉链法）：数组+链表
基本思想：底层用数组（称为“桶”）存储链表的头节点，每个链表存储哈希地址相同的键值对（即冲突的键值对）。插入时，将键值对添加到对应链表；查找/删除时，遍历对应链表即可。
结构示例：数组大小m=10，哈希函数hash(key)=key%10，插入(12,A)、(22,B)、(32,C)后，存储结构如下：
数组索引0：[]
索引1：[]
索引2：[(12,A) → (22,B) → (32,C)] # 哈希地址为2的键值对组成链表
索引3：[]
...
插入/查找/删除步骤：
插入：计算index=hash(key)%m，将(key, value)添加到table[index]对应的链表头部（或尾部）；
查找：计算index，遍历table[index]的链表，比较键是否相等；
删除：计算index，遍历链表找到键值对并删除节点。
优缺点：
优点：
o无聚集现象（冲突的键值对独立存储在不同链表）；
o动态分配内存，数组大小无需预先确定（链表可动态增长）；
o删除操作简单（直接从链表中删除节点，无需移动其他元素）；
缺点：
o链表节点存储在不连续内存，缓存友好性差；
o若哈希函数分布不均，某一链表过长（如所有键哈希到同一桶），查找时间退化为O(n)。
工业界选择：链地址法因实现简单、冲突处理效果稳定，成为主流选择（如Python的dict、Java的HashMap底层均基于链地址法，且当链表长度超过阈值时转为红黑树，优化长链表的查找效率）。
10.4 哈希表的Python实现：基于链地址法
本节基于链地址法实现一个支持动态扩容的哈希表，包含put(key, value)（插入/更新）、get(key)（查找）、remove(key)（删除）核心操作。
10.4.1 基本结构设计
底层数组（table）：列表，每个元素是一个链表（用Python列表模拟），存储哈希地址相同的键值对；
哈希函数：采用除留余数法，对字符串键先计算哈希码（多项式哈希）再取模；
装填因子（α）：键值对数量n与数组容量m的比值（α = n/m），用于触发扩容/缩容（α>0.7时扩容，α<0.2时缩容，平衡空间与时间效率）；
扩容/缩容：当α超过阈值时，创建新数组（容量为原数组的2倍/0.5倍），重新哈希所有键值对并插入新数组。
10.4.2 完整代码实现
python
class HashTable:
def __init__(self, capacity: int = 16):
"""初始化哈希表，默认容量为16（2的幂，便于取模计算）"""
self.capacity = capacity # 底层数组容量
self.size = 0 # 键值对数量
self.table = [[] for _ in range(self.capacity)] # 数组+链表（桶）
def _hash(self, key) -> int:
"""计算键的哈希地址（支持整数和字符串键）"""
if isinstance(key, int):
# 整数键直接取模
return key % self.capacity
elif isinstance(key, str):
# 字符串键：多项式哈希计算哈希码，再取模
hash_code = 0
for c in key:
hash_code = hash_code * 31 + ord(c) # 31为质数，减少冲突
return hash_code % self.capacity
else:
raise TypeError("Key must be int or str")
def put(self, key, value) -> None:
"""插入或更新键值对：若key存在则更新value，否则插入新键值对"""
index = self._hash(key)
# 遍历链表，检查key是否已存在
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value) # 更新value
return
# key不存在，插入链表尾部
self.table[index].append((key, value))
self.size += 1
# 装填因子超过0.7，扩容为原容量的2倍
if self.size / self.capacity > 0.7:
self._resize(self.capacity * 2)
def get(self, key):
"""查找key对应的value，若不存在返回None"""
index = self._hash(key)
# 遍历链表查找key
for k, v in self.table[index]:
if k == key:
return v
return None
def remove(self, key):
"""删除key对应的键值对，若不存在返回None"""
index = self._hash(key)
# 遍历链表查找并删除key
for i, (k, v) in enumerate(self.table[index]):
if k == key:
del self.table[index][i]
self.size -= 1
# 装填因子小于0.2且容量>16，缩容为原容量的0.5倍（避免过小容量）
if self.size > 0 and self.size / self.capacity < 0.2 and self.capacity > 16:
self._resize(self.capacity // 2)
return v
return None
def _resize(self, new_capacity: int) -> None:
"""扩容/缩容：创建新数组，重新哈希所有键值对"""
old_table = self.table
self.capacity = new_capacity
self.table = [[] for _ in range(new_capacity)] # 初始化新数组
self.size = 0 # 重置size，后续put时重新计数
# 遍历旧表，将所有键值对插入新表
for bucket in old_table:
for key, value in bucket:
self.put(key, value) # 利用put的哈希和插入逻辑
def __str__(self) -> str:
"""打印哈希表内容（仅显示非空桶）"""
res = []
for i, bucket in enumerate(self.table):
if bucket:
res.append(f"桶{i}: {bucket}")
return "哈希表:
" + "
".join(res)
10.4.3 功能测试
python
# 创建哈希表
ht = HashTable()
# 插入键值对
ht.put("name", "Alice")
ht.put("age", 20)
ht.put("score", 95)
print("插入后哈希表：")
print(ht)
# 查找
print("
查找'age'：", ht.get("age")) # 输出：20
# 更新
ht.put("age", 21)
print("更新'age'后查找：", ht.get("age")) # 输出：21
# 删除
ht.remove("score")
print("
删除'score'后哈希表：")
print(ht)
输出结果（哈希地址因Python字符串哈希实现略有差异）：
插入后哈希表：
桶2: [('name', 'Alice')]
桶4: [('age', 20)]
桶7: [('score', 95)]
查找'age'： 20
更新'age'后查找： 21
删除'score'后哈希表：
桶2: [('name', 'Alice')]
桶4: [('age', 21)]
10.5 哈希表的性能分析
10.5.1 装填因子（Load Factor）
装填因子α定义为哈希表中键值对数量n与数组容量m的比值：
α=nm lpha = rac{n}{m} α=mn
α是影响哈希表性能的核心指标：
α越小（数组越空）：冲突概率低，链表/探测序列短，操作效率高（接近O(1)）；
α越大（数组越满）：冲突概率高，链表/探测序列长，操作效率低（接近O(n)）。
实际应用中，哈希表的装填因子通常控制在0.5~0.7（如Python的dict默认装填因子阈值为0.66，超过则扩容）。
10.5.2 时间复杂度
理想情况（无冲突）：插入、查找、删除均为O(1)；
平均情况（冲突均匀分布）：插入、查找、删除均为O(1)（与α相关的常数时间，如α=0.7时，平均查找链表长度约0.7，需0.7次比较）；
最坏情况（所有键哈希到同一位置）：插入、查找、删除均为O(n)（如链地址法中某一链表长度为n）。
10.5.3 空间复杂度
哈希表的空间复杂度为O(m)，其中m为数组容量。由于需要预留空间以降低冲突率（α<1），哈希表是一种“用空间换时间”的数据结构。
10.6 工程应用场景
10.6.1 字典与集合
哈希表是实现“键值对存储”的底层技术，几乎所有编程语言都内置了基于哈希表的字典和集合：
字典（如Python的dict、Java的HashMap）：存储键值对，支持O(1)时间的插入、查找、删除；
集合（如Python的set、Java的HashSet）：存储唯一键，值为占位符，本质是特殊的字典。
示例：用dict实现用户信息的快速查询：
python
users = {
"alice": {"age": 20, "email": "alice@example.com"},
"bob": {"age": 22, "email": "bob@example.com"}
}
print(users["alice"]["email"]) # 输出：alice@example.com（O(1)查找）
10.6.2 缓存系统（LRU Cache）
缓存（Cache）是一种存储高频访问数据的技术，用于减少对低速存储（如数据库）的访问次数。LRU（最近最少使用）缓存是最常用的缓存策略，其核心是“当缓存满时，删除最近最少使用的数据”。
LRU Cache通常通过“哈希表+双向链表”实现：
哈希表：key → 链表节点，实现O(1)时间定位节点；
双向链表：按访问时间排序节点，头部为最近使用，尾部为最少使用，实现O(1)时间插入/删除节点。
10.6.3 数据校验与加密
哈希函数可将任意长度的数据映射为固定长度的哈希值，用于数据校验和加密：
数据校验：文件传输时，发送方计算文件的哈希值（如MD5、SHA-256）并一同发送，接收方计算接收文件的哈希值，若与发送方一致，则文件未被篡改；
密码存储：用户密码不直接存储，而是存储其哈希值（如网站数据库存储用户密码的SHA-256哈希），登录时计算输入密码的哈希值并对比，避免密码泄露风险。
10.6.4 分布式系统：一致性哈希
分布式系统中，哈希表可用于负载均衡（如将用户请求分配到不同服务器）。一致性哈希通过将“服务器”和“请求”映射到同一个哈希环上，确保服务器增减时，只有少量请求需要重新分配，减少系统波动。
10.7 本章总结
哈希表的核心价值：通过哈希函数实现键到地址的直接映射，在平均情况下提供O(1)的插入、查找、删除操作，是“快速键值访问”场景的首选数据结构。
关键技术点：
o哈希函数：需满足计算简单、分布均匀，常用除留余数法；
o冲突解决：链地址法（数组+链表，工业界常用）和开放定址法（线性/二次/双重探测，理论研究多）；
o性能优化：通过控制装填因子（扩容/缩容）和优化哈希函数，维持O(1)的平均时间复杂度。
局限性：
o键无序存储，无法按键的顺序遍历（如需有序，需用TreeMap等基于BST的结构）；
o哈希函数对键的类型有限制（如Python的dict键必须是可哈希类型，即不可变类型）；
o最坏情况性能退化为O(n)，需通过良好的哈希函数设计和冲突处理缓解。
哈希表的学习关键在于理解“哈希函数设计”和“冲突解决机制”，以及如何在实际应用中权衡“时间”“空间”和“冲突率”，选择合适的哈希策略。
10.8 思考题
1.设计一个哈希函数，用于存储URL（如“https://www.example.com”），要求分布均匀且计算简单（提示：可结合字符串哈希和除留余数法）。
2.基于开放定址法（线性探测）实现一个哈希表，支持put(key, value)、get(key)、remove(key)操作（注意删除时需处理“墓碑”问题，避免查找中断）。
3.为什么Python的dict在链表长度超过8时会将链表转为红黑树？（提示：红黑树的查找时间为O(log n)，优化长链表的性能）。
4.对比哈希表和二叉搜索树（BST）的优缺点，分析在什么场景下选择哈希表，什么场景下选择BST。
5.实现一个简化版的LRU Cache，支持get(key)和put(key, value)操作，要求时间复杂度均为O(1)（提示：哈希表+双向链表）。
本站原创，转载请注明出处：https://www.xin3721.com/python3/python49298.html
