【C++】哈希二

上篇博客我们写了解决哈希冲突的两种办法，不过我们写的都是针对整形的，而在实际情况下，要存入哈希表中的数据可以是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;
	};
}