哈希表通过哈希函数将键映射到存储位置，当两个不同的键映射到同一个位置时就会产生哈希冲突，开放寻址法是解决这类冲突的主流方案，核心思路是当目标位置被占用时，按照特定规则寻找下一个可用位置。线性探测和二次探测是开放寻址法中最常见的两种探测方式，二者的探测步长规则不同，适用场景也有差异。
开放寻址法基本原理
开放寻址法的哈希表所有数据都存储在数组本身中，不需要额外的链表结构。当插入键值对时，先计算初始哈希位置，如果该位置为空则直接插入；如果该位置已经被占用且键不匹配，就按照预设的探测序列依次检查后续位置，直到找到空位置或者匹配到相同键为止。删除操作不能直接将位置置空，否则会中断后续的探测链，通常需要标记为已删除状态。
线性探测逻辑解析
线性探测的探测步长是固定的1，探测序列为hash(key) + 1、hash(key) + 2、hash(key) + 3，当超过数组长度时回到数组开头循环。这种方式实现简单，但容易产生聚集现象，即连续的被占用位置会越来越长，导致后续插入和查找的效率下降。
以下是线性探测的C++实现示例，使用固定大小的数组存储键值对，支持插入、查找和删除操作：
#include <iostream>
#include <string>
using namespace std;
// 键值对结构体
struct HashNode {
int key;
string value;
bool isDeleted; // 标记是否被删除
HashNode() : key(-1), value(""), isDeleted(false) {}
};
class LinearProbingHashTable {
private:
static const int TABLE_SIZE = 10; // 哈希表大小
HashNode table[TABLE_SIZE];
// 哈希函数：简单取模
int hashFunc(int key) {
return key % TABLE_SIZE;
}
public:
// 插入键值对
void insert(int key, string value) {
int index = hashFunc(key);
int startIndex = index;
// 循环探测直到找到空位置或者已删除位置
while (table[index].key != -1 && !table[index].isDeleted) {
// 如果键已存在，更新值
if (table[index].key == key) {
table[index].value = value;
return;
}
index = (index + 1) % TABLE_SIZE;
// 避免无限循环，遍历完整个表还没找到位置则提示满
if (index == startIndex) {
cout << "哈希表已满，无法插入" << endl;
return;
}
}
// 插入新节点
table[index].key = key;
table[index].value = value;
table[index].isDeleted = false;
}
// 查找键对应的值
string search(int key) {
int index = hashFunc(key);
int startIndex = index;
while (table[index].key != -1 || table[index].isDeleted) {
if (!table[index].isDeleted && table[index].key == key) {
return table[index].value;
}
index = (index + 1) % TABLE_SIZE;
if (index == startIndex) {
break;
}
}
return "未找到对应键";
}
// 删除键
void remove(int key) {
int index = hashFunc(key);
int startIndex = index;
while (table[index].key != -1 || table[index].isDeleted) {
if (!table[index].isDeleted && table[index].key == key) {
table[index].isDeleted = true;
cout << "删除成功" << endl;
return;
}
index = (index + 1) % TABLE_SIZE;
if (index == startIndex) {
break;
}
}
cout << "未找到要删除的键" << endl;
}
// 打印哈希表
void printTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i].key == -1) {
cout << "位置" << i << ": 空" << endl;
} else if (table[i].isDeleted) {
cout << "位置" << i << ": 已删除" << endl;
} else {
cout << "位置" << i << ": 键=" << table[i].key << ", 值=" << table[i].value << endl;
}
}
}
};
int main() {
LinearProbingHashTable hashTable;
hashTable.insert(1, "张三");
hashTable.insert(11, "李四"); // 1%10=1，11%10=1，产生冲突，线性探测到位置2
hashTable.insert(2, "王五");
cout << "查找键11: " << hashTable.search(11) << endl;
hashTable.remove(11);
cout << "删除后查找键11: " << hashTable.search(11) << endl;
hashTable.printTable();
return 0;
}
二次探测逻辑解析
二次探测的探测步长是探测次数的二次函数，探测序列为hash(key) + 1²、hash(key) + 2²、hash(key) + 3²，同样超过数组长度时取模回到数组范围。这种方式可以减少线性探测的聚集现象，但可能会产生二次聚集，且要求哈希表的大小最好是质数，才能保证探测序列可以遍历所有位置。
以下是二次探测的C++实现示例，在线性探测的基础上修改探测逻辑：
#include <iostream>
#include <string>
using namespace std;
struct HashNode {
int key;
string value;
bool isDeleted;
HashNode() : key(-1), value(""), isDeleted(false) {}
};
class QuadraticProbingHashTable {
private:
static const int TABLE_SIZE = 11; // 使用质数作为表大小，避免探测死循环
HashNode table[TABLE_SIZE];
int hashFunc(int key) {
return key % TABLE_SIZE;
}
public:
void insert(int key, string value) {
int index = hashFunc(key);
int startIndex = index;
int i = 1; // 探测次数
while (table[index].key != -1 && !table[index].isDeleted) {
if (table[index].key == key) {
table[index].value = value;
return;
}
// 二次探测：index = (初始哈希 + i²) % 表大小
index = (startIndex + i * i) % TABLE_SIZE;
i++;
if (i >= TABLE_SIZE) {
cout << "哈希表已满，无法插入" << endl;
return;
}
}
table[index].key = key;
table[index].value = value;
table[index].isDeleted = false;
}
string search(int key) {
int index = hashFunc(key);
int startIndex = index;
int i = 1;
while (table[index].key != -1 || table[index].isDeleted) {
if (!table[index].isDeleted && table[index].key == key) {
return table[index].value;
}
index = (startIndex + i * i) % TABLE_SIZE;
i++;
if (i >= TABLE_SIZE) {
break;
}
}
return "未找到对应键";
}
void remove(int key) {
int index = hashFunc(key);
int startIndex = index;
int i = 1;
while (table[index].key != -1 || table[index].isDeleted) {
if (!table[index].isDeleted && table[index].key == key) {
table[index].isDeleted = true;
cout << "删除成功" << endl;
return;
}
index = (startIndex + i * i) % TABLE_SIZE;
i++;
if (i >= TABLE_SIZE) {
break;
}
}
cout << "未找到要删除的键" << endl;
}
void printTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i].key == -1) {
cout << "位置" << i << ": 空" << endl;
} else if (table[i].isDeleted) {
cout << "位置" << i << ": 已删除" << endl;
} else {
cout << "位置" << i << ": 键=" << table[i].key << ", 值=" << table[i].value << endl;
}
}
}
};
int main() {
QuadraticProbingHashTable hashTable;
hashTable.insert(1, "苹果");
hashTable.insert(12, "香蕉"); // 1%11=1，12%11=1，冲突，二次探测位置1+1=2
hashTable.insert(23, "橙子"); // 23%11=1，冲突，二次探测位置1+4=5
cout << "查找键23: " << hashTable.search(23) << endl;
hashTable.remove(12);
hashTable.printTable();
return 0;
}
两种探测方式对比
| 对比项 | 线性探测 | 二次探测 |
|---|---|---|
| 探测步长 | 固定1，依次递增 | 探测次数的二次函数 |
| 聚集现象 | 容易产生一次聚集，连续占用区域变长 | 减少一次聚集，但可能出现二次聚集 |
| 表大小要求 | 无特殊要求 | 建议为质数，保证探测序列覆盖所有位置 |
| 实现复杂度 | 简单，逻辑清晰 | 稍复杂，需要记录探测次数计算步长 |
| 适用场景 | 数据量小、冲突少的场景 | 数据量中等、需要减少聚集的场景 |
在实际开发中，选择线性探测还是二次探测需要根据数据量、冲突频率和性能要求来决定。如果哈希表负载因子较低，线性探测的实现成本更低；如果需要处理更多的哈希冲突，二次探测能提供更稳定的查找效率。