答案：C++中开放寻址法通过线性探测、二次探测和双重哈希在冲突时寻找空位，需标记删除状态并控制负载因子以维持性能。
在C++中实现开放寻址法（Open Addressing）解决哈希冲突，核心思路是当发生冲突时，在哈希表中寻找下一个可用的位置来存储数据，而不是使用链表等外部结构。常见的探测方式包括线性探测、二次探测和双重哈希。
1. 线性探测（Linear Probing）
线性探测是最简单的开放寻址策略：当哈希位置被占用时，依次检查下一个位置，直到找到空位。
关键点：
- 哈希函数：hash(key) % table_size
- 探测序列：(hash(key) + i) % table_size，其中 i 从 0 开始递增
- 删除操作需标记“已删除”状态，避免查找中断
示例代码：
立即学习“C++免费学习笔记（深入）”；
#include#include using namespace std; enum State { EMPTY, OCCUPIED, DELETED };
struct HashEntry { int key; int value; State state;
HashEntry() : key(0), value(0), state(EMPTY) {}};
class HashTable { private: vector
table; int size; int hash(int key) { return key % size; } int find_index(int key) { int index = hash(key); int i = 0; while (table[(index + i) % size].state != EMPTY && table[(index + i) % size].key != key) { i++; } return (index + i) % size; }public: HashTable(int s) : size(s) { table.resize(size); }
void insert(int key, int value) { int index = hash(key); int i = 0; while (table[(index + i) % size].state == OCCUPIED && table[(index + i) % size].key != key) { i++; } int pos = (index + i) % size; table[pos].key = key; table[pos].value = value; table[pos].state = OCCUPIED; } int search(int key) { int index = hash(key); int i = 0; while (table[(index + i) % size].state != EMPTY) { int pos = (index + i) % size; if (table[pos].state == OCCUPIED && table[pos].key == key) { return table[pos].value; } i++; } return -1; // not found } void remove(int key) { int index = find_index(key); if (table[index].state == OCCUPIED && table[index].key == key) { table[index].state = DELETED; } }};
2. 二次探测（Quadratic Probing）
为减少聚集现象，使用平方增量进行探测。
探测公式：(hash(key) + i²) % table_size
注意：表大小应为质数，且负载因子控制在较低水平，以确保能找到空位。
修改插入部分示例：
void insert(int key, int value) { int index = hash(key); int i = 0; while (i < size) { int pos = (index + i*i) % size; if (table[pos].state == EMPTY || table[pos].state == DELETED) { table[pos].key = key; table[pos].value = value; table[pos].state = OCCUPIED; return; } else if (table[pos].key == key && table[pos].state == OCCUPIED) { table[pos].value = value; // update return; } i++; } }3. 双重哈希（Double Hashing）
使用第二个哈希函数计算步长，进一步分散探测路径。
探测公式：(h1(key) + i * h2(key)) % table_size
常用设计：
h1(key) = key % size
h2(key) = prime - (key % prime)，prime 为略小于 size 的质数示例：
int hash2(int key) { int prime = 7; // 小于 size 的质数 return prime - (key % prime); }void insert(int key, int value) { int index1 = hash(key); int index2 = hash2(key); int i = 0; while (i < size) { int pos = (index1 + i * index2) % size; if (table[pos].state == EMPTY || table[pos].state == DELETED) { table[pos].key = key; table[pos].value = value; table[pos].state = OCCUPIED; return; } i++; } }注意事项与优化建议
开放寻址法虽然节省空间，但对负载因子敏感。一般当负载因子超过 0.7 时性能显著下降。
- 保持负载因子低，必要时扩容并重新哈希
- 选择合适的探测方法：线性简单但易聚集，双重哈希分布更均匀
- 删除操作不能真正清空，必须标记为 DELETED
- 表大小尽量用质数，尤其配合二次或双重哈希
基本上就这些。开放寻址法实现不复杂，但细节决定稳定性。
