二次探测法

### 什么是二次探测法 二次探测法是一种用于解决哈希冲突的技术，当两个不同的键通过同一个哈希函数映射到相同的位置时发生冲突。为了缓解这一问题，二次探测法利用了一种特殊的探查序列来寻找下一个可用位置[^2]。 其核心思想是在遇到冲突时，按照一定的规律调整偏移量 \(d_i\) 来重新计算存储位置。具体的公式如下： \[ f(\text{key}) = (\text{hash}(\text{key}) + d_i) \mod m \] 其中： - \(m\) 是哈希表的大小， - \(d_i\) 的取值为平方数序列：\(1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2\) （这里 \(q \leq m / 2\)）。 这种方法能够有效减少线性聚集现象的发生概率，从而提高查找效率[^4]。 --- ### 如何实现二次探测法 以下是基于 Python 编程语言的一个简单示例代码，演示如何使用二次探测法构建并操作一个基本的哈希表： ```python class HashTable: def __init__(self, size): self.size = size self.table = [None] * size def hash_function(self, key): return key % self.size def insert(self, key): index = self.hash_function(key) if not self.table[index]: self.table[index] = key else: i = 1 while True: new_index = (index + i ** 2) % self.size if not self.table[new_index]: self.table[new_index] = key break i += 1 if i > self.size // 2: # 防止无限循环 raise Exception("Hash table is full or cannot resolve collision.") def search(self, key): index = self.hash_function(key) if self.table[index] == key: return index i = 1 while True: new_index = (index + i ** 2) % self.size if self.table[new_index] == key: return new_index if i >= self.size // 2: # 超过最大尝试次数则停止 return None i += 1 # 测试用例 ht = HashTable(7) keys_to_insert = [50, 700, 76, 85, 92, 73, 101] for k in keys_to_insert: ht.insert(k) print(ht.table) # 输出最终填充后的哈希表状态 ``` 上述程序定义了一个简单的 `HashTable` 类，并实现了插入和查询功能。如果某个键对应的初始槽位已被占用，则会依次尝试距离原槽位更远的位置（由平方增量决定），直到找到空闲空间为止。 --- ### §相关问题§ 1. 如果哈希表容量固定，在极端情况下可能会导致什么后果？ 2. 使用链地址法相比二次探测法有哪些优缺点？ 3. 当前最常用的几种哈希函数分别是什么类型的？它们各自的特点又是什么？ 4. 在实际应用中，为什么通常会选择开放寻址法而非拉链法作为默认解决方案之一？ 5. 对于大规模数据集而言，哪种策略更适合应对频繁发生的哈希碰撞情况？