【C++】精妙的哈希算法

_小羊_

发布于 2024-10-16 15:26:22

610

发布于 2024-10-16 15:26:22

文章被收录于专栏：C++

一、哈希结构

1、哈希概念

AVL树、红黑树等平衡树搜索效率取决于搜索过程中的比较次数，一般时间复杂度为O(logN)，虽然平衡树的搜索效率已经很快，但如果可以不经过任何比较或者常数次的比较后就能搜索到我们要找的元素，会极大的提高效率。

哈希结构，是一种通过特定函数（哈希函数）将关键码映射到表中的一个位置，那么在查找时通过该函数就可以很快的找到该元素。

但是上述的映射方法存在一个问题，就是不同的元素可能会映射到同一个位置，这时就发生了哈希冲突（也叫哈希碰撞），解决哈希冲突，是实现哈希结构的关键。

2、哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不合理。 哈希函数的设计要保证高效性和可靠性：

一致性：确保相同的输入总是产生相同的输出哈希值
均匀分布：哈希值应在哈希表的地址空间中尽可能均匀分布，以减少哈希冲突
计算效率：哈希函数应简单且计算快速，以便在实际应用中能够快速执行
冲突最小化：设计哈希函数时应尽量减少哈希冲突的发生，以提高哈希表的性能

| 常见哈希函数： 哈希函数是哈希表的核心，它决定了如何将关键字映射到哈希地址。

直接定制法：取关键字的某个线性函数为散列地址，Hash(Key)=A*Key+B。这种方法简单、均匀，但需要事先知道关键字的分布情况
除留余数法：取一个不大于哈希表地址数m的质数p，按照哈希函数Hash(key)=key%p将关键码转换成哈希地址。这种方法实现简单，且当p选择合理时，哈希冲突的概率较低
平方取中法：对关键字进行平方运算，然后抽取中间的几位作为哈希地址。这种方法适用于不知道关键字分布情况，且位数不是很大的场景
折叠法：将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长取后几位作为哈希地址。这种方法适用于关键字位数较多的情况

此外，还有随机数法、数学分析法等哈希函数设计方法，可以根据具体应用场景选择合适的哈希函数。 哈希函数设计的越好，产生哈希冲突的可能性就越低，但是哈希冲突还是无可避免。

3、哈希冲突

解决哈希冲突的两种常见方法是：闭散列（开放定址法）和开散列（链地址法）。

3.1 闭散列

当发生哈希冲突时，如果哈希表中还有空位置，就把key存放到冲突位置的“下一个”空位置去。找下一个空位置，常见的探测方法有线性探测、二次探测和双重散列等。

| 线性探测： 从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止。

插入上图中在插入15前，通过哈希函数得到映射位置为5，但是5位置被占了，就依次向后找，在7位置找到了一个空位置将15插入。
删除闭散列解决哈希冲突时，不好随便物理删除某个元素，可以考虑标记的方法来伪删除一个元素。

//每个位置都给标记
enum State
{
	EXIST,//存在
	DELETE,//删除
	EMPTY//空
}

| 线性探测实现：

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:

	HashTable()
	{
		_tables.resize(10);//提前开10个位置
	} 
	
private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;//存储元素个数
};

插入

关键码对表的size()取模，不能对capacity()取模，因为哈希表支持[]访问，只能访问下标小于size()的元素。

散列表的载荷因子 = 表中的元素个数 / 表的大小

当载荷因子达到某个临界值，就需要扩容。载荷因子越大，产生冲突的可能性就越大，相反产生冲突的可能性就越小。通常载荷因子应限制在0.7-0.8一下。

不能直接对原表进行扩容，无论是原地扩还是异地扩，都会把原数据拷贝过来。但是扩完容后元素的相对位置可能会发生改变，原本冲突的元素扩完容后就不冲突了，所以直接对原表进行扩容是不行的。

扩容有两种方法：

