博客

手撕哈希表（HashTable）——C++高阶数据结构详解

  • Post author:
  • Post category:其他


目录



传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎米娜桑来指点江山哦（QQ：1319365055）


🎉🎉非科班转码社区诚邀您入驻🎉🎉


小伙伴们，打码路上一路向北，彼岸之前皆是疾苦


一个人的单打独斗不如一群人的砥砺前行


这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！

社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）

直达：

社区链接点我

在这里插入图片描述



概念🤔

哈希简单来说就是把任意输入通过特定方式（hash函数） 处理后 生成一个值。这个值等同于存放数据的地址，这个地址里面再吧输入的数据进行存储。

哈希表

也叫散列表，哈希表是一种

数据结构

，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为

O(1)

，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器。

在普通的顺序结构或者平衡树中，因为关键码内容和存储位置之间没有对应关系，所以查找一个元素必须经过关键码的多次比较，顺序结构中查找的时间复杂度为 O(N)，平衡树中查找的时间复杂度为树的高度 O(logN) ；

而最理想的搜索方法是可以不经过任何比较，直接从表中得到要搜索的元素，即查找的时间复杂度为 O(1) 的哈希

！

哈希表采用的是一种转换思想，一个重要的概念就是如何将关键字（key）转换成数组下标进行映射存储。

这种转换思想就是转换函数，哈希方法中称为哈希（散列）函数，构造出来的结构称为哈希表（散列表）。

在这里插入图片描述


举个栗子：

给定集合 {1, 7, 6, 4, 5, 9}，将哈希函数设置为：h a s h ( k e y ) = k e y % c a p a c i t y ，其中capacity为存储元素空间的总大小。

若我们将该集合存储在 capacity 为10的哈希表中，则各元素存储位置对应如下：

在这里插入图片描述

在查找时只需要对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置取出元素进行比较，若关键码相等则搜索成功。



哈希碰撞🤔

也叫哈希冲突，指不同关键字通过相同哈希函数计算出了相同的哈希地址，比如在上述例子中，再将元素 11 插入当前的哈希表就会产生哈希冲突。 因为元素11通过该哈希函数得到的哈希地址与元素1相同，都是下标为1的位置：

hash(11)=11 % 10 = 1

在这里插入图片描述


那么这种冲突是否可以避免呢？

答案是只能缓解，不可避免。

由于哈希函数的原理是将输入空间一个较大的值映射到一个较小的 Hash 空间内，而 Hash空间一般远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成同一输出的情况。


抽屉原理

在这里插入图片描述

它是组合数学中一个重要的原理，桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。抽屉原理的含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。



哈希函数🤔

不合理的哈希函数就是引发哈希冲突的重要原因，哈希函数设计的越精妙，产生哈希冲突的可能性越低！

哈希函数的设计遵从

三大原则

：


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

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

3. 哈希函数应该比较简单。

常见的哈希函数有：


  1. 直接定址法

取关键字的线性函数作为哈希地址：

Hash(Key) = A ∗ Key + B

优点：每个值都有一个唯一位置，效率很高，每个都是一次就能找到。

缺点：使用场景比较局限，通常要求数据是整数，范围比较集中。

使用场景：适用于整数，且数据范围比较集中的情况。


  1. 除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数

Hash(Key) = Key % p (p <= m)

，将关键码转换成哈希地址

优点：使用广泛，不受限制

缺点：需要解决哈希冲突，冲突越多，效率下降越厉害


  1. 平方取中法

    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址（偶数位的数不妨可以多取一位）

使用场景：不知道关键字分布且关键字位数不多


  1. 折叠法

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

使用场景：不知道关键字分布且关键字位数多


  1. 随机数法

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

使用场景：各关键字位数不等


  1. 数字分析法

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

举个栗子，假设要存储某家公司员工信息，如果用手机号作为关键字，那么极有可能前 7 位都是相同的，那么我们可以选择后 4 位作为哈希地址

使用场景：关键字位数比较大，或事先知道关键字的分布且关键字的若干位分布较均匀的情况



解决哈希冲突🤔

解决哈希冲突有两种常见的方法：

闭散列

和

开散列



闭散列😎

也叫

开放定址法

，在发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的 “下一个” 空位置中去，寻找“下一个位置”的方式多种多样，常见的方式有以下两种：



  1. 线性探测

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

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

H0 ：通过哈希函数对元素的关键码进行计算得到的位置。

Hi：冲突元素通过线性探测后得到的存放位置。

m ：表的大小。

所以开放定址法的

优点

就是实现简单，而

缺点

