C++ —— 哈希详解 - 开散列与闭散列

//如果到达表的最后一个位置那么就模一下表的空间大小
hashi = (hash0 + i) % _tables.size();

hashi = (hash0 + (i*i*flag)) % _tables.size();

//定义一个枚举来记录数组的三个状态
enum State
{
	EXIST,//存在
	EMPTY,//空
	DELETE//删除
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;//状态为空
};

template<class K, class V>
class HashTable
{
public:

private:
	vector<HashData<K, V>> _tables;//表的空间大小
	size_t _n;  // 记录数据个数
};

//素数表
inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	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
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

//扩容
// 负载因子 >= 0.7扩容 n/m 数据个数/表的空间大小
//为了方便计算分子n*10
if (_n * 10 / _tables.size() >= 7)
{
	//创建一个新的哈希表 newht 哈希表里本来就有vector
	HashTable<K, V> newht;
	//*2是无法一直保持素数的
	//newht._tables.resize(_tables.size() * 2);

	//使用素数表来获取比素数表的值大一点的值
	newht._tables.resize(__stl_next_prime(_tables.size() + 1));

	for (auto& data : _tables)
	{
		// 遍历旧表，旧表的数据映射到新表
		if (data._state == EXIST)
		{
			//使用新对象去调用插入，把旧表的数据插入到新表
			newht.Insert(data._kv);
		}
	}
	//交换新旧表的空间
	_tables.swap(newht._tables);
}

bool Insert(const pair<K, V>& kv)
{
	//如果值已经存在
	if (Find(kv.first))
		return false;
	Hash hash;//仿函数，用于转换成为无符号整形
	//插入值之后从起始位置hash0去用插入的值对表的大小取模算出值对应的位置
	size_t hash0 = hash(kv.first) % _tables.size();//hash0是第一次算出来的位置
	size_t hashi = hash0;
	size_t i = 1;
	int flag = 1;
	while (_tables[hashi]._state == EXIST)//如果hashi的状态为存在
	{
		//进行线性探测
		//如果到达表的最后一个位置那么就模一下表的空间大小
		hashi = (hash0 + i) % _tables.size();
		++i;

		//二次探测
		/*hashi = (hash0 + (i*i*flag)) % _tables.size();
		if (hashi < _tables.size())
			hashi += _tables.size();

		if (flag == 1)
		{
			flag = -1;
		}
		else
		{
			++i;
			flag = 1;
		}*/
	}

	//当遇到空的位置就插入
	_tables[hashi].kv = kv;
	_tables[hashi]._state = EXIST;//将插入的位置标记为存在
	++_n;

	return true;
}

HashData<K, V>* Find(const K& key)
{
	Hash hash;
	size_t hash0 = hash(key) % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;
	while (_tables[hashi]._state != EMPTY)
	{
		if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
			&& _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];
		}

		// 线性探测
		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	return nullptr;
}

bool Erase(const K& key)
{
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		ret->_state = DELETE;
		return true;
	}
	else
	{
		return false;
	}
}

//定义一个枚举来记录数组的三个状态
enum State
{
	EXIST,//存在
	EMPTY,//空
	DELETE//删除
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;//状态为空
};


template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

/*
1. 将string类型转换成无符号整形(BKDR_Hash)
2. 字符串转换成整形，可以把字符ascii码相加即可
3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
4. 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去
乘以⼀个质数，这个质数⼀般去31, 131等效果会⽐较好
*/

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	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
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

namespace open_address//开发定址法
{								//加上一个仿函数Hash，用于转换成为无符号整形
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
			:_tables(__stl_next_prime(0))//给一个0去获取>=0的素数
			, _n(0)//数据个数
		{}

