hash：哈希表 哈希桶

目录

1.哈希的思想

2.解决冲突

3.哈希表（采用的闭散列，线性探测）

4.哈希桶（开散列）

5.总结

---

1.哈希的思想

hash是一种根据存储的关键字的哈希值确定存储位置的算法。哈希值通过哈希函数可以计算得出结果，最常用的哈希函数就是除留余数法了。

---

2.解决冲突

如果俩个关键字值不同但是哈希值相同就会发生不明确存哪的问题，这种情况被称为哈希冲突。

解决冲突的方式1：闭散列，采用用线性探测，即跳过被占用的按顺序向下探测位置。

解决冲突的方式2：开散列，由于是链式结构，所以直接在对应位置串起来即可。

---

3.哈希表（采用的闭散列，线性探测）

上菜：

enum state
	{
		empty, //表示空状态
		exist, //表示占据状态
		dlete //表示删除状态
	};
	template<class K>
	class HashFunc //仿函数，用来计算关键字的hash值
	{
		int operator()(const K& key)
		{
			return key;
		}
	};
	template<> //特化，采用string的assic码来计算
	class HashFunc<string>
	{
		int operator()(const string& key)
		{
			int val = 0;
			for (auto e : key)
			{
				val *= 131; //结论，用数学公式证明的，用就完了。
				val += e;
			}
			return val;
		}
	};
	template<class K,class V>
	struct hashnode
	{
		state st=empty;
		pair<K, V> _kv;
	};
	template<class K,class V,class Hash=HashFunc<K>>
	class hashtable
	{
	private:
		vector<hashnode<K,V>> _table;
		int size = 0;
	public:
		bool insert(const pair<K, V>& kv) //插入
		{
			if (_table.size() == 0 || 10*size/_table.size() >= 7) //负载因子确定为0.7
			{
				int newsize = _table.size() == 0 ? 10 : _table.size() = _table.size() * 2;
				hashtable<K,V,Hash> newtable; //建立新表
				newtable._table.resize(newsize); //修改长度
				for (auto e : _table)
				{
					//将旧表元素插入到新表中
					if (e.st == empty)
					{
						newtable.insert(e._kv);
					}
				}
				_table.swap(newtable._table);//新旧表交换
			}
			Hash hash;
			int val=hash(kv.first); //计算下标
			int hashi = val % (_table.size()); 
			while (_table[hashi].st == exist) //已经被占据了就继续查找
			{
				hashi++;
				hashi %= (_table.size()); //防止越界
			}
			_table[hashi]._kv = kv;
			_table[hashi].st = exist; //记得标记为占有状态
			size++; 
			return true;
		}
		hashnode<K, V>* find(const K& key) //要找一个循环，因为元素可能发生了冲突
		{
			Hash hash;
			int start = hash(key) % (_table.size()); //标记起始位置
			int hashi = start;
			while (hashi != start && _table[hashi].st != empty)//不能为空位置
			{
				if (_table[hashi].st != delete && _table[hashi]._kv.first == key)
				{
					return &_table[hashi];
				}
				hashi++;
				hashi %= (_table.size());
			}
			return nullptr;
		}
		bool erase(const K& key)
		{
			hashnode<K, V>* ret = find(key); //复用find查找位置
			if (ret)
			{
				ret->st = dlete;
				--size; //记得--size
				return true;
			}
			return false;
		}
		void print() //打印看看结果
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i].st == exist)
				{
					printf("[%d:%d] ", i, _tables[i]._kv.first);
				}
				else
				{
					printf("[%d:*] ", i);
				}
			}
			cout << endl;
		}
	};

思路非常简单，先用hash函数找到对应位置。被占住了就继续向后找空位置。写这段代码需要注意的是在扩容时，由于长度的变化，需要映射新的位置。可以采用复用insert的方式完成映射。

---

4.哈希桶（开散列）

上菜：

#pragma once
#include<iostream>
#include<vector>
using namespace std;
 
template<class K>
struct HashFunc
{
	int operator()(const K& key)
	{
		return key;
	}
};
template<>
struct HashFunc<string>
{
	int operator()(const string& key)
	{
		int val = 0;
		for (auto e : key)
		{
			val *= 131;
			val += e;
		}
		return val;
	}
};
 
template<class K, class V>
struct HashNode //链式结构要创建结点
{
	pair<K, V> _kv;
	HashNode* _next;
	HashNode(pair<K, V> kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};
 
template<class K,class V,class Hash=HashFunc<K>>
class Hashtable
{
private:
	vector<HashNode<K,V>*> _table;
	int size=0;
public:
	~Hashtable()
	{
		for (int i = 0; i < _table.size(); i++)
		{
			HashNode<K, V>* cur = _table[i];
			while (cur)
			{
				HashNode<K, V>* next = cur->_next; //记录下一个位置
				delete cur;
				cur = next;
			}
			_table[i] = nullptr; //记得置空
		}
	}
	HashNode<K,V>* find(const K& key)
	{
		Hash hash;
		if (_table.size() == 0)
		{
			return nullptr;
		}
		int hashi = hash(key) % _table.size(); //计算位置
		HashNode<K,V>* cur = _table[hashi];
		while (cur)
		{
			if (cur->_kv.first == key) //找到
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr;
	}
	bool insert(const pair<K, V>& kv)
	{
		if (find(kv.first)) //去重
			return false;
		if (_table.size() == size || _table.size() == 0) //扩容
		{
			int newsize = (_table.size() == 0 ? 10 : _table.size() * 2);
			Hashtable<K, V, Hash> newtable; //构建新表
			newtable._table.resize(newsize); 
			for (int i = 0; i < _table.size(); i++)
			{
				//不能浪费空间，要将原来的资源直接插入到新表就不可以复用。
				HashNode<K, V>* cur = _table[i];
				while (cur)
				{
					HashNode<K, V>* next = cur->_next;
					Hash hash;
					int hashi = hash(cur->_kv.first)%(newtable._table.size());
					cur->_next = newtable._table[hashi];
					newtable._table[hashi] = cur;
					cur = next;
				}
			}
			_table.swap(newtable._table);
		}
		Hash hash;
		int hashi = hash(kv.first)%_table.size();
		HashNode<K, V>* newnode = new HashNode<K, V>(kv);
		//头插
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		++size; //记得++size
	}
};

同样是先用hash函数找到对应位置，不同的是，可以直接头插不需要移位。唯一需要注意的依然是扩容，这里不可以复用代码，因为旧表的空间必须利用上，不然会出现资源泄露的问题。

---

5.总结

hash（链式）相对于平衡搜索数（avl 红黑树）有优有劣。

优点：a.对于查找来说，平衡搜索树时间复杂度是O(logn)。而hash的时间复杂度趋近O（1）。

           b.对于插入来说，平衡搜索树需要不断的翻转。而hash直接头插即可。

缺点：a.由于搜索树的性质决定了搜索树可以将数据有序化，而hash是无序的。

           b.随着数据的增大，hash空间消耗会大于平衡搜索树。