【C++进阶】九、哈希表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++进阶】九、哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、哈希概念

二、哈希冲突

三、哈希函数

四、哈希冲突解决

4.1 闭散列（开放定址法）

4.1.1 线性探测

4.1.2 二次探测

4.1.3 研究表明

五、哈希表的闭散列实现

5.1 闭散列哈希表的结构

5.2 闭散列的插入

5.2 闭散列的查找

5.3 闭散列的查找

5.4 哈希表取模问题

5.5 string类型无法取模问题

5.6 完整代码

四、哈希冲突解决

4.2 开散列（链地址法、哈希桶）

六、哈希表的开散列实现（哈希桶）

6.1 哈希桶的结构

6.2 哈希桶的插入

6.3 哈希桶的查找

6.4 哈希桶的删除

6.5 完整代码

七、开散列与闭散列比较

八、哈希表的大小建议是素数

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

一、哈希概念

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

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

当向该结构中：

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

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如，集合{1, 7, 6, 4, 5, 9}

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

二、哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词

比如，按照上述哈希方式，向集合中再次插入元素44，会出现哈希冲突，因为4和44都映射到了哈希值为4的地方

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

发生哈希冲突该如何处理呢？下面讲解

三、哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数：

（1）直接定址法 -- (常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

（2）除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数 p作为除数，按照哈希函数：Hash(key) = key% p(p <= m)，将关键码转换成哈希地址

优点：使用场景广泛，不受限制
缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害

（3）平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

（4）折叠法--(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

（5）随机数法--(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key)，其中random为随机数函数

通常应用于关键字长度不等时采用此法

（6）数学分析法--(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址

例如：

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移
位、前两数与后两数叠加(如1234改成 12+34=46 )等方法

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

四、哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

4.1 闭散列（开放定址法）

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key存放到冲突位置中的 “下一个” 空位置中去

那如何寻找下一个空位置？常见的方式有两种：线性探测和二次探测

4.1.1 线性探测

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

比如上述场景，插入元素44，先通过哈希函数计算哈希地址，哈希地址为4，因此44理论上应该插在哈希地址为4位置，但是该位置已经放了值为4的元素，即发生哈希冲突

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

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

线性探测：

Hi = (H0 + i) % m ( i = 1,2,3,...)

Hi：冲突元素通过线性探测后得到的存放位置，即哈希地址
H0：通过哈希函数对元素的关键码进行计算得到的位置
哈希表表的大小

除留余数法插入过程：

hashi = key % capacity （除留余数法）

hashi：通过哈希函数对元素的关键码进行计算得到的位置，即哈希地址

key：插入的元素

capacity：哈希表的大小

插入值：集合{1, 7, 6, 4, 5, 9}

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

再次插入元素44，发生哈希冲突（采用线性探测）

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加

将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低

因此，为了降低哈希冲突出现的次数，哈希表当中引入了负载因子（载荷因子）：

负载因子（载荷因子） = 表中有效数据个数 / 哈希表的大小

负载因子越大，产出冲突的概率越高，增删查改的效率越低
负载因子越小，产出冲突的概率越低，增删查改的效率越高

注意：哈希冲突是无法避免的，只能降低哈希冲突的概率

对于开放定址法（闭散列），荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的 CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的 hash库，如 Java的系统库限制了荷载因子为 0.75，超过此值将 resize散列表（扩容）

线性探测删除：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素（下面模拟实现再细讲）

线性探测优缺点：

线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低

4.1.2 二次探测

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

产生了哈希冲突，采用二次探测找下一个空位置的方法为：

Hi = (H0 + i^2) % m ( i = 1,2,3,...)

Hi：冲突元素通过线性探测后得到的存放位置，即哈希地址
H0：通过哈希函数对元素的关键码进行计算得到的位置
哈希表表的大小

比如，上面插入的44

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积

二次探测和线性探测一样，采用二次探测也需要关注哈希表的负载因子

4.1.3 研究表明

研究表明：

当表的长度为质数且表负载因子a不超过 0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过 0.5，如果超出必须考虑增容

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

五、哈希表的闭散列实现

注：只采用线性探测

5.1 闭散列哈希表的结构

在闭散列的哈希表中，哈希表每个位置除了存储所给数据之外，还应该存储该位置当前的状态，哈希表中每个位置的可能状态如下：

PTY（无数据的空位置）
EXIST（已存储数据）
DELETE（原本有数据，但现在被删除了）

可以用枚举定义这三个状态

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

哈希表每个位置存储的结构，存储数据使用键值对

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

哈希表需要提供构造函数，默认开 10和空间大小

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

闭散列的哈希表基本结构如下：

//枚举：标识每个位置的状态
	enum State
	{
		EMPTY,
		EXIST,
		DELETE,
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;//默认缺省值为空 EMPTY
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
        HashTable()
			:_n(0)
		{
			_tables.resize(10);//默认开10个空间
		}
		
	private:
		vector<Data> _tables;//利用已有的容器
		size_t _n;//用于记录表中有效数据的个数
	};

记录表中有效数据的个数的原因：用于计算当前哈希表的负载因子，用于判断扩容操作

5.2 闭散列的插入

向哈希表中插入数据的步骤如下：

查找哈希表中是否存在插入的值，若已存在则插入失败
判断当前负载因子是否大于标定负载因子，大于就需要扩容，否则就进行插入
进行插入：计算哈希地址，线性探测查找插入的位置
插入位置的状态设置为EXIST，哈希表中的有效元素个数加一

扩容需要注意：

在将原哈希表的数据插入到新哈希表的过程中，不能只是简单的将原哈希表中的数据对应的挪到新哈希表中，而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置，然后再进行插入

这里标定哈希表的负载因子为0.7，大于0.7则扩容

注意：产生哈希冲突向后进行探测时，一定会找到一个合适位置进行插入，因为哈希表的负载因子是控制在0.7以下的，也就是说哈希表永远都不会被装满

//插入
bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))//查询插入的值是否已经存在
	{
		return false;//存在插入失败
	}

	//大于标定负载因子，就需要扩容
	//这里负载因子设置为 0.7
	if (_n * 10 / _tables.size() > 7)//_n *10 和负载因子0.7*10 的原因是：比如 5 / 10 = 0，因为_tables.size默认开空间为10
	{
		// 旧表数据，重新计算，映射到新表
		HashTable<K, V, Hash> newHT;
		newHT._tables.resize(_tables.size() * 2);
		//将原哈希表当中的数据插入到新哈希表
		for (auto& e : _tables)
		{
			if (e._state == EXIST)//数据存在
			{
				newHT.Insert(e._kv);
			}
		}
		//交换这两个哈希表
		_tables.swap(newHT._tables);
	}

	//没有大于标定负载因子，进行插入
	Hash hf;//仿函数
	size_t hashi = hf(kv.first) % _tables.size();//计算哈希地址，找到插入的位置,除数不能是capacity
	while (_tables[hashi]._state == EXIST)//该位置已被占用
	{
		++hashi;//线性探测
		hashi %= _tables.size();//防止下标超出哈希表范围
	}
	//找到可以插入的位置，将数据插入该位置，并将该位置的状态设置为EXIST
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	++_n;//有效数据个数+1

	return true;
}