也显而易见就是冲突一旦发生，极有可能造成数据堆积，不同关键字占据可利用空间，导致查找时需要多次比较，即所谓的

踩踏效应

，搜索效率下降。

随着数据的增多，哈希冲突的可能性增加，有可能一个位置会发生多次哈希冲突，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低，于是哈希表中又引入了

负载因子（载荷因子）

：

负载因子 = 表中有效数据个数 / 空间的大小

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

负载因子越小，产出冲突的概率越低，增删查改的效率越高，但是越小也意味着空间利用率越低，此时大量空间可能被浪费。

因此我们在闭散列（开放定址法）对负载因子的标准定在了 0.7~0.8，一旦大于 0.8 会导致查表时缓存未命中率呈曲线上升；这就是为什么有些哈希库都有规定的负载因子，Java 的系统库就将负载因子定成了 0.75，超过 0.75 就会自动扩容。



  1. 二次探测

二次探测的根本目的是为了避免线性探测可能产生的踩踏效应，他在寻找空位置的方法上进行了改造：

Hi = (H0 + i

2

) % m (i = 1,2,3,…)

H0：通过哈希函数对元素的关键码进行计算得到的位置。

Hi：冲突元素通过二次探测后得到的存放位置。

m：表的大小。

采用二次探测相比线性探测而言，哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积，当然二次探测也需要考虑负载因子，因此不能看出闭散列最大的缺点就是空间利用率低，其实这也是哈希的老病根。



开散列😎

开散列，又叫链地址法（拉链法），

首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶（bucket），各个桶中的元素通过一个链表连接，各链表的头结点存储在哈希表中。

在这里插入图片描述

相比闭散列那种报复社会型的小藓钕占座，开散列就显得格局打开了，既然没法坐那我就吊扶手。其中链表的头结点存储在哈希表中的方式，

不会影响与自己哈希地址不同的元素的增删查改的效率

，因此开散列的负载因子相比闭散列而言，可以稍微大一点。闭散列负载因子不能超过1，一般建议控制在 [0.0, 0.7] 之间；

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

。

而且开散列相对闭散列不仅仅只有空间利用率高的优点，还有它处理某些极端情况的能力，比如根据哈希函数计算的哈希地址全部在同一个地址，就是全员冲突，此时效率退化到了 O(N)：

在这里插入图片描述

此时我们可以将这个单链表更改为红黑树结构，哈希表中存红黑树的根节点，这样就算进来 10 亿个元素也只需要查找 30 次：

在这里插入图片描述

结构转换其实和负载因子有点相似，比如 Java 新版本中当桶中元素达到 8 个以上就会将单链表换成红黑树，小于等于 8 个再换回单链表；当然有些地方也不采用转换红黑树，而是到达一定上限后进行哈希扩容，此时再将数据重新映射，冲突的数据也会相对减少。



闭散列实现🤔

首先我们应该知道在闭散列的哈希表中，每个位置除了存储所给数据之外，还应该存储该位置当前的状态，

那么状态的存在意义是什么？

比如我需要在哈希表中查找一个数据，这个数据我用哈希函数算出来他的位置是 1 ，但是我们不知道是不是存在哈希冲突，如果冲突就会向后偏移，我们就需要从 1 这个位置开始向后遍历，但是万万不能遍历完整个哈希表，这样就失去了哈希原本的意义，只需要遍历到一个空位置就可以说明他不存在，即可结束。

那如何标识一个空位置？用数字 0 吗？那如果我们要存储的元素就是 0 怎么办？

因此我们必须要单独给每个位置设置一个状态字段

。

但是如果设置存在和不存在两种状态，那么遇到下面这种情况时就会出现错误：

假设哈希表当中箭头所指处有元素存在并将其删除，此时我们要判断当前哈希表当中是否存在元素 101，当我们从 1 下标开始往后找到 2 下标（空位置）时，我们按照原来的逻辑就会停下来，此时并没有找到元素 101！

在这里插入图片描述

这样一来，当我们在哈希表中查找元素的过程中，若当前位置的元素与待查找的元素不匹配，但是当前位置的状态是EXIST或是DELETE，那么我们都应该继续往后进行查找，而当我们插入元素的时候，可以将元素插入到状态为空或是已删除的位置

由此我们需要三个状态：

EMPTY（无数据的空位置，闭散列的查找终点）

EXIST（已存储数据）

DELETE（原本有数据现删除了，非终点查找时跳过）

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

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:
	//...
private:
	vector<HashData<K, V>> _table;
	size_t _n = 0; //哈希表中的有效元素个数
};



