哈希表通过散列函数将键映射到存储位置，当不同键映射到同一位置时会产生散列冲突，二次探测法是解决这类冲突的经典开放寻址方案，核心目标是减少冲突带来的变量聚集问题，提升检索效率。
二次探测法的基本原理
二次探测法属于开放寻址法的分支，当发生散列冲突时，不会像线性探测那样依次向后查找空位置，而是按照二次方的步长跳跃查找。假设初始散列位置为h(k)，发生冲突时的探测序列为：
h(k, i) = (h'(k) + c1*i + c2*i²) mod m
其中h'(k)是初始散列函数，i是探测次数（从0开始），c1和c2是常数，m是哈希表的大小。通常为了简化实现，会取c1=0，c2=1，此时探测序列变为：
h(k, i) = (h'(k) + i²) mod m
二次探测法减少变量聚集的机制
线性探测法发生连续冲突时，会产生连续的被占用位置，形成变量聚集区域，后续插入的键如果散列到该区域附近，会进一步拉长聚集区域，导致检索时需要遍历更多位置。而二次探测法的步长随探测次数平方增长，会跳过连续的位置，避免形成连续的聚集区域，让冲突的键分散到哈希表的不同位置，从而减少检索时的遍历长度。
需要注意的是，二次探测法要求哈希表的大小m为质数，且负载因子不超过0.5，才能保证所有位置都能被探测到，避免无法插入新键的问题。
二次探测法的实战实现
下面以Python为例实现基于二次探测法的哈希表，包含插入、查找、删除三个核心操作：
class QuadraticProbingHashTable:
def __init__(self, size=11):
# 初始化哈希表，size取质数
self.size = size
self.keys = [None] * self.size
self.values = [None] * self.size
self.DELETED = object() # 标记已删除的位置
def _hash(self, key):
# 初始散列函数，计算键的哈希值
return hash(key) % self.size
def _probe(self, index, i):
# 二次探测计算下一个位置
return (index + i * i) % self.size
def insert(self, key, value):
# 插入键值对，负载因子超过0.5则扩容
load_factor = sum(1 for k in self.keys if k is not None and k is not self.DELETED) / self.size
if load_factor > 0.5:
self._resize()
index = self._hash(key)
i = 0
first_deleted = None
while self.keys[index] is not None:
if self.keys[index] == key:
# 键已存在，更新值
self.values[index] = value
return
if self.keys[index] is self.DELETED and first_deleted is None:
first_deleted = index
i += 1
index = self._probe(self._hash(key), i)
if i >= self.size:
# 探测完所有位置仍未找到空位，扩容后重新插入
self._resize()
return self.insert(key, value)
# 优先插入到之前删除的位置
if first_deleted is not None:
index = first_deleted
self.keys[index] = key
self.values[index] = value
def get(self, key, default=None):
# 查找键对应的值
index = self._hash(key)
i = 0
while self.keys[index] is not None:
if self.keys[index] == key:
return self.values[index]
i += 1
index = self._probe(self._hash(key), i)
if i >= self.size:
break
return default
def delete(self, key):
# 删除键值对，标记为已删除
index = self._hash(key)
i = 0
while self.keys[index] is not None:
if self.keys[index] == key:
self.keys[index] = self.DELETED
self.values[index] = None
return True
i += 1
index = self._probe(self._hash(key), i)
if i >= self.size:
break
return False
def _resize(self):
# 扩容哈希表，大小取下一个质数
old_keys = self.keys
old_values = self.values
self.size = self._next_prime(self.size * 2)
self.keys = [None] * self.size
self.values = [None] * self.size
for i in range(len(old_keys)):
if old_keys[i] is not None and old_keys[i] is not self.DELETED:
self.insert(old_keys[i], old_values[i])
def _next_prime(self, n):
# 查找大于等于n的质数
while True:
if self._is_prime(n):
return n
n += 1
def _is_prime(self, n):
# 判断是否为质数
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# 测试代码
if __name__ == "__main__":
ht = QuadraticProbingHashTable()
# 插入测试数据
test_data = [("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5)]
for k, v in test_data:
ht.insert(k, v)
# 查找测试
print(ht.get("c")) # 输出3
# 删除测试
ht.delete("c")
print(ht.get("c")) # 输出None
二次探测法与其他冲突解决方法的对比
常见的散列冲突解决方法还有线性探测法、链地址法，三者的特性对比如下：
| 方法 | 变量聚集情况 | 检索效率 | 空间开销 | 适用场景 |
|---|---|---|---|---|
| 线性探测法 | 严重，易形成连续聚集 | 负载因子高时下降明显 | 低，仅存储键值对 | 负载因子低、数据量小的场景 |
| 二次探测法 | 较轻，键分布更分散 | 负载因子不超过0.5时稳定 | 低，仅存储键值对 | 需要控制空间开销、负载因子可控的场景 |
| 链地址法 | 无变量聚集问题 | 负载因子高时仍保持稳定 | 高，需要额外存储链表指针 | 负载因子高、数据量大的场景 |
二次探测法的注意事项
- 哈希表大小必须选择质数，否则可能出现探测序列无法覆盖所有位置的问题，导致插入失败。
- 负载因子建议控制在0.5以内，超过该阈值后冲突概率会大幅上升，需要触发扩容操作。
- 删除操作不能直接将位置置为None，否则会中断后续的探测序列，需要使用专门的删除标记。
- 如果业务场景中存在大量冲突键，二次探测法的性能可能不如链地址法，需要根据实际数据特征选择方案。