数据结构：哈希表(Hash)

概述

• 哈希表是一种 高效的键值对存储数据结构 ，它通过 哈希函数 将键映射到数组的特定位置（桶），从而实现 O(1) 时间复杂度的查找、插入和删除操作（平均情况）。
• 资料：https://pan.quark.cn/s/43d906ddfa1b

一、 哈希表 的核心思想

哈希表的核心是“ 空间换时间 ”，通过哈希函数建立键和存储位置的直接映射，避免像数组或链表那样的遍历操作。

简单来说：

1. 用一个数组（称为“桶数组”）存储数据；
2. 对每个键key，通过 哈希函数 计算出它在数组中的索引位置；
3. 直接将键值对存入该位置，或从该位置取出数据。

二、哈希表的关键组成

1. 哈希函数（ Hash Function）

哈希函数是哈希表的灵魂，它接收一个键key，返回一个整数（数组索引）。一个好的哈希函数需要满足：

• 确定性 ：相同的键必须映射到相同的索引；
• 均匀性 ：键的分布尽可能均匀，减少冲突；
• 高效性 ：计算速度快。

常见的哈希函数：

• 取模法 ：hash(key) = key % 数组大小（适用于整数键）；
• 乘法哈希 ：hash(key) = floor(数组大小 × (key × A - floor(key × A)))（A 是黄金比例常数）；
• 字符串哈希 ：将字符串的字符编码通过加权求和后取模，例如：
  hash(str) = (s[0] × 31^(n-1) + s[1] × 31^(n-2) + ... + s[n-1]) % 数组大小。

2. 冲突解决（Collision Resolution）

由于键的数量远大于数组大小，不同的键可能被哈希函数映射到同一个索引，这就是 哈希冲突 。必须通过策略解决冲突：

（1）链地址法（Separate Chaining）

• 原理 ：每个桶对应一个链表（或红黑树），冲突的键值对存入同一个桶的链表中；
• 操作 ：查找时先通过哈希函数定位桶，再遍历链表找到目标键；
• 优点 ：实现简单，适合频繁插入删除的场景；
• 缺点 ：链表遍历会增加时间复杂度（最坏情况 O(n)）。

（2）开放地址法（Open Addressing）

• 原理 ：冲突时，按某种规则在数组中寻找下一个空桶；
• 常见策略 ：
  • 线性探测 ：冲突时向后遍历(index + 1) % 数组大小，直到找到空桶；
  • 二次探测 ：冲突时按(index + i²) % 数组大小寻找空桶（i=1,2,3…）；
  • 双重哈希 ：用第二个哈希函数计算步长，避免聚集；
• 优点 ：无需额外存储指针，内存利用率高；
• 缺点 ：容易出现“聚集”（连续占用多个桶），删除操作复杂。

3. 负载因子（Load Factor）

负载因子 = 哈希表中元素数量 / 桶数组大小。它决定了哈希表的扩容时机：

• 负载因子过大会导致冲突概率剧增，性能下降；
• 负载因子过小会浪费内存；
• 通常当负载因子超过阈值（如 0.75）时，哈希表会 扩容 （桶数组大小翻倍），并重新哈希所有元素。

三、哈希表的基本操作

以链地址法为例，哈希表的核心操作实现逻辑：

1. 插入（Put）

1. 计算键key的哈希值，得到数组索引index；
2. 若该桶为空，直接创建链表存入键值对；
3. 若该桶已有链表，遍历链表：
   • 若找到相同键，更新对应的值；
   • 若未找到，在链表尾部插入新节点。

2. 查找（Get）

1. 计算键key的哈希值，定位到桶index；
2. 遍历该桶的链表，找到对应键并返回值；
3. 若未找到，返回None或抛出异常。

3. 删除（Remove）

1. 定位到键对应的桶；
2. 遍历链表找到目标节点，删除并调整链表指针。

四、哈希表的实现（Python）

以下是基于链地址法的简易哈希表实现：

class HashNode:
"""哈希表节点（链表节点）"""
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None

