哈希冲突解决：除法散列法与线性探测详解

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
enum State
{
	EMPTY,//位置上状态为空
	DELETE,//位置上状态为删除
	EXIST//位置上状态为存在
};
template<class k,class v>
//破局
struct HashDate
{
	State _state=EMPTY;//每个位置上都有这么一个状态
	pair<k, v> _kv;//保存的数据
};
template<class k, class v>
class HashTable
{
private:
	vector<HashDate<k,v>> _table;
	size_t _n;//存储的数据个数
};

//插入pair<k,v>
bool insert(const pair<k, v>& kv)
{
	//先计算key第一个要映射的位置
	size_t hash0 = key % _table.size();
	size_t i = 1;
	size_t hashi = hash0;
	//如果第一个位置不是exist,则直接插入；
    //若发生冲突则往后查找位置状态不是exist的位置，状态为empty或者是delete都可以插入
	while (_table[hashi]._state == EXIST)
	{
		//% _table.size()的目的是为了防止越界
		hashi = (hashi + i) % _table.size();
		++i;
	}
	//跳出循环，找到位置
	_table[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	++_n;
	return true;
}

//插入pair<k,v>
bool insert(const pair<k, v>& kv)
{
	//负载因子>=0.7是就要扩容
	if ((double)_n / _table.size() >= 0.7)
	{
		////_table.resize(2 * _table.size());
		////方法1:搞一个新的数组，拷贝旧数据，将旧表中的数据重新映射到新表中，然后交换
		//veector<HashDate<k, v>> newTable(2 * _table.size());
		//for (size_t i = 0; i < _table.size(); i++)
		//{
		//	if (_table[i]._state == EXIST) 
		//	{
		//		//重新映射
		//		//……
		//	}
		//}
		//_table.swap(newTable);
		

		//方法2：创建一个新的哈希表
		HashTable<k, v> newtable;
		newtable._table.resize(2 * _table.size());
		//遍历旧的表，将旧表中的pair数据插入到新表中
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i]._state == EXIST) {
				newtable.insert(_table[i]._kv);
			}
		}
		//交换新旧哈希表中的_table表
		_table.swap(newtable._table);
	}
	//先计算key第一个要映射的位置
	size_t hash0 = kv.first % _table.size();
	size_t i = 1;
	size_t hashi = hash0;
	//如果第一个位置不是exist,则直接插入；
    //若发生冲突则往后查找位置状态不是exist的位置，状态为empty或者是delete都可以插入
	while (_table[hashi]._state == EXIST)
	{
		//% _table.size()的目的是为了防止越界
		hashi = (hashi + i) % _table.size();
		++i;
	}
	//跳出循环，找到位置
	_table[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	++_n;
	return true;
}

//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
//以保证key的每一位2进制都参与运算
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	// >= n
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

#include<iostream>
#include<vector>
using namespace std;
//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
//以保证key的每一位2进制都参与运算
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	// >= n
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}
enum State
{
	EMPTY,//位置上状态为空
	DELETE,//位置上状态为删除
	EXIST//位置上状态为存在
};
template<class k,class v>
struct HashDate
{
	State _state;//每个位置上的状态
	pair<k, v> _kv;//存储的数据
};
template<class k, class v>
class HashTable
{
public:
	HashTable()
		:_table(__stl_next_prime(1))
	{}
	//插入pair<k,v>
	bool insert(const pair<k, v>& kv)
	{
		//不允许插入相同的key
		if (find(kv.first))
		{
			return false;
		}
		//负载因子>=0.7是就要扩容
		if ((double)_n / _table.size() >= 0.7)
		{
			////_table.resize(2 * _table.size());
			////方法1:搞一个新的数组，拷贝旧数据，然后交换
			//vector<HashDate<k, v>> newTable(2 * _table.size());
			//for (size_t i = 0; i < _table.size(); i++)
			//{
			//	if (_table[i]._state == EXIST) 
			//	{
			//		//重新映射
			//		//……
			//	}
			//}
			//_table.swap(newTable);
			
			//创建一个新的哈希表
			HashTable<k, v> newtable;
			newtable._table.resize(__stl_next_prime(_table.size()+1));
			//遍历旧的表，将旧表中的pair数据插入到新表中
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._state == EXIST) {
					newtable.insert(_table[i]._kv);
				}
			}
			//交换新旧哈希表中的_table表
			_table.swap(newtable._table);
		}
		//先计算key第一个要映射的位置
		size_t hash0 = kv.first % _table.size();
		size_t i = 1;
		size_t hashi = hash0;
		//查找位置状态不是exist的位置，状态为empty或者是delete都可以插入
		while (_table[hashi]._state == EXIST)
		{
			//% _table.size()的目的是为了防止越界
			hashi = (hashi + i) % _table.size();
			++i;
		}
		//跳出循环，找到位置
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_n;
		return true;
	}
private:
	vector<HashDate<k,v>> _table;
	size_t _n;//存储的数据个数
};

