哈希：哈希函数 | 哈希概念 | 哈希冲突 | 闭散列 | 开散列

南桥

发布于 2024-09-07 12:55:27

1150

发布于 2024-09-07 12:55:27

文章被收录于专栏：南桥谈编程

unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到

log_2N

，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

unordered_map

unordered_map介绍

介绍文档

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
它的迭代器至少是前向迭代器。

接口说明

unordered_map 的构造

函数声明	功能介绍
unordered_map	构造不同格式的unordered_map对象

unordered_map的容量

函数声明	功能介绍
bool empty() const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数

unordered_map的迭代器

是一个单向迭代器

函数声明	功能介绍
begin	返回unordered_map第一个元素的迭代器
end	返回unordered_map最后一个元素下一个位置的迭代器
cbegin	返回unordered_map第一个元素的const迭代器
cend	返回unordered_map最后一个元素下一个位置的const迭代器

unordered_map的元素访问

函数声明	功能介绍
operator[]	返回与key对应的value，没有一个默认值

unordered_map的查询

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

unordered_map的修改操作

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

unordered_map的桶操作

函数声明	功能介绍
size_t bucket_count()const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const	返回n号桶中有效元素的总个数
size_t bucket(const K& key))	返回元素key所在的桶号

unordered_set文档介绍

set和unordered_set使用方法类似文档介绍

底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构

哈希概念

序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(

log_2 N

)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

哈希也叫做散列，是一种映射，把值和值进行一对一或者一对多关联。

哈希表：使用哈希思想实现的数据结构。一般都是将值和存储位置建立映射关系。

当向该结构中：

插入元素根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

存在的问题：

值很分散时，效率不高
有些值不好映射，比如：string、结构体对象

除留余数法解决了数据分散问题，但是会导致哈希冲突，不同的值可能会映射到相同位置。例如下面10001和11就映射到一位置。

哈希冲突

对于两个数据元素的关键字

k_i

和

k_j

(i != j)，有

k_i

k_j

，但有：Hash(

k_i

) ==Hash(

k_j

)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

解决哈希冲

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。也就是说，自己位置被占了，去抢别的位置。冲突次数越高，效率越低。

寻找下一个空位置：

线性探测

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

插入： 通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。 删除： 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。 扩容： 散列表的载荷因子定义为:α=填入表中的元素个数 / 散列表的长度 负载因子越高，冲突率越高，效率越低；负载因子越小，冲突效率越低，效率就越高，空间利用率就越低。

模拟实现

扩容机制：首先扩容，然后原有的值不能直接拷贝，需要重新映射。

#include<iostream>
#include<vector>
#include<utility>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	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);
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first)) return false;
		//扩容
		if (_n * 10 / _tables.size() >= 7)
		{
			//size_t newsize = _tables.size() * 2;
			//vector<HashData<K, V>> newtables(newsize);
			//for (size_t i = 0; i < _tables.size(); i++)
			//{}

			size_t newsize = _tables.size() * 2;
			HashTable<K, V> newHT;
			newHT._tables.resize(newsize);
			for (size_t 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;
	}

	HashData<K, V>* Find(const K& key)
	{
		size_t hashi = key % _tables.size();
		//线性探测
		while (_tables[hashi]._state != EMPTY)  //如果该位置存在继续往后探测
		{
			if (_tables[hashi]._state == EXIST && _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;
			--_n;
			return  true;
		}
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;  //有效数据个数
};

上述类型是整型，可以直接进行取模运算，但是对于其他类型，例如：string，自定义类型该如何处理？对于其他类型，可以先转换成整型，然后进行映射。注意这里不是类型转换！key不支持强转整型取模，需要自己提供转换成整型的仿函数。在书写代码时，需要增加一个仿函数，用于转换类型：

#include<iostream>
#include<vector>
#include<string>
#include<utility>
using namespace std;

enum State
{
	EMPTY,
	EXIST,
	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;
	}
};

struct StringHashFunc
{
	size_t operator()(const string& key)
	{
		return key[0];
	}
};

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

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first)) return false;
		//扩容
		if (_n * 10 / _tables.size() >= 7)
		{
			//size_t newsize = _tables.size() * 2;
			//vector<HashData<K, V>> newtables(newsize);
			//for (size_t i = 0; i < _tables.size(); i++)
			//{}

			size_t newsize = _tables.size() * 2;
			HashTable<K, V, Hash> newHT;
			newHT._tables.resize(newsize);
			for (size_t 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 == EXIST && _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;
			--_n;
			return  true;
		}
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;  //有效数据个数
};

对于处理string类型时，会出现冲突，因为英文单词中首字母相同的单词有很多，我们可以对一个单词中所有字母的ASII码值进行相加：

struct StringHashFunc
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash += ch;
		}
		return hash;
	}
};

但是这种方法仍然有缺陷，例如：abcd，bcad，aadd这几个的ASII码仍然还是有冲突。

字符串哈希算法

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：

H_i

= (

H_0

i^2

)% m, 或者：

H_i

= (

H_0

i^2

)% m。其中：i =1,2,3…，

H_0

是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

开散列

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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

模拟实现

插入时，需要实现头插：先将待插入的元素插入进去，然后使它变成头结点。

扩容：

方案一：将旧表中的数据通过映射的方式拷贝到新表中，然后再释放掉旧表中的内容，就表中虽然vector数组可以通过析构的方式释放掉，但是对应的接点删除效率不高。

if (_n == _tables.size())
{
	size_t newsize = _tables.size() * 2;
	HashTable<K, V, Hash> newHT;
	newHT._tables.resize(newsize);
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			newHT.Insert(cur->_kv);
			cur = cur->_next;
		}
	}

	_tables.swap(newHT._tables);
}

方案二：将节点从旧表中拿出来，通过映射的方式放在新表中

// 扩容：负载因子为1（平均每个桶下面一个）
			if (_n == _tables.size())
			{
				//方案二：
				vector<Node*> newTables(_tables.size() * 2, nullptr);
				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 % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}

删除：再删除的时候需要考虑删除的数据是头结点还是中间的节点，如果是头结点直接删除即可，中间节点之间让前一个节点指向被删除节点的下一个节点。

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

// 特化
template<>
struct HashFunc<string>
{
	// abcd
	// bcad
	// aadd
	// BKDR
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

bool Erase(const K& key)
{
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
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;
}

完整代码：

namespace gwj_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.resize(10, nullptr);
			_n = 0;
		}

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

					cur = next;
				}

				_tables[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			
			Hash hs;

			// 扩容：负载因子为1（平均每个桶下面一个）
			if (_n == _tables.size())
			{
				//方案一：
				//	size_t newsize = _tables.size() * 2;
				//	HashTable<K, V, Hash> newHT;
				//	newHT._tables.resize(newsize);
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		Node* cur = _tables[i];
				//		while (cur)
				//		{
				//			newHT.Insert(cur->_kv);
				//			cur = cur->_next;
				//		}
				//	}

				//	_tables.swap(newHT._tables);

				//方案二：
				vector<Node*> newTables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						//头插到新表的位置
						size_t hashi = hs(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}

			size_t hashi = hs(kv.first) % _tables.size();
			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* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			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;
	};

	void TestHT1()
	{
		int a[] = { 10001,11,55,24,19,12,31,4,34,44 };
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(32, 32));
		ht.Insert(make_pair(32, 32));

		ht.Erase(31);
		ht.Erase(11);
	}

	void TestHT2()
	{
		HashTable<string, int> ht;
		ht.Insert(make_pair("sort", 1));
		ht.Insert(make_pair("left", 1));
		ht.Insert(make_pair("insert", 1));
	}


}

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

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

函数