5.2 闭散列的查找

查找数据的步骤如下：

通过哈希函数计算出对应插入数据的哈希地址
从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败

注意：在查找过程中，必须找到位置状态为EXIST，并且与key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了

//查找
Data* Find(const K& key)
{
	Hash hf;
	size_t hashi = hf(key) % _tables.size();//计算哈希值，找到哈希值对应的位置
	while (_tables[hashi]._state != EMPTY)
	{
		//若该位置的状态为EXIST，并且key值匹配，则查找成功
		if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];//返回找到数据的地址
		}

		++hashi;//线性探测
		hashi %= _tables.size();//防止下标超出哈希表范围
	}

	return nullptr;//没找到
}

5.3 闭散列的查找

删除哈希表中的元素非常简单，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE即可

//删除
bool Erase(const K& key)
{
	Data* ret = Find(key);//查找该数据是否存在
	if (ret)//存在
	{
		ret->_state = DELETE;
		--_n;//哈希表有效个数 -1
		return true;//删除成功
	}
	else
	{
		return false;//删除失败
	}
}

5.4 哈希表取模问题

哈希表还需提供一个仿函数，也就是上面的第三个模板参数 Hash

template<class K, class V, class Hash = HashFunc<K>>

这个仿函数用于对传入的数据进行强转，因为哈希表需要计算哈希地址，计算哈希地址需要取模操作，取模操作需要的操作数是整型。但是我们不知道传入类型会是什么，所以需要对传入的数据强制类型转换为整型，以便计算哈希地址

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

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