		bool Insert(const pair<K, V>& kv)
		{
			//如果值已经存在
			if (Find(kv.first))
				return false;

			//扩容
			// 负载因子 >= 0.7扩容 n/m 数据个数/表的空间大小
			//为了方便计算分子n*10
			if (_n * 10 / _tables.size() >= 7)
			{
				//创建一个新的哈希表 newht 哈希表里本来就有vector
				HashTable<K, V> newht;
				//*2是无法一直保持素数的
				//newht._tables.resize(_tables.size() * 2);

				//使用素数表来获取比素数表的值大一点的值
				newht._tables.resize(__stl_next_prime(_tables.size() + 1));

				for (auto& data : _tables)
				{
					// 遍历旧表，旧表的数据映射到新表
					if (data._state == EXIST)
					{
						//使用新对象去调用插入，把旧表的数据插入到新表
						newht.Insert(data._kv);
					}
				}
				//交换新旧表的空间
				_tables.swap(newht._tables);
			}


			Hash hash;//仿函数，用于转换成为无符号整形
			//插入值之后从起始位置hash0去用插入的值对表的大小取模算出值对应的位置
			size_t hash0 = hash(kv.first) % _tables.size();//hash0是第一次算出来的位置
			size_t hashi = hash0;
			size_t i = 1;
			int flag = 1;
			while (_tables[hashi]._state == EXIST)//如果hashi的状态为存在
			{
				//进行线性探测
				//如果到达表的最后一个位置那么就模一下表的空间大小
				hashi = (hash0 + i) % _tables.size();
				++i;

				//二次探测
				/*hashi = (hash0 + (i*i*flag)) % _tables.size();
				if (hashi < _tables.size())
					hashi += _tables.size();

				if (flag == 1)
				{
					flag = -1;
				}
				else
				{
					++i;
					flag = 1;
				}*/
			}

			//当遇到空的位置就插入
			_tables[hashi].kv = kv;
			_tables[hashi]._state = EXIST;//将插入的位置标记为存在
			++_n;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hash;
			size_t hash0 = hash(key) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				// 线性探测
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			
			size_t hashi = key % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						// 头结点
						_tables[hashi] = cur->_next;
					}
					else
					{
						// 中间节点
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}



	private:
		vector<HashData<K, V>> _tables;//表的空间大小
		size_t _n;  // 记录数据个数
	};
}

//将普通类型转换成无符号整形
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};


/*
1. 将string类型转换成无符号整形(BKDR_Hash)
2. 字符串转换成整形，可以把字符ascii码相加即可
3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
4. 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去
乘以⼀个质数，这个质数⼀般去31, 131等效果会⽐较好
*/
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};

namespace hash_bucket//哈希桶
{
	template<class K, class V>
	struct HashNode//给一个节点用来挂节点
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		//构造
		HashTable()
			:_tables(11)
			, _n(0)
		{}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0;// 表中存储数据个数
	};
}

bool Insert(const pair<K, V>& kv)
{
    Hash hs;
    size_t hashi = kv.first % _tables.size();
    // 头插
    //让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
    Node* newnode = new Node(kv);//创建一个新节点new Node

    //将新节点的下一个节点指向原来的第一个节点的地址
    //第一个节点的地址在哈希表里
    newnode->_next = _tables[hashi];

    _tables[hashi] = newnode;//再把新节点给与_tables[hashi]里存储的指针
    ++_n;

    return true;
}

// 负载因子 == 1时扩容
if (_n == _tables.size())
{
	vector<Node*> newTatble(_tables.size() * 2);
	//遍历旧表
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			// 旧表数据头插到新表
			size_t hashi = cur->_kv.first % newTatble.size();
			cur->_next = newTatble[hashi];
			newTatble[hashi] = cur;

			cur = next;
		}
		//交换
		_tables[i] = nullptr;

	}

	_tables.swap(newTatble);
}

HashData<K, V>* Find(const K& key)
{
	Hash hash;
	size_t hash0 = hash(key) % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;
	while (_tables[hashi]._state != EMPTY)
	{
		if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
			&& _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];
		}

		// 线性探测
		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	return nullptr;
}

bool Erase(const K& key)
		{
			
			size_t hashi = key % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						// 头结点
						_tables[hashi] = cur->_next;
					}
					else
					{
						// 中间节点
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

namespace hash_bucket//哈希桶
{
	template<class K, class V>
	struct HashNode//给一个节点用来挂节点
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		//构造
		HashTable()
			:_tables(11)
			, _n(0)
		{}

		bool Insert(const pair<K, V>& kv)
		{
			// 负载因子 == 1时扩容
			if (_n == _tables.size())
			{
				vector<Node*> newTatble(_tables.size() * 2);
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						// 旧表数据头插到新表
						size_t hashi = cur->_kv.first % newTatble.size();
						cur->_next = newTatble[hashi];
						newTatble[hashi] = cur;

						cur = next;
					}
					//交换
					_tables[i] = nullptr;

				}

				_tables.swap(newTatble);
			}

			size_t hashi = kv.first % _tables.size();
			// 头插
			//让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
			Node* newnode = new Node(kv);//创建一个新节点new Node

			//将新节点的下一个节点指向原来的第一个节点的地址
			//第一个节点的地址在哈希表里
			newnode->_next = _tables[hashi];

			_tables[hashi] = newnode;//再把新节点给与_tables[hashi]里存储的指针
			++_n;

			return true;
		}

		Node* Find(const K& key)
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return &cur->_kv.first;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();

			Node* cur = _tables[hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = 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 _n = 0;// 表中存储数据个数
	};
}