class HashTable:
"""哈希表（链地址法）"""
def __init__(self, capacity=8):
self.capacity = capacity # 桶数组大小
self.size = 0 # 元素数量
self.buckets = [None] * self.capacity # 桶数组
self.load_factor_threshold = 0.75 # 负载因子阈值

def _hash(self, key):
"""哈希函数：计算键的索引"""
return hash(key) % self.capacity # 使用Python内置hash函数，再取模

def _resize(self):
"""扩容：桶数组大小翻倍，重新哈希所有元素"""
old_buckets = self.buckets
self.capacity *= 2
self.buckets = [None] * self.capacity
self.size = 0 # 重置size，重新插入时更新

# 遍历旧桶，重新插入所有元素
for bucket in old_buckets:
current = bucket
while current:
self.put(current.key, current.value)
current = current.next

def put(self, key, value):
"""插入键值对"""
# 检查是否需要扩容
if self.size / self.capacity >= self.load_factor_threshold:
self._resize()

index = self._hash(key)
node = self.buckets[index]

# 桶为空，直接插入
if not node:
self.buckets[index] = HashNode(key, value)
self.size += 1
return

# 桶不为空，遍历链表
prev = None
while node:
# 键已存在，更新值
if node.key == key:
node.value = value
return
prev = node
node = node.next

# 键不存在，插入链表尾部
prev.next = HashNode(key, value)
self.size += 1

def get(self, key):
"""查找键对应的值"""
index = self._hash(key)
node = self.buckets[index]

while node:
if node.key == key:
return node.value
node = node.next

return None # 键不存在

def remove(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 True # 删除成功
prev = node
node = node.next

return False # 键不存在

def __str__(self):
"""打印哈希表"""
result = []
for i in range(self.capacity):
bucket = []
node = self.buckets[i]
while node:
bucket.append(f"({node.key}: {node.value})")
node = node.next
if bucket:
result.append(f"桶{i}: {' -> '.join(bucket)}")
return "\n".join(result)

# 使用示例
ht = HashTable()
ht.put("apple", 5)
ht.put("banana", 3)
ht.put("cherry", 7)
ht.put("apple", 10) # 更新apple的值

print(ht.get("apple")) # 输出: 10
print(ht.remove("banana")) # 输出: True
print(ht)

五、哈希表的优缺点

优点

1. 高效的平均性能 ：插入、查找、删除的平均时间复杂度为 O(1)；
2. 灵活的键类型 ：支持多种类型的键（整数、字符串、对象等，只要可哈希）；
3. 易于实现 ：核心逻辑简单，工程上广泛应用。

缺点

1. 最坏情况性能差 ：若哈希函数设计不佳或负载因子过高，时间复杂度会退化为 O(n)；
2. 无序性 ：哈希表中的元素是无序存储的，无法直接按顺序遍历；
3. 内存开销 ：链地址法需要额外存储链表指针，开放地址法可能浪费桶空间；
4. 不可变键 ：键必须是不可变类型（如Python中的字符串、元组），否则哈希值会变化导致无法查找。

六、哈希表的应用场景

哈希表是工程中最常用的 数据结构 之一，典型场景包括：

1. 缓存系统 ：如Redis、Memcached的核心存储结构；
2. 数据库索引 ：数据库用哈希索引加速等值查询；
3. 集合/字典实现 ：Python的dict、Java的HashMap、C++的unordered_map均基于哈希表；
4. 字符串匹配 ：如布隆过滤器（基于哈希的快速判重）；
5. 计数统计 ：如统计字符出现次数、词频统计等；
6. 负载均衡 ：一致性哈希算法用于分布式系统的负载分配。

七、总结

哈希表是“时间效率”与“空间效率”的平衡产物，通过哈希函数和冲突解决策略，实现了近乎常数时间的增删改查操作。它是解决“快速查找”问题的首选数据结构，也是理解 分布式系统 、缓存机制的基础。实际开发中，直接使用语言内置的哈希表实现（如Python的dict）即可满足绝大多数需求，无需重复造轮子。