上篇博客我们写了解决哈希冲突的两种办法,不过我们写的都是针对整形的,而在实际情况下,要存入哈希表中的数据可以是string或自定义类型等等。那么我们就应该想一种办法去解决这里的问题。
比如说string,我们想到如何让string也转为整形,本质上就是利用一个哈希函数将字符串转化为哈希值,也就是整形。比如我们可以让字符串中每一个字符的ACSCII值相加,但这样容易重复,我们可以让它们乘以一个不同的数在进行相加,这样重复率会低一些。于是就有人研究这种问题,怎么才能让重复率尽可能的低呢?
于是有人提出一种BKDRhash,下面有一个简单的解释,
于是我们就可以来实现一下,我们这里实现成仿函数的形式,为了方便后面给哈希表传参数
其实类似的哈希函数还有很多,我们这里就以这个为例子。其实库中也是这么实现的
说完了字符串,再举一个例子,比如说日期类,其实我们也让年月日分别乘一个数就行,或者有其他的合适的方式都可以
我们知道,unordered_map和unordered_set就是用哈希表封装出来的
我们如果用string当key值的话,是直接可以编译过的,而日期类却不行,这是因为string经常做key,所以在库中做了特化处理,就是模板进阶部分说的特化
我们可以看到哈希函数是有缺省值的,我们用一些它支持的类型是不用传的,并且对于string来说是一种类模板的特化,就是只要key是string,就调用特化版本的,大概像这样
对于int就会调用第一个,对于string就会调用特化版的第二个
那么接下来我们就接着上篇博客,加上模板等一系列的操作,并且哈希桶由于是去堆上开空间,所以我们还需要写一个析构函数,否则会造成内存泄漏。因为我们后边还要用这个封装出unordered_map和unordered_set
我下边只是对于哈希桶版本进行了一些修改
template<class T>
struct hashfun {
size_t operator()(const T& key) {
return (size_t)key;
}
};
template<>
struct hashfun<string> {
size_t operator()(const string& str) {
size_t hashret = 0;
for (auto& e : str) {
hashret = hashret * 131 + e;
}
return hashret;
}
};
namespace hash_bucket {
template<class K,class V>
struct HashNode {
HashNode(const pair<K,V>&vall)
:val(vall)
,_next(nullptr){}
pair<K,V> val;
HashNode<K,V>* _next = nullptr;
};
template<class K,class V,class hashfunc=hashfun<K>>
class HashTable {
typedef HashNode<K, V> Node;
public:
HashTable(size_t n=10) {
_hashvec.resize(n, nullptr);
}
~HashTable() {
for (size_t i = 0; i < _hashvec.size(); i++) {
Node* cur = _hashvec[i];
Node* next = nullptr;
while (cur) {
next = cur->_next;
delete cur;
cur = next;
}
}
}
Node* find(const K&key) {
size_t hashi = hashfunc()(key) % _hashvec.size();
Node* cur = _hashvec[hashi];
while (cur) {
if (cur->val.first == key)return cur;
cur = cur->_next;
}
return nullptr;
}
bool insert(const pair<K,V>&_kv) {
if (find(_kv.first))return false;
if (_n == _hashvec.size()) {
//扩容
HashTable newtable(_hashvec.size() * 2);
for (size_t i = 0; i < _hashvec.size(); i++) {
Node* cur = _hashvec[i];
Node* next = nullptr;
while (cur) {
next = cur->_next;
size_t hashi = hashfunc()(cur->val.first) % newtable._hashvec.size();
cur->_next = newtable._hashvec[hashi];
newtable._hashvec[hashi] = cur;
cur = next;
}
_hashvec[i] = nullptr;
}
_hashvec.swap(newtable._hashvec);
}
size_t hashi = hashfunc()(_kv.first) % _hashvec.size();
Node* newnode = new Node(_kv);
newnode->_next = _hashvec[hashi];
_hashvec[hashi] = newnode;
++_n;
return true;
}
bool erase(const K&key) {
size_t hashi = hashfunc()(key) % _hashvec.size();
Node* prev = nullptr;
Node* cur = _hashvec[hashi];
while (cur&&cur->val != key) {
prev = cur;
cur = cur->_next;
}
if (cur == nullptr)return false;
if (prev == nullptr) {
_hashvec[hashi] = cur->_next;
}
else {
prev->_next = cur->_next;
}
delete cur;
return true;
}
private:
size_t _n = 0;
vector<Node*> _hashvec;
};
}