数据插入😎

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

  1. 查找该键值对是否存在，存在则插入失败
  2. 判断是否需要调整哈希表大小，大小为 0 或者负载因子过大应及时调整

哈希表的调整方式如下：

  1. 若哈希表的大小为0，则将哈希表的初始大小设置为10。
  2. 若哈希表的负载因子大于0.7，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据重新映射到新哈希表，最后将原哈希表与新哈希表交换即可
  1. 插入键值
  2. 有效元素个数 +1 
bool Insert(const pair<K, V>& kv)
{
	HashData<K, V>* ret = Find(kv.first);
	if (ret) //如果已经存在该键值对（不允许数据冗余）
	{
		return false; //插入失败
	}

	//判断是否需要调整大小
	if (_table.size() == 0) //哈希表大小为0
	{
		_table.resize(10); //设置初始空间大小
	}
	else if ((double)_n / (double)_table.size() > 0.7) //负载因子>0.7需要增容
	{
		//增容
		//创建新的哈希表，大小设置为原哈希表的2倍
		HashTable<K, V> newHT;
		newHT._table.resize(2 * _table.size());
		//将原哈希表当中的数据插入到新哈希表
		for (auto& e : _table)
		{
			if (e._state == EXIST)
			{
				newHT.Insert(e._kv);
			}
		}
		//交换两个哈希表
		_table.swap(newHT._table);
	}

	//键值对插入
	//通过哈希函数计算哈希地址
	size_t start = kv.first%_table.size(); //注意除数不是capacity
	size_t index = start;
	size_t i = 1;
	int base = index;
	//找到一个状态为EMPTY或DELETE的位置
	while (_table[index]._state == EXIST)
	{
		index = start + i; //线性探测
		//index = start + i*i; //二次探测
		index %= _table.size(); //防止下标超出哈希表范围
		i++;
	}
	//数据插入，并将状态设置为EXIST
	_table[index]._kv = kv;
	_table[index]._state = EXIST;
	
	//哈希表中的有效元素个数加一
	_n++;
	return true;
}



数据查找😎

哈希表中数据的查询首先需要验证此时哈希表的大小是否是 0，是 0 则查找失败，然后再根据哈希函数计算出哈希地址，对应哈希地址在哈希表中进行遍历查找，遇到 EMPTY 位置还没找到则查找失败。

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

HashData<K, V>* Find(const K& key)
{
	if (_table.size() == 0) //大小为0，查找失败
	{
		return nullptr;
	}

	size_t start = key % _table.size(); //计算哈希地址
	size_t index = start;
	size_t i = 1;
	while (_table[index]._state != EMPTY)
	{
		//若该位置的状态为EXIST，并且key值匹配，则查找成功
		if (_table[index]._state == EXIST&&_table[index]._kv.first == key)
		{
			return &_table[index];
		}
		index = start + i; //线性探测
		//index = start + i*i; //二次探测
		index %= _table.size(); //防止下标超出哈希表范围
		i++;
	}
	return nullptr; //查找失败
}



数据删除🤔

其实哈希表的数据删除是非常简单的，我们的基本思想就是进行伪删除，也就是我们改变他的状态码即可，待删除位置置为 DELETE 即可，这样既不用大费周章的操作数据，也不会造成空间的浪费： 

bool Erase(const K& key)
{
	//查看是否存在
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		//若存在，所在位置的状态改为DELETE即可
		ret->_state = DELETE;
		//有效元素个数减一
		_n--;
		return true;
	}
	return false;
}



开散列实现🤔

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

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

因为开散列的优势，在发生哈希冲突时不需要进行任何探测来跳到下一个未占用的地址，直接挂桶即可，所以开散列不需要状态码成员，其他的流程就与闭散列一样了，需要根据负载因子来判断当前是否进行哈希增容，且时刻记录当前表中的有效元素个数： 

typedef HashNode<K, V> Node;//typedef方便后续操作
template<class K, class V>
class HashTable
{
public:
	//...
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //有效元素个数
};



插入数据😎

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

查看哈希表中是否存在该键值的键值对，若已存在则插入失败。判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整，将键值对插入哈希表，最后哈希表中的有效元素个数加一

实际操作中为了降低时间复杂度，在增容时取结点都是从单链表的表头开始向后依次取的，在插入结点时也是直接将结点头插到对应单链表

将键值对插入哈希表的具体步骤如下：

  1. 通过哈希函数计算出对应的哈希地址。
  2. 若产生哈希冲突，则直接将该结点头插到对应单链表即可 
