【C++哈希桶(开散列)】_开散列 -- 哈希桶

1. 开散列（哈希桶）概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结存储在哈希表中。

• 散列函数计算:地址=关键码/哈希表的容量

开散列比闭散列的优势

• 闭散列的思想：找"下一个"为空的位置，那么就会相互冲突，如果冲突的多了，效率就低；
• 开散列的思想：哈希表的挂单链表，就不会相互冲突

框架：

 
template<class K>
struct Hash
{
};
// 字符串特化
template<>
struct Hash<string>
{
};
 
//节点
template<class T, class V>
struct HashNode
{
	pair<T, V> _kv;
	HashNode<T, V>* _next;
};
//哈希表
template<class T, class V>
class HashTable
{
	typedef HashNode<T, V> Node;
public:
	bool Erase(const K& key)
	Node* Find(const K& key)
	bool Insert(const pair<K, V>& kv)
private:
	vector<Node*> _tables;
	size_t _n = 0;
};

 2.把各种类型转化为整形以及字符串的特化

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
// 特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto e : s)
		{
			// BKDR,减少哈希冲突
			//防止一个桶挂的太长
			value *= 31;
			value += e;
		}
		return value;
	}
};

3.查询接口函数

Node* Find(const K& key)
		{
			//数组为空返回空
			if (_tables.empty())
			{
				return nullptr;
			}
			//仿函数：把key转化为整形
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			//找在第几个桶
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
 
			return nullptr;
		}

4.插入接口函数

bool Insert(const pair<K, V>& kv)
		{
			//已经之歌元素有插入失败
			Node* ret = Find(kv.first);
			if (ret)
				return false;
 
			HashFunc hf;
			// 负载因子 == 1时扩容
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					//每个桶的头，如果为空就下一个桶
					Node* cur = _tables[i];
					while (cur)
					{
						//保存一下下一个元素以免找不到
						Node* next = cur->_next;
 
						size_t index = hf(cur->_kv.first) % newTables.size();
						// 头插，插入顺序不影响
						cur->_next = newTables[index];
						newTables[index] = cur;
 
						cur = next;
					}
 
					_tables[i] = nullptr;
				}
 
				_tables.swap(newTables);
			}
 
			size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			// 头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
 
			++_n;
			return true;
		}

5.删除接口函数

bool Erase(const K& key)
		{
			//数组为空没有删除的元素
			if (_tables.empty())
			{
				return false;
			}
 
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			//单链表删除保存前一个和后一个
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr) // 头删
					{
						_tables[index] = cur->_next;
					}
					else // 中间删除
					{
						prev->_next = cur->_next;
					}
 
					--_n;
 
					delete cur;
 
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
 
			return false;
		}