但是这里还有一个问题，如果传入的是字符串，字符串将会出现无法取模的问题

5.5 string类型无法取模问题

字符串无法取模，是哈希问题中最常见的问题

字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址

但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是 4294967295，而众多字符能构成的字符串的种类却是无限的

鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法

博客链接：各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

所以，要解决string取模的问题，需要在原有的仿函数的基础上，对仿函数进行特化

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

//仿函数特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 131;//BKDRHash算法
			hash += ch;
		}
		return hash;
	}
};

5.6 完整代码

//闭散列
namespace CloseHash
{
    //仿函数
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//仿函数特化
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto ch : key)
			{
				hash *= 131;//BKDRHash算法
				hash += ch;
			}
			return hash;
		}
	};
    
	//枚举：标识每个位置的状态
	enum State
	{
		EMPTY,
		EXIST,
		DELETE,
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;//默认缺省值为空 EMPTY
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable()
			:_n(0)
		{
			_tables.resize(10);//默认开10个空间
		}

		//插入
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))//查询插入的值是否已经存在
			{
				return false;//存在插入失败
			}

			//大于标定负载因子，就需要扩容
			//这里负载因子标定为 0.7
			//_n *10 和负载因子0.7*10 的原因是：比如 5 / 10 = 0，因为_tables.size默认开空间为10
			if (_n * 10 / _tables.size() > 7)
			{
				// 旧表数据，重新计算，映射到新表
				//直接新建一张表，开好空间
				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(_tables.size() * 2);
				//将原哈希表当中的数据插入到新哈希表
				for (auto& e : _tables)
				{
					if (e._state == EXIST)//数据存在，进行插入
					{
						newHT.Insert(e._kv);//复用插入函数
					}
				}
				//交换这两个哈希表
				_tables.swap(newHT._tables);
			}

			//没有大于标定负载因子，进行插入
			Hash hf;//仿函数
			size_t hashi = hf(kv.first) % _tables.size();//计算哈希地址，找到插入的位置,除数不能是capacity
			while (_tables[hashi]._state == EXIST)//该位置已被占用
			{
				++hashi;//线性探测
				hashi %= _tables.size();//防止下标超出哈希表范围
			}
			//找到可以插入的位置，将数据插入该位置，并将该位置的状态设置为EXIST
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			//有效数据个数+1
			++_n;

			return true;
		}

		//查找
		Data* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();//计算哈希值，找到哈希值对应的位置
			while (_tables[hashi]._state != EMPTY)
			{
				//若该位置的状态为EXIST，并且key值匹配，则查找成功
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];//返回找到数据的地址
				}

				++hashi;//线性探测
				hashi %= _tables.size();//防止下标超出哈希表范围
			}

			return nullptr;//没找到
		}

		//删除
		bool Erase(const K& key)
		{
			Data* ret = Find(key);//查找该数据是否存在
			if (ret)//存在
			{
				ret->_state = DELETE;
				--_n;//哈希表有效个数 -1
				return true;//删除成功
			}
			else
			{
				return false;//删除失败
			}
		}

	private:
		vector<Data> _tables;//利用已有的容器
		size_t _n;//用于记录表中有效数据的个数
	};

	void TestHash1()
	{
		//注：没有实现迭代器，不方便打印，调试查看即可
		HashTable<int, int> ht;
		int arr[] = { 18, 8, 7, 27, 57, 3, 38, 18 };
		for (auto& e : arr)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(17, 17));
		ht.Insert(make_pair(5, 5));

		cout << ht.Find(7) << endl;
		cout << ht.Find(8) << endl;

		ht.Erase(7);
		cout << ht.Find(7) << endl;
		cout << ht.Find(8) << endl;

	}

	void TestHash2()
	{
		string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		HashTable<string, int> countHT;
		for (auto& e : arr)
		{
			HashData<string, int>* ret =  countHT.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				countHT.Insert(make_pair(e, 1));
			}
		}
	}
}