//返回值类型为HashDate<k, v>*，方便修改相应的数据
HashDate<k, v>* find(const k& key)
{
	//计算key映射的位置
	size_t hash0 = key % _table.size();
	size_t i = 1;
	size_t hashi = hash0;
	//只要这个位置不是空就继续查找
	while (_table[hashi]._state !=EMPTY)
	{
		//只有位置状态为exist的位置中的数据才进行key值比较
		if (_table[hashi]._state!=DELETE&&_table[hashi]._kv.first == key)
		{
			return &_table[hashi];
		}
		hashi = (hashi + i) % _table.size();
		++i;
	}
	return nullptr;
}

bool erase(const k& key)
{
	//删除前先进行查找，如果找到了，就让其状态为delete
	HashDate<k, v>* ret = find(key);
	if (ret)
	{
		ret->_state = DELETE;
		--_n;
		return true;
	}
	else
	{
		return false;
	}
}

#pragma once
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
//使用下面的函数就可以实现了建议M取不太接近2的整数次幂的一个质数（素数）
//以保证key的每一位2进制都参与运算
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	// >= n
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}
enum State
{
	EMPTY,//位置上状态为空
	DELETE,//位置上状态为删除
	EXIST//位置上状态为存在
};
template<class k,class v>
//破局
struct HashDate
{
	State _state=EMPTY;//每个位置上都有这么一个状态
	pair<k, v> _kv;//保存的数据
};
template<class k>
struct HashFunc
{
	//将不是整型的转换成整型
	size_t operator()(const k& key)
	{
		return size_t(key);
	}
};
//特化一下
template<>
struct HashFunc<string>
{
	//我们可以将string中的每一位的asscal码值加起来去取模
	//我们可以再加之前*131,避免大量冲突
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			//我们可以再加下一个之前 * 131
			hash *= 131;
		}
		return hash;
	}
};

template<class k, class v,class hash=HashFunc<k>>
class HashTable
{
public:
	HashTable()
		:_table(__stl_next_prime(1))
	{}
	//插入
	hash hs;//仿函数，将数据变成整型，以便取模
	bool insert(const pair<k, v> kv)
	{
		//不允许插入相同的key
		if (find(kv.first))
		{
			return false;
		}
		//若空间不够，还插什么插
		//这里看空间是否足够，看的是复杂因子
		// 负载因⼦⼤于0.7就扩容
		if ((double)_n / (double)_table.size() >= 0.7)
		{
			//_table.resize();
			//直接进行扩容操作，原先的数据的位置没有改变，会有问题
			//方法1:搞一个新的数组，拷贝旧数据，然后交换
			// 有点麻烦
			//vector<HashDate<k, v>> newtables(2 * _table.size());
			//for (size_t i = 0; i < _table.size(); i++)
			//{
			//	if (_table[i]._state == EXIST) {
			//		//重新映射
			//	}
			//}
			////交换
			//_table.swap(newtables);

			//方法2:直接重新搞一个哈希表
			HashTable<k, v, hash> newht;
			newht._table.resize(__stl_next_prime(_table.size()+1));
			//遍历旧表，将旧表中的数据插入到新表中
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._state == EXIST) {
					//旧表数据插入到新表中
					newht.insert(_table[i]._kv);
				}
			}
			//交换新旧哈希表中的_table表
			_table.swap(newht._table);
		}
		//计算出第一个要映射的位置
		size_t hash0 = hs(kv.first) % _table.size();
		size_t i = 1;
		size_t hashi = hash0;
		//寻找可以插入的位置，只要位置不为exist就可以插入
		while (_table[hashi]._state == EXIST)
		{
			hashi = (hashi + i) % _table.size();
			//(hashi + i) % _table.size()是为了防止越界
			++i;
		}
		//跳出循环说明找到位置
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_n;
		return true;
	}


	HashDate<k, v>* find(const k& key)
	{
		size_t hash0 = hs(key) % _table.size();
		size_t i = 1;
		size_t hashi = hash0;
		//只要这个位置不是空就继续查找
		while (_table[hashi]._state != EMPTY)
		{
			if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
			{
				return &_table[hashi];
			}

			hashi = (hashi + i) % _table.size();
			++i;
		}
		return nullptr;
	}


	bool erase(const k& key)
	{
		//删除前先进行查找，如果找到了，就让其状态为delete
		HashDate<k, v>* ret = find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_n;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	//vector<pair<k, v>> _table;
	//这样写是不行的
	//为什么？如果我删除某个位置上的数据，那这个位置上就是nullptr
	// 我在进行查找的时候，比如查找删除数据的后一个位置上的数据
	// 那就查找不到，因为那个删除数据位置上是nullptr
	// 找到空就停止了，所以我们不能这么写

	//破局
	//直接复用vector，目的是为了方便扩容
	vector<HashDate<k, v>> _table;
	size_t _n = 0;//存储的数据个数
};