链地址法是哈希表中解决哈希冲突的常用方案，核心思路是当多个不同的键通过哈希函数计算得到相同的哈希地址时，将这些键对应的元素都存储在该地址对应的链表中，而不是像开放寻址法那样寻找其他空闲位置。这种方式不需要提前预留大量空闲空间，在处理冲突时逻辑相对简单，是很多编程语言哈希表实现的底层方案之一。
哈希冲突的产生原因
哈希表的核心是通过散列函数将任意长度的键转换为固定范围的哈希值，再映射到对应的存储桶中。但哈希值的取值范围通常远小于键的可能取值数量，因此必然会出现不同的键计算得到相同哈希值的情况，这就是哈希冲突。比如使用简单的取模哈希函数hash(key) = key % 10，键11和键21计算得到的哈希值都是1，就会产生冲突。
链地址法的核心原理
链地址法的实现结构可以拆分为两个部分：
- 一个固定大小的数组，数组的每个元素称为一个桶，用来存储对应哈希地址的链表头节点
- 每个桶对应一个链表，所有哈希值映射到该桶的键值对都会按顺序插入到这个链表中
当进行插入操作时，先计算键的哈希值找到对应的桶，再遍历桶对应的链表，如果键不存在就插入到链表末尾；查找操作时同样先定位桶，再遍历链表匹配键；删除操作则是定位桶后找到对应节点并移除。
链地址法的简单实现示例（Python）
以下是一个基础的链地址法哈希表实现，支持插入、查找、删除操作：
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
class ChainHashTable:
def __init__(self, capacity=10):
self.capacity = capacity
# 初始化桶数组，每个元素初始为None
self.buckets = [None for _ in range(capacity)]
def _hash(self, key):
# 简单取模哈希函数
return hash(key) % self.capacity
def put(self, key, value):
index = self._hash(key)
node = self.buckets[index]
# 如果桶为空，直接插入新节点
if node is None:
self.buckets[index] = Node(key, value)
return
# 遍历链表，找到相同key则更新值，否则插入到末尾
prev = None
while node:
if node.key == key:
node.value = value
return
prev = node
node = node.next
prev.next = Node(key, value)
def get(self, key):
index = self._hash(key)
node = self.buckets[index]
# 遍历链表查找key
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 is None:
# 要删除的是头节点
self.buckets[index] = node.next
else:
prev.next = node.next
return
prev = node
node = node.next
# 使用示例
ht = ChainHashTable(capacity=5)
ht.put("name", "张三")
ht.put("age", 20)
ht.put("name", "李四") # 更新已存在的key
print(ht.get("name")) # 输出 李四
print(ht.get("age")) # 输出 20
ht.remove("age")
print(ht.get("age")) # 输出 None
其他常见哈希冲突解决方式
除了链地址法，还有几种常用的哈希冲突解决思路：
- 开放寻址法：当发生冲突时，按照某种探测序列（如线性探测、二次探测、双重哈希）寻找下一个空闲的桶位置存储元素，不需要额外的链表结构，但负载因子较高时性能下降明显
- 再哈希法：准备多个不同的哈希函数，当第一个哈希函数发生冲突时，依次使用第二个、第三个哈希函数计算地址，直到找到空闲位置，缺点是增加了计算开销
- 建立公共溢出区：将哈希表分为基本表和溢出表两部分，所有发生冲突的元素都放入溢出表中，查找时先查基本表，找不到再查溢出表，适合冲突较少的场景
链地址法的优缺点
链地址法的优势比较明显：
- 实现逻辑简单，不需要复杂的探测逻辑
- 删除操作方便，只需要修改链表指针即可，不需要像开放寻址法那样处理删除标记
- 负载因子可以大于1，不需要频繁扩容，空间利用率更高
同时它也存在一些不足：
- 需要额外的指针空间存储链表节点，增加了一定的内存开销
- 如果哈希函数设计不合理，导致大量元素集中到同一个桶中，链表长度过长会退化为线性查找，性能下降
- 缓存局部性较差，链表节点在内存中不一定连续，访问时缓存命中率低于连续存储的结构
链地址法的适用场景
链地址法适合以下场景：
- 哈希表的键值对数量不确定，负载因子波动较大的情况
- 需要频繁进行插入、删除操作的场景
- 可以接受一定额外内存开销，追求实现简单、逻辑清晰的场景
很多主流编程语言的哈希表实现都采用了链地址法的变种，比如Java的HashMap在JDK1.8之后，当链表长度超过阈值时会将链表转换为红黑树，避免链表过长导致的性能问题，这也是链地址法的一种优化思路。