方法一：新建原表两倍大小的vector，遍历原表的元素重新映射到vector中，再将新建的vector和原表的vector交换。
方法二：因为方法一还需要重写一遍映射过程，所以可以直接新建一个哈希表，遍历原表的元素插入到新建的哈希表中，最后交换两个哈希表的vector，这个方法的好处是新建的哈希表复用了原哈希表的Insert。

方法一我们就不实现了，直接用更好一点的方法二：

bool Insert(const pair<K, V>& kv)
{
	if (_n * 10 / _tables.size() >= 7)//载荷因子达到一定的值进行扩容
	{
		HashTable<K, V> newHT;
		newHT._tables.resize(2 * _tables.size());
		for (int i = 0; i < _tables.size(); i++)
		{
			if (_tables[i]._state == EXIST)
			{
				newHT.Insert(_tables[i]._kv);
			}
		}
		_tables.swap(newHT._tables);
	}
	size_t hashi = kv.first % _tables.size();//确定映射位置
	while (_tables[hashi]._state == EXIST)
	{
		++hashi;
		hashi %= _tables.size();//防止越界
	}
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	++_n;
	return true;
}

但是现在还有个问题，在上面的代码中要求我们的key可以取模，也就是key只能是无符号整数，如果是浮点数、字符串等上面的代码就行不通，所以还需要想办法将可能出现的浮点数、字符串等类型的key转换为无符号的整型再做映射。

像浮点数等可以直接强转为无符号整型，可以考虑用仿函数解决。字符串一般不能直接强转为无符号整型，我们可以对字符串特殊处理，也就是模版特化，将字符串中字符的ASCII码值加起来作为映射值。但是这里还有个问题，将字符串中字符的ASCII码值加起来也可能冲突，比如相同的字符按不同的顺序组合起来的字符串。不过好在有专门的字符串哈希函数（字符串哈希函数有好多种，这里使用其中一种：BKDR Hash函数），这里就不做过多介绍了，有兴趣的同学请百度了解。他给出的解决办法是字符每次相加之前+31（31、131、1313、13131…都行）来尽可能减少冲突。

template<class K>
struct HashFunc //key强转为整型
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//对string类型特殊处理
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash = hash * 31 + e;
		}
		return hash;
	}
};

删除

删除指定的元素，只需要找到该元素的位置，将该位置的状态标记为DELETE即可。

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

查找

查找过程需要注意的是，当在表中找到被查找的元素时还要判断此位置是否被标记为已删除，因为删除操作我们并没有实际物理上的删除某个元素。

HashData<K, V>* Find(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	while (_tables[hashi]._state != EMPTY)
	{
		if (_tables[hashi]._state != DELETE 
		&& _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];
		}
		++hashi;
		hashi %= _tables.size();
	}
	return nullptr;
}

线性探测的优点是简单好理解，缺点是数据容易堆积，查找时可能需要多次比较。闭散列 / 开放定址法我们就先实现到这里，它是一种零和博弈，和下面将要介绍的开散列 / 链地址法对比还是稍逊一筹。

3.2 开散列

通过哈希函数计算散列地址，具有相同映射地址的元素归于同一子集合，每一个子集合称为一个哈希桶，各个桶中的元素通过一个单链表链接起来，哈希表中存各链表的头节点。开散列每个桶中存放的都是产生哈希冲突的元素。

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

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash = hash * 31 + e;
		}
		return hash;
	}
};

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

	pair<K, V> _kv;
	HashNode<K, V>* _next;
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
	HashTable()
	{
		_tables.resize(10, nullptr);
	}

	~HashTable()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* pcur = _tables[i];
			while (pcur)
			{
				Node* next = pcur->_next;
				delete pcur;
				pcur = next;
			}
			_tables[i] = nullptr;
		}
	}

private:
	vector<Node*> _tables;
	size_t _n = 0;
};

插入

bool Insert(const pair<K, V>& kv)
{
	size_t hashi = kv.first % _tables.size();

	//负载因子==1就扩容
	if (_n == _tables.size())
	{
		HashTable<K, V> newHT;
		newHT._tables.resize(2 * _tables.size(), nullptr);
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* pcur = _tables[i];
			while (pcur)
			{
				newHT.Insert(pcur->_kv);
				pcur = pcur->_next;
			}
		}
		_tables.swap(newHT._tables);
	}
	Node* newnode = new Node(kv);

	//头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