四、哈希冲突解决

4.2 开散列（链地址法、哈希桶）

开散列概念：

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

开散列也称为哈希桶

比如，插入值：集合{1, 7, 6, 4, 5, 9} ，采用的哈希函数依旧是除留余数法

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

再次插入 44

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

开散列中每个桶中放的都是发生哈希冲突的元素

开散列的哈希表，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：

哈希桶的负载因子可以更大，空间利用率高
哈希桶在极端情况下还有可用的解决方案

哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O(N)

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

可以考虑将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

在这种情况下，就算有十亿个元素全部冲突到一个哈希桶中，我们也只需要在这个哈希桶中查找30次左右，这就是所谓的“桶里种树

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++

为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构，比如在JAVA中比较新一点的版本中，当桶当中的数据个数超过8时，就会将该桶当中的单链表结构换成红黑树结构，而当该桶当中的数据个数减少到8或8以下时，又会将该桶当中的红黑树结构换回单链表结构

但有些地方也会选择不做此处理，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大

unordered_set 和 unordered_map 的底层采用的是哈希桶（开散列）

六、哈希表的开散列实现（哈希桶）

6.1 哈希桶的结构

在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点

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)
	{}
};

哈希桶需要提供构造函数

//构造
HashTable()
	:_n(0)
{
	_tables.resize(10);//默认开10个空间
}

哈希桶需要提供析构函数，用于释放节点空间

//析构
~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;
	}
}

开散列的哈希表基本结构如下：

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()
		:_n(0)
	{
		_tables.resize(10);//默认开10个空间
	}

	//析构
	~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;
		}
	}

private:
	vector<Node*> _tables;//指针数组, 哈希表
	size_t _n;//用于记录表中有效数据的个数
};

6.2 哈希桶的插入

向哈希桶中插入数据的步骤如下：

查找哈希表中是否存在插入的值，若已存在则插入失败
判断当前负载因子是否大于标定负载因子，大于就需要扩容，否则就进行插入
进行插入：计算哈希地址，进行头插
哈希表中的有效元素个数加一

这里标定哈希表的负载因子为0.7，大于0.7则扩容

这里的扩容，只需对旧表的节点重新计算哈希地址，插入到新表，然后再交换两个表即可，无需重新新建节点

原因：在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要创建相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举，直接利用已有节点即可

//插入
bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))//查询插入的值是否已经存在
	{
		return false;//存在插入失败
	}

	//大于标定负载因子，就需要扩容
	//这里负载因子标定为 1
	if (_tables.size() == _n)
	{
		//创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍
		vector<Node*> newTables;
		newTables.resize(_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 = Hash()(cur->_kv.first) % newTables.size();
				//节点头插到新表
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;

				cur = next;//取该桶的下一个节点
			}
			//该桶取完后将该桶置空
			_tables[i] = nullptr;
		}
		//交换这两个哈希表
		_tables.swap(newTables);
	}

	//不需要扩容，进行插入
	size_t hashi = Hash()(kv.first) % _tables.size();
	//头插
	Node* newNode = new Node(kv);
	newNode->_next = _tables[hashi];
	_tables[hashi] = newNode;
	//有效数据+1
	++_n;

	return true;
}

6.3 哈希桶的查找

查找数据的步骤如下：

通过哈希函数计算出对应插入数据的哈希地址
通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行

//查找
Node* Find(const K& key)
{
	size_t hashi = Hash()(key) % _tables.size();//计算key的哈希地址
	Node* cur = _tables[hashi];
	//遍历这个桶进行查找
	while (cur)
	{
		if (cur->_kv.first == key)//查找成功
		{
			return cur;
		}
		cur = cur->_next;
	}
	//该桶遍历完，查找失败
	return nullptr;
}

6.4 哈希桶的删除

删除数据的步骤如下：

过哈希函数计算出对应的哈希桶编号
遍历对应的哈希桶，寻找待删除结点
若找到了待删除结点，进行删除，哈希表中的有效元素个数减一
没找到删除失败

