C手动实现一个线性探测法HashMap
目录
C++手动实现一个线性探测法HashMap
1.HashMap原理
当散列函数计算出某个元素的插入位置，而该位置上的空间已不再可用时，最简单的办法就是循序往下一一寻找，直到找到一个可用空间为止，只要表格array足够大，总是能找到一个安身立命的空间，但是要花多少时间就很难说了。进行元素搜寻操作时，道理也相同，如果散列表计算出来的位置上的元素值与我们的搜寻目标不符，就循序往下一一寻找，直到找到吻合者或者直到遇上空格元素。
分析线性探测的表现，需要两个假设：一表格足够大，二每个元素都够独立。在此假设之下，最坏的情况是线性寻访整个表格，平均情况则是寻访一半表格。所以线性探测的一个突出问题是：平均插入成本的成长幅度，远高于负载系数的成长幅度，这样的现象在hashing过程中称为主集团primary clustering（此时我们手上有的是一大团已被用过的方格，插入操作极有可能在主集团所形成的泥泞中奋力爬行，不断解决碰撞问题）。
2.代码解析
模板类设计 ：
- 使用模板泛化键类型（
KeyType），支持整数、字符串等类型。 table存储键值，occupied标记槽位是否被占用。
- 使用模板泛化键类型（
核心方法 ：
hashFunction：计算键的哈希值（取绝对值的模运算）。insert：插入键值，冲突时线性探测下一个空闲槽位。search：从哈希位置开始顺序查找键值。remove：标记指定键的位置为空闲。
显示哈希表 ：
- 遍历所有槽位，输出键值或“空”
注意事项
负载因子 ：
- 最佳负载因子为
0.6~0.7，超过时建议扩容哈希表。 - 扩容可通过重新哈希（Rehashing）实现，将现有键重新插入到更大的表中。
- 最佳负载因子为
删除优化 ：
- 本实现使用标记删除法（
occupied数组），避免移动元素。 - 若需完全删除节点，需遍历后续槽位并前移元素，但会增加复杂度。
- 本实现使用标记删除法（
冲突解决 ：
- 线性探测的局限性在于可能导致聚集（Clustering），改用二次探测或双重哈希可缓解。
#include <iostream>
#include <vector>
#include <string>
#include <utility> // for std::pair
using namespace std;
template<typename KeyType, typename ValueType>
class HashTable {
private:
vector<pair<KeyType, ValueType>> table;
vector<bool> occupied; // 标记槽位是否被占用
int size;
// 哈希函数：简单取模
int hashFunction(const KeyType& key) const {
return abs(key) % size;
}
public:
// 构造函数，初始大小为质数（例如101）
HashTable(int size = 101) : size(size), table(size), occupied(size, false) {}
// 插入操作
void insert(const KeyType& key, const ValueType& value) {
int index = hashFunction(key);
while (occupied[index]) {
index = (index + 1) % size;
}
table[index] = pair<KeyType, ValueType>(key, value);
occupied[index] = true;
}
// 查找操作
bool search(const KeyType& key, ValueType& result) const {
int index = hashFunction(key);
while (occupied[index]) {
if (table[index].first == key) {
result = table[index].second;
return true;
}
index = (index + 1) % size;
}
return false;
}
// 删除操作
bool remove(const KeyType& key) {
int index = hashFunction(key);
while (occupied[index]) {
if (table[index].first == key) {
occupied[index] = false;
return true;
}
index = (index + 1) % size;
}
return false; // 未找到键
}
};
int main() {
// 定义哈希表类型：键为int，值为string
HashTable<int, string> ht(7); // 哈希表大小为7
// 插入测试数据
ht.insert(23, "Alice");
ht.insert(14, "Bob");
ht.insert(55, "Charlie");
ht.insert(31, "David");
ht.insert(77, "Eve");
ht.insert(89, "Frank");
ht.insert(10, "Grace"); // 哈希值为3 (10%7=3)，探测到索引3被占用，插入到4
// 查找测试
string result;
cout << endl << "查找键31对应的值:";
if (ht.search(31, result)) {
cout << result << endl;
} else {
cout << "未找到" << endl;
}
// 删除测试
ht.remove(77);
return 0;
}