【C++详解】——哈希unordered系列关联式容器底层结构——Hash闭散列哈希表模拟实现哈希桶模拟实现

Posted on by hackdl

目录

unordered系列关联式容器

unordered_map 

unordered_map的接口说明

1.unordered_map的构造

 2.unordered_map的容量

3.迭代器相关 

4.unordered_map的元素访问

5. unordered_map的查询

6.unordered_map的修改操作

unordered_set

性能测试

底层结构——Hash

哈希概念 

哈希冲突 

哈希函数 

1.直接定址法（常用）

2.除留余数法（常用）

3.平方取中法

4.折叠法

5.随机数法

哈希冲突的处理 

闭散列 

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

闭散列哈希表模拟实现

哈希表的结构 

 插入操作

查找操作

删除操作

哈希桶模拟实现

哈希表的结构 

插入操作

查找操作

删除操作

unordered系列关联式容器

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

unordered_multimap和unordered_multiset可查看详细文档
cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map

unordered_map 

​ 

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

unordered_map的接口说明

1.unordered_map的构造

功能：构造不同格式的unordered_map对象

​

 2.unordered_map的容量

empty（）：检测unordered_map是否为空

size（）：获取unordered_map内有效元素的个数

​

3.迭代器相关 

​ 

4.unordered_map的元素访问

operator[]:返回与key对应的value，没有一个默认值 

​

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶
中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，
将key对应的value返回。

5. unordered_map的查询

 find（）：返回key在哈希桶中的位置

count（）：返回哈希桶中关键码为key的键值对的个数

​

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

6.unordered_map的修改操作

insert（）：向容器中插入键值对

erase（）：删除容器中的键值对

clear（）：清空容器中有效元素的个数

swap（）：交换两个容器中的元素 

​

unordered_set

unordered_set和unordered_map的使用方式基本一致，主要差异在于set当中存的是key，而map当中存的是key-value的键值对，对于unordered_set的详细介绍可以参考下面的文档链接。

https://cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set

性能测试

我相信不少人认为基于红黑树实现的map和set的效率已经很高了，stl为什么还要多写两个容器呢。下面就让我们用代码测试一下，unordered系列容器的效率如何，它们的优点在哪里。

测试代码：我们先生成N个随机数，然后将生成的随机数先存储到vector中，接下来我们就可以把vector的数据插入到map、set以及unordered_map、unordered_set中，这样就保证了每个容器中的元素都是相同的，确保实验的准确性。同时我们还可以通过给生成的随机数+i的方式，减少生成数据的重复性。