//删除
bool Erase(const K& key)
{
	size_t hashi = Hash()(key) % _tables.size();//计算key的哈希地址
	Node* prev = nullptr;//用于记录 cur的前一个节点
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)//找到需要删除的节点
		{
			if (cur == _tables[hashi])//头删
			{
				_tables[hashi] = cur->_next;
			}
			else//中间删除
			{
				prev->_next = cur->_next;
			}
			delete cur;
			--_n;

			return true;
		}
		else//迭代遍历
		{
			prev = cur;
			cur = cur->_next;
		}
	}
	//删除失败
	return false;
}

6.5 完整代码

//开散列（哈希桶）
namespace BucketHash
{
    
    //仿函数
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
 
	//仿函数特化
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto ch : key)
			{
				hash *= 131;//BKDRHash算法
				hash += ch;
			}
			return hash;
		}
	};

	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()
			:_n(0)
		{
			_tables.resize(10);//默认开10个空间
		}

		//析构
		~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;//存在插入失败
			}

			//大于标定负载因子，就需要扩容
			//这里负载因子标定为 1
			if (_tables.size() == _n)
			{
				//创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍
				vector<Node*> newTables;
				newTables.resize(_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 = Hash()(cur->_kv.first) % newTables.size();
						//节点头插到新表
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;//取该桶的下一个节点
					}
					//该桶取完后将该桶置空
					_tables[i] = nullptr;
				}
				//交换这两个哈希表
				_tables.swap(newTables);
			}

			//不需要扩容，进行插入
			size_t hashi = Hash()(kv.first) % _tables.size();
			//头插
			Node* newNode = new Node(kv);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			//有效数据+1
			++_n;

			return true;
		}

		//查找
		Node* Find(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();//计算key的哈希地址
			Node* cur = _tables[hashi];
			//遍历这个桶进行查找
			while (cur)
			{
				if (cur->_kv.first == key)//查找成功
				{
					return cur;
				}
				cur = cur->_next;
			}
			//该桶遍历完，查找失败
			return nullptr;
		}

		//删除
		bool Erase(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();//计算key的哈希地址
			Node* prev = nullptr;//用于记录 cur的前一个节点
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)//找到需要删除的节点
				{
					if (cur == _tables[hashi])//头删
					{
						_tables[hashi] = cur->_next;
					}
					else//中间删除
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;

					return true;
				}
				else//迭代遍历
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			//删除失败
			return false;
		}
	private:
		vector<Node*> _tables;//指针数组, 哈希表
		size_t _n;//用于记录表中有效数据的个数
	};

	void TestHash1()
	{
		HashTable<int, int> ht;
		int arr[] = { 18, 8, 7, 27, 57, 3, 38, 18 , 13, 4};
		for (auto& e : arr)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(17, 17));
		ht.Insert(make_pair(5, 5));

		cout << ht.Find(7) << endl;
		cout << ht.Find(8) << endl;

		ht.Erase(7);
		cout << ht.Find(7) << endl;
		cout << ht.Find(8) << endl;
	}

	void TestHash2()
	{
		string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		HashTable<string, int> countHT;
		for (auto& e : arr)
		{
			auto ret = countHT.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				countHT.Insert(make_pair(e, 1));
			}
		}
	}
}

七、开散列与闭散列比较

使用开散列需要增加链接指针，似乎增加了存储开销。事实上：由于闭散列必须保持大量的空闲空间以确保搜索效率，如二次探查法要求负载因子a <= 0.7，而表中所余空间又比指针大的多，所以使用开散列反而比闭散列节省存储空间

八、哈希表的大小建议是素数

使用除留余数法时，哈希表的大小最好是素数，这样能够减少哈希冲突产生的次数

每次增容时让哈希表的大小增大两倍，那么增容后哈希表的大小就不是素数了。因此我们可以将需要用到的素数序列提前用一个数组存储起来，当我们需要增容时就从该数组当中进行获取就行了

实现如下：

inline unsigned long __stl_next_prime(unsigned long n)
{
	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
	};

	for (int i = 0; i < __stl_num_primes; ++i)
	{
		if (__stl_prime_list[i] > n)
		{
			return __stl_prime_list[i];
		}
	}

	return __stl_prime_list[__stl_num_primes - 1];
}

SGI_3.0版本就是这种扩容方法

c++ 哈希表,C嘎嘎,# 高阶数据结构（C++版）,# STL（C++）,散列表,数据结构,哈希算法,c++