上面的扩容过程虽然可行，但是不够好。假如原表中有很多个节点，新建新表扩容后复用Insert就要new很多个节点再插入，这实际上是很有消耗的。因为原节点和新new的节点并无差别，所以可以直接将原表中的节点拿下来头插到新表中，这样就不用再new新节点。

| 优化：

bool Insert(const pair<K, V>& kv)
{
	size_t hashi = hs(kv.first) % _tables.size();
	
	//负载因子==1就扩容
	if (_n == _tables.size())
	{
		vector<Node*> newtables(2 * _tables.size(), nullptr);
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* pcur = _tables[i];
			while (pcur)
			{
				Node* next = pcur->_next;
				size_t hashi = pcur->_kv.first % newtables.size();
				pcur->_next = newtables[hashi];
				newtables[hashi] = pcur;
				pcur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newtables);
	}
	Node* newnode = new Node(kv);

	//头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

删除

学习过链表我们知道，单链表的头删和其他位置的删除需要分开处理，因为其他位置删除节点后要将前后节点链接起来，而单链表的头节点没有前一个节点。

bool Erase(const K& key)
{
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	Node* pcur = _tables[hashi];
	Node* prev = nullptr;
	while (pcur)
	{
		if (pcur->_kv.first == key)
		{
			if (prev == nullptr)
			{
				_tables[hashi] = pcur->_next;
			}
			else
			{
				prev->_next = pcur->_next;
			}
			delete pcur;
			--_n;
			return true;
		}
		prev = pcur;
		pcur = pcur->_next;
	}
	return false;
}

4、完整代码

namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K>
	struct HashFunc //key强转为整型
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//对string类型特殊处理
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash = hash * 31 + e;
			}
			return hash;
		}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:

		HashTable()
		{
			_tables.resize(10);//提前开10个位置
		}

		bool Insert(const pair<K, V>& kv)
		{
			//去冗余
			if (Find(kv.first))
			{
				return false;
			}

			if (_n * 10 / _tables.size() >= 7)//载荷因子达到一定的值进行扩容
			{
				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(2 * _tables.size());
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();//确定映射位置
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();//防止越界
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;
				return true;
			}
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//存储元素个数
	};
}

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

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash = hash * 31 + e;
			}
			return hash;
		}
	};

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

		pair<K, V> _kv;
		HashNode<K, V>* _next;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* pcur = _tables[i];
				while (pcur)
				{
					Node* next = pcur->_next;
					delete pcur;
					pcur = next;
				}
				_tables[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();

			负载因子==1就扩容
			//if (_n == _tables.size())
			//{
			//	HashTable<K, V> newHT;
			//	newHT._tables.resize(2 * _tables.size(), nullptr);
			//	for (int i = 0; i < _tables.size(); i++)
			//	{
			//		Node* pcur = _tables[i];
			//		while (pcur)
			//		{
			//			newHT.Insert(pcur->_kv);
			//			pcur = pcur->_next;
			//		}
			//	}
			//	_tables.swap(newHT._tables);
			//}

			//负载因子==1就扩容
			if (_n == _tables.size())
			{
				vector<Node*> newtables(2 * _tables.size(), nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* pcur = _tables[i];
					while (pcur)
					{
						Node* next = pcur->_next;//记录下一个节点
						size_t hashi = hs(pcur->_kv.first) % newtables.size();//映射新表的相对位置
						pcur->_next = newtables[hashi];//头插
						newtables[hashi] = pcur;
						pcur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}
			Node* newnode = new Node(kv);

			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

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

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* pcur = _tables[hashi];
			Node* prev = nullptr;
			while (pcur)
			{
				if (pcur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = pcur->_next;
					}
					else
					{
						prev->_next = pcur->_next;
					}
					delete pcur;
					--_n;
					return true;
				}
				prev = pcur;
				pcur = pcur->_next;
			}
			return false;
		}
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent.com 删除

c++