int main()
{
	const size_t N = 1000000;

	unordered_set us;
	set s;

	vector v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i

运行代码，有如下结果：

​

【结论】：综合各种场景，unordered系列综合性能是更好的，尤其是find查找的效率，性能一骑绝尘。但同时也不要小看map和set，毕竟基于红黑树实现的它们还拥有有序这一优势。因此，当选择一个容器使用时，要注意其应用的具体环境。

底层结构——Hash

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。下面，我将介绍哈希的具体原理。

哈希概念 

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

向该结构当中插入和搜索元素的过程如下：

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

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

例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小 

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
但是按照上述哈希方式，向集合中插入元素44，会出现什么问题？ 

哈希冲突 

对于两个数据元素的关键字，经过哈希函数转换后映射到了哈希表中的同一个位置，导致无法确定后一个key的存储位置。即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢？

哈希函数 

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

哈希函数设计的原则：

  1. 哈希函数的定义域必须包括需要存储的全部关键码，且如果散列表允许有m个地址，其值域必须在0到m-1之间。
  2. 哈希函数计算出来的地址能均匀分布在整个空间中。
  3. 哈希函数应该比较简单。

1.直接定址法（常用）

取关键字的某个线性函数为哈希地址：Hash (Key) = A ∗ Key + B Hash(Key)=A*Key+BHash(Key)=A∗Key+B。

优点：每个值都有一个唯一位置，效率很高，每个都是一次就能找到。
缺点：使用场景比较局限，通常要求数据是整数，范围比较集中。
使用场景：适用于整数，且数据范围比较集中的情况。

2.除留余数法（常用）

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：H a s h ( K e y ) = K e y % p ( p

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

3.平方取中法

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址。

使用场景：不知道关键字的分布，而位数又不是很大的情况。

4.折叠法

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

使用场景：折叠法适合事先不需要知道关键字的分布，或关键字位数比较多的情况。

5.随机数法

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

使用场景：通常应用于关键字长度不等时。

注意：哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是当数据量过大时，任何哈希函数都无法避免哈希冲突。

哈希冲突的处理 

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

闭散列 

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

那如何寻找下一个空位置呢，常见的方式有下面两种：

1.线性探测

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

Hashi = key % size + i    （i=0，1，2，3…）

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

key：冲突元素

size：HashTable的大小

例如，我们用除留余数法将序列{3，5，33，16，7，4}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：

但是随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加。比如当我们后面要插入4的时候。

我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。介于此，哈希表当中引入了负载因子

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

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

例如，我们将哈希表的大小改为20，可以看到在插入相同序列时，产生的哈希冲突会有所减少：

但负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容。

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

2.二次探测

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

Hashi = key % size + i*i    （i=0，1，2，3…）

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

key：冲突元素

size：HashTable的大小

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

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

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

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

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

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

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

哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率为O(N)。这时，我们可以考虑将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中。

闭散列哈希表模拟实现

哈希表的结构 

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

//我们可以用枚举定义这三个状态
enum State {
		EMPTY, //无数据的空位置
		EXIST, //已存储数据
		DELETE //原来存储过数据，现在已经删除
	};

 如果我们不在哈希表中存储该位置的状态，那么就无法同时实现哈希表插入过程中的线性探测和查找函数。即闭散列哈希表必须要存储当前位置的状态。比如下面的场景：

为了方便HashTable内存储的每一个数据都同时包含数据信息和状态信息，我们可以给待插入的数据定义一个结构体。

闭散列的哈希表中的每个位置存储的结构，应该包括所给数据和该位置的当前状态。

template
	struct HashData
	{
		pair _kv; //数据
		State _state = EMPTY;//位置状态，默认设置为空
	};

对于HashTable，我们可以顶一个vector来存储数据，而为了在插入元素时好计算当前哈希表的负载因子，我们还应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。

//哈希表
template
class HashTable
{
public:
	//...
private:
	vector> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

 插入操作

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

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

其中，哈希表的调整方式如下：

  • 若哈希表的大小为0，则将哈希表的初始大小设置为10。
  • 若哈希表的负载因子大于0.7，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。

注意： 在将原哈希表的数据插入到新哈希表的过程中，不能只是简单的将原哈希表中的数据对应的挪到新哈希表中，而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置，然后再进行插入。扩容时，不能对vector原地扩容，否则寻址就乱了。

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

  1. 通过哈希函数计算出对应的哈希地址。
  2. 若产生哈希冲突，则从哈希地址处开始，采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。
  3. 将键值对插入到该位置，并将该位置的状态设置为EXIST。

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

bool Insert(const pair& kv)
{
	if (Find(kv.first))
		return false;

	//负载因子：填入表中的元素个数/散列表的长度
	// 负载因子大于0.7时扩容
	//先检测是否需要扩容
	if (_tables.size() == 0
		|| _n * 10 / _tables.size() >= 7)
	{
		//扩容时，不能直接扩容，否则寻址就乱了
		//先将旧表重新映射到新表
		size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		HashTable newHT;
		newHT._tables.resize(newsize);
		for (auto& data : _tables)
		{
			if (data._state == EXIST)
			{
				newHT.Insert(data._kv);
			}
		}
		_tables.swap(newHT._tables);
	}
	//插入过程
	size_t hashi = kv.first % _tables.size();
	size_t i = 1;
	size_t index = hashi;
	while (_tables[index]._state == EXIST)
	{
		//线性探测
		index = hashi + i;
		++i;
	}
    _tables[index]._kv = kv;
    _tables[index]._state = EXIST;
    _n++;
	return true;
}

查找操作

在哈希表中查找数据的步骤如下：

  1. 先判断哈希表的是否为空，空表就不用再进行查找，直接返回空即可。
  2. 通过哈希函数计算出对应的哈希地址。
  3. 从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
HashData* Find(const K& key)
{
	if (_tables.size() == 0)
	{
		return nullptr;
	}
	//线性探测
	size_t hashi = key % _tables.size();
	size_t i = 1;
	size_t index = hashi;
	while (_tables[index]._state != EMPTY)
	{
		if (_tables[index]._state == EXIST
			&& _tables[index]._kv.first == key)
		{
			return &_tables[index];
		}
		index = hashi + i;
		index %= _tables.size(); //越界后则从头开始找
		++i;

		//找了一圈后，说明没找到
		if (index == hashi)
		{
			break;
		}

	}
	return nullptr;
}

 【注意】：找到时最好返回该节点的指针。

删除操作

删除哈希表中的元素非常简单，实现了find函数删除操作时可以直接套用，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。

在哈希表中删除数据的步骤如下：

  1. 查看哈希表中是否存在该键值的键值对，若不存在则删除失败。
  2. 若存在，则将该键值对所在位置的状态改为DELETE即可。
  3. 哈希表中的有效元素个数减一。

注意： 删除元素时没必要将该位置的数据清0，只需要将该元素所在状态设为DELETE，这么做并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖。

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

哈希桶模拟实现

哈希表的结构 

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

struct HashNode
{
	HashNode* _next;
	T _data;
	HashNode(const T& data)
		:_next(nullptr)
		,_data(data)
	{}
};

与闭散列的哈希表不同的是，在实现开散列的哈希表时，我们不用为哈希表中的每个位置设置一个状态字段，因为在开散列的哈希表中，我们将哈希地址相同的元素都放到了同一个哈希桶中，并不需要经过探测寻找所谓的“下一个位置”。

哈希表的开散列实现方式，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。

//哈希表
template
class HashTable
{
public:
	//...
private:
	vector _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

插入操作

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

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

其中，哈希表的调整方式如下：

  • 若哈希表的大小为0，则将哈希表的初始大小设置为10。
  • 若哈希表的负载因子已经等于1了，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。

使用哈希桶时负载因子可以大于1
        负载因子越大，冲突的概览越高，查找效率越低，空间利用率越高
        负载因子越小，冲突的概览越低，查找效率越高，空间利用率越低（空间换时间）

【注意】 在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要创建相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举。

扩容过程：直接将原表中的节点插入到新表即可，不用拷贝新的节点。

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

  1. 通过哈希函数计算出对应的哈希地址。
  2. 若产生哈希冲突，则直接将该结点头插到对应单链表即可。
bool Insert(const T& data)
	{
		KeyOfT kot;
		if (Find(kot(data)))
		{
			return false;
		}
		//先检测是否需要扩容
		
		if (_tables.size() == 0 || _n == _tables.size()) //在这里设计为负载因子等于1时扩容
		{
			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			vector newtables(newsize, nullptr);
			for (auto& cur : _tables)
			{
				//为了提高效率，不采用拷贝、删除节点的方式
				// 而是直接将旧表中的节点插入到新表中
				while (cur)
				{
					Node* next = cur->_next;
					size_t hashi = kot(cur->_data) % newtables.size();
					cur->_next = newtables[hashi];
					newtables[hashi] = cur;
					cur = next;
				}
			}
			_tables.swap(newtables);
		}
		//插入过程
		size_t hashi = kot(data) % _tables.size();
		Node* newnode = new Node(data);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
			
		++_n;
		return true;
	}

查找操作

在哈希表中查找数据的步骤如下：

  1. 先判断哈希表的大小是否为0，若为0则查找失败。
  2. 通过哈希函数计算出对应的哈希地址。
  3. 通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。
Node* Find(const K& key)
	{
		if (_tables.size() == 0)
			return nullptr;

		size_t hashi = key % _tables.size();
		Node* cur = _tables[hashi];
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return cur;
			}

			cur = cur->_next;
		}

		return nullptr;
	}

删除操作

在哈希表中删除数据的步骤如下：

  1. 通过哈希函数计算出对应的哈希桶编号。
  2. 遍历对应的哈希桶，寻找待删除结点。
  3. 若找到了待删除结点，则将该结点从单链表中移除并释放。
  4. 删除结点后，将哈希表中的有效元素个数减一。
bool Erase(const K& key)
	{
		size_t hashi = key % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hashi];
		KeyOfT kot;

		while (cur)
		{
			if (kot(cur->_data) == 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;
	}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: