1、使用哈希算法完成MyHash类,实现简单的哈希类。添加private属性之后,完善相应的public函数。 自选哈希函数,自选解决哈希碰撞的方法。 MyHash(int max_element); 构造函数,构造一个元素最多为max_element的哈希表。 ~MyHash(); 析构函数 void setvalue(int key, int value); 将哈希表中键值为key的元素设定值改为value。(哈希表中没有被setvalue的键值默认值为0) int getvalue(int key); 获得哈希表中键值为key的元素的对应value值 注意事项: 1、如果哈希表的最大元素为max_element,为了防止表中元素元素发生碰撞,则最好将表长设置为max_element的整数倍。 2、如果使用H(x) = x % mod作为哈希函数,mod设定为接近表长的质数可以有效防止碰撞
时间: 2024-02-03 17:14:19 浏览: 138
以下是使用哈希算法完成MyHash类的示例代码,使用线性探测法解决哈希碰撞:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class MyHash {
private:
int max_element; // 哈希表最大元素个数
int table_size; // 哈希表长度
vector<int> keys; // 存储键
vector<int> values; // 存储值
public:
MyHash(int max_element) {
this->max_element = max_element;
table_size = max_element * 2; // 表长设为最大元素个数的两倍
keys.resize(table_size, 0);
values.resize(table_size, 0);
}
~MyHash() {}
// 哈希函数,使用H(x) = x % mod
int hash_func(int key) {
return key % table_size;
}
void setvalue(int key, int value) {
int index = hash_func(key); // 计算哈希值
int i = 0;
while (keys[index] != 0 && keys[index] != key) { // 线性探测找到空槽或对应键
i++;
index = (index + i) % table_size; // 下一个槽位
}
keys[index] = key;
values[index] = value; // 存储键值对
}
int getvalue(int key) {
int index = hash_func(key); // 计算哈希值
int i = 0;
while (keys[index] != 0 && keys[index] != key) { // 线性探测找到对应键
i++;
index = (index + i) % table_size; // 下一个槽位
}
if (keys[index] == key) {
return values[index]; // 返回对应值
} else {
return 0; // 没有找到对应键,返回默认值0
}
}
};
int main() {
MyHash hash_table(10);
hash_table.setvalue(3, 10);
hash_table.setvalue(13, 5);
hash_table.setvalue(23, 2);
cout << hash_table.getvalue(3) << endl; // 输出10
cout << hash_table.getvalue(13) << endl; // 输出5
cout << hash_table.getvalue(23) << endl; // 输出2
cout << hash_table.getvalue(33) << endl; // 输出0,表示没有找到对应键
return 0;
}
```
在上述示例代码中,我们使用了哈希函数H(x) = x % mod,并且将表长设为最大元素个数的两倍。对于哈希碰撞,我们使用线性探测法解决,即当哈希槽位已经被占用时,我们就线性地向后探测,直到找到一个空槽位或者对应的键。在setvalue函数中,我们先计算键的哈希值,然后进行线性探测,直到找到空槽位或对应的键,然后在该槽位存储键值对。在getvalue函数中,我们同样先计算键的哈希值,然后进行线性探测,直到找到对应的键或者空槽位。如果找到了对应的键,我们就返回该键对应的值,否则就返回默认值0。
阅读全文