bool Insert(const pair<K, V>& kv)
{
	Node* ret = Find(kv.first);
	if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
	{
		return false;
	}
	//判断是否需要调整大小
	if (_n == _table.size()) //哈希表的大小为0或负载因子超过1
	{
		//增容
		//创建新的哈希表，大小设置为原哈希表2倍（若哈希表大小为0，则初始大小设置为10）
		vector<Node*> newtable;
		size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
		newtable.resize(newsize);
		//将原哈希表当中的结点插入到新哈希表
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i])
			{
				Node* cur = _table[i];
				while (cur) //结点取完为止
				{
					Node* next = cur->_next; 
					size_t index = cur->_kv.first % newtable.size(); //哈希函数计算桶编号index（除数不能是capacity）
					//头插到编号为index的桶中
					cur->_next = newtable[index];
					newtable[index] = cur;

					cur = next;
				}
				_table[i] = nullptr; //取完后置空
			}
		}
		//交换两个哈希表
		_table.swap(newtable);
	}

	//键值对插入
	size_t index = kv.first % _table.size(); //哈希函数计算出桶编号index（除数不能是capacity）
	Node* newnode = new Node(kv);
	//头插到编号为index的桶中
	newnode->_next = _table[index];
	_table[index] = newnode;

	//有效元素个数加一
	_n++;
	return true;
}



查找数据😎

开散列查找数据的方法和闭散列的查找方法是一样的： 

HashNode<K, V>* Find(const K& key)
{
	if (_table.size() == 0) //哈希表大小为0，查找失败
	{
		return nullptr;
	}

	size_t index = key % _table.size(); //哈希函数计算出哈希桶编号 index（除数不能是capacity）
	HashNode<K, V>* cur = _table[index];
	while (cur) 
	{
		if (cur->_kv.first == key) //查找成功
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr; //查找失败
}



数据删除😎

开散列查找数据的方法和闭散列的删除方法是一样的： 

bool Erase(const K& key)
{
	//哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
	size_t index = key % _table.size();
	Node* prev = nullptr;
	Node* cur = _table[index];
	while (cur)
	{
		if (cur->_kv.first == key) //key值匹配，则查找成功
		{
			if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
			{
				_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
			}
			else //待删除结点不是第一个结点
			{
				prev->_next = cur->_next; 
			}
			delete cur; 
			//删除后，有效元素个数减一
			_n--;
			return true; //删除成功
		}
		prev = cur;
		cur = cur->_next;
	}
	return false; //删除失败
}



利用素数来规定哈希表大小🤔


其实哈希表在使用除留余数法时，为了减少哈希冲突的次数，很多地方都使用了素数来规定哈希表的大小

下面用合数（非素数）10和素数11来进行说明。

合数10的因子有：1，2，5，10。

素数11的因子有：1，11。

我们选取下面这五个序列：

间隔为1的序列：s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

间隔为2的序列：s2 = {2, 4, 6, 8,10, 12, 14, 16, 18, 20}

间隔为5的序列：s3 = {5, 10, 15, 20, 25, 30, 35, 40,45, 50}

间隔为10的序列：s4 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

间隔为11的序列：s5 = {11, 22, 33, 44, 55, 66, 77, 88, 99, 110}

对这几个序列分别放进哈希表，分别观察，不难得出他们的规律：

  1. 如果一个序列中，每个元素之间的间隔为1，那么不管哈希表的大小为几，该序列插入哈希表后都是均匀分布的
  2. 如果一个序列中，每个元素之间的间隔刚好是哈希表大小或哈希表的倍数，他们将全部产生冲突
  3. 如果一个序列中，序列的间隔恰好是哈希表大小的因子，那么哈希表的分布就会产生间隔，反之则不会。


综上所述，某个随机序列当中，每个元素之间的间隔是不定的，为了尽量减少冲突，我们就需要让哈希表的大小的因子最少，此时素数就可以视为最佳方案。



实现方案😎

很明显如果还是采用传统的 2 倍扩容就会不符合素数大小的要求，所以我们不妨直接将素数大小存储在数组里，我们规定下面这个数组即可，其中元素近似 2 倍增长： 

const size_t primeList[PRIMECOUNT] =
{
	53ul, 97ul, 193ul, 389ul, 769ul,
	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};

在扩容时直接求取下一个素数即可： 

size_t GetNextPrime(size_t prime)
{
	const int PRIMECOUNT = 28;
	size_t i = 0;
	for (i = 0; i < PRIMECOUNT; i++)
	{
		if (primeList[i] > prime)
			return primeList[i];
	}
	return primeList[i];
}

aqa 芭蕾 eqe 亏内，代表着开心代表着快乐，ok 了家人们


版权声明：本文为qq_61500888原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。