哈希

哈希也可以叫散列

画一个哈希表

 

 哈希冲突越多，哈希表效率越低。

闭散列开放定址法:

1.线性探测，依次往后去找下一个空位置。

2.二次探测，按2次方往后找空位置。

#pragma once
#include<vector>
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
template<class K>
struct SetKeyOfT
{
	const K& operator()(const K& key)
	{
		return key;
	}
};
//unordered_set<K>  ->HashTable<K,K>
//unordered_map<K,V>   ->HashTable<K,pair<K,V>>
enum State
{
	EMPTY,
	EXITS,
	DELETE,	
};
template<class T>
struct HashData//解决：该位置原来就是空还是删除后变为了空
{
	T _data;
	State _state;
};
template<class K,class T,class KeyOfT>
class HashTable//冲突了一定是连续的，但是删除会影响查找，所以应该设置状态标志。将T替换为HashData
{
	typedef HashData<T> HashData;
public:
	bool Insert(const T& d)
	{
		KeyOfT koft;
		//负载因子=表中数据/表的大小  衡量哈希表满的程度
		//表越接近满，插入数据越容易冲突，冲突越多，效率越低。
		//哈希表并不是满了才增容，开放定址法中，一般负载因子到了0.7左右就开始增容
		//负载因子越小，冲突概率越低，整体效率越高，但是负载因子越小，浪费的空间越大。
		//所以负载因子一般去折中值
		if (_tables.size()==0||_num*10/_tables.size()>=7)
		{
			//增容
			//1.开二倍大小的新表
			//2.遍历旧表中的数据，确定数据在新表中的映射位置
			//3.释放旧表
			vector<HashData> newtables;
			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			newtables.resize(_tables.size() * 2);
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._state == EXITS)
				{
					size_t index = koft(_tables[i]._data % newtables.size());
					while (newtables[index]._state == EXITS)
					{
						++index;
						if (index == _tables.size())
						{
							index = 0;
						}
					}
					newtables[index] = _tables[i];
				}
			}
			_tables.swap(newtables);
		}
		//KeyOfT koft;
		//计算d中的key在表中映射的位置
		size_t index = koft(d) % _tables.size();
		//EXITS就进行探测
		while (_tables[index]._state==EXITS)
		{
			if (koft(_tables[index]._data) == koft(d))
				return false;
			++index;
			if (index == _tables.size())
			{
				index = 0;
			}
		}
		_tables[index]._data = d;
		_tables[index]._state = EXITS;
		_num++;
		return true;
	}
	HashData* Find(const K& key)
	{
		KeyOfT koft;
		//计算d在表中映射的位置
		size_t index = key % _tables.size();
		while (_tables[index]._state != EMPTY)
		{
			if (koft(_tables[index]._data) == key)
			{
				if (_tables[index]._state == EXITS)
					return &_tables[index];
				else if (_tables[index]._state == DELETE)
					return nullptr;
			}
			++index;
			if (index == _tables.size())
			{
				index = 0;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		HashData* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_num;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	vector<HashData> _tables;
	size_t _num=0;//存了几个有效数据
};

void TestHashTable()
{
	
	HashTable<int, int, SetKeyOfT<int>> ht;
	ht.Insert(4);
	ht.Insert(14);
	ht.Insert(24);
	ht.Insert(5);
	ht.Insert(15);
	ht.Insert(25);
	ht.Insert(6);
	ht.Insert(16);
	

}

更优的实现方法

开散列哈希桶：

namespace OPEN_HASH
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
	};
	template<class K,class T,class KeyOfT>
	class HashTable
	{
	public:
		typedef HashNode<T>* Node;
		bool Insert(const T& data)
		{
			//1.先查找这个值在不在表中
			KeyOfT koft;
			//如果负载因子等于1，则增容，避免大量的哈希冲突
			if (_tables.size == _num)
			{
				//增容
				//1.开二倍大小的新表
				//2.遍历旧表中的数据，确定数据在新表中的映射位置
				//3.释放旧表
				vector<Node> newtables;
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				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 = koft(cur->_data) % newtables.size();
						cur->_next = newtables[index];
						newtables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables[i].swap(newtables);
			}
			//计算数据在表中映射的位置
			size_t index = koft(data) % _tables.size();
			Node cur = _tables[index];
			while (cur)
			{
				if (koft(cur->_data) == koft(data))
					return false;
				else
					cur = cur->next;
			}
			//2.头插到挂的链表中
			Node newnode = new Node(data);
			newnode->next = _tables[index];
			_tables[index] = newnode;
			++_num;
			return true;
		}
		Node* Find(const K& key)
		{
			KeyOfT koft;
			size_t index = key % _tables.size();
			Node cur = _tables[index];
			while (cur)
			{
				if (koft(cur->_data) == key)
				{
					return cur;
				}
				else return cur->_next;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			KeyOfT koft;
			size_t index = key % _tables.size();
			Node prev = nullptr;
			Node cur = _tables[index];
			while (cur)
			{
				if (koft(cur->_data) == key)
				{
					if (prev == nullptr)
						//表示要删的值在一个结点
						_tables[index] = cur->_next;
					else
						prev->_next = cur->_next;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	private:
		vector<Node> _tables;
		size_t _num=0;//记录表中存储的数据个数
	};
}