4、hash函数的代码实现
#ifndef HASHTABLE
#define HASHTABLE
#include<vector>
#include<map>
using namespace std;
template<class K,class V>
class HashTable{
private:
const static int upperTol = 10;
const static int lowerTol = 2;
const static int initCapacity = 7;
map<K, V> * hashtable;
int num_element;
int M;
int hash(K key){ //求出 hash值
return (std::hash<K>()(key)% M);
}
void resize(int newM){ //进行扩容操作
map<K, V> * newHashTable = new map<K, V>[newM]();
for (int i = 0; i < newM; i++)
newHashTable[i] = map<K, V>();
int oldM = M;
this->M = newM;
for (int i = 0; i < oldM; i++){
map<K, V> map2 = hashtable[i];
for (auto p : map2)
newHashTable[hash(p.first)][p.first] = p.second;
}
this->hashtable = newHashTable;
}
//
public:
HashTable(int M){
this->M = M;
num_element = 0;
hashtable = new map<K, V>[M]();
for (int i = 0; i < M; i++)
hashtable[i] = map<K,V>();
}
HashTable(){
new (this) HashTable(initCapacity); //placement new
}
int getSize(){
return num_element;
}
void add(K key, V value){
// cout << hash(key) << endl;
if (hashtable[hash(key)].count(key) == 1) //判断里面的键,是否存在
hashtable[hash(key)][key] = value;
else{
hashtable[hash(key)][key] = value;
num_element++;
if (num_element >= upperTol*M){
resize(2*M);
}
}
}
V remove(K key){
V ret = NULL;
//map<K, V> map2 = hashtable[hash(key)];
if (hashtable[hash(key)].count(key) == 1){
ret = hashtable[hash(key)].erase(key);
num_element--;
if (num_element <= lowerTol*M &&M / 2>= initCapacity){
resize(M/2);
}
}
return ret;
}
void set(K key, V value){
if (hashtable[hash(key)].count(key) == 1){
hashtable[hash(key)][key] = value;
}
else{
cout << "不存在该键值" << endl;
}
}
bool contains(K key){
return hashtable[hash(key)].count(key) == 1;
}
V get(K key){
return hashtable[hash(key)][key];
}
};
#endif;
我们咋样解决hash冲突,上面是用的是seperate chaining 来解决。