C++容器之unordered_map、unordered_set的底层剖析_unorderedmap底层实现

文中源码以上传至Gitee

序列式容器和关联式容器

序列式容器和关联式容器是C++标准库中的两种不同类型的容器。序列式容器是按照元素在容器中的线性顺序进行存储和访问的容器。它们可以包含不同类型的元素，并提供了按顺序插入、删除和访问元素的操作。常见的序列式容器包括：

1. vector：动态数组，支持快速的随机访问。
2. list：双向链表，支持高效的插入和删除操作。
3. deque：双端队列，支持在两端进行插入和删除操作。

关联式容器是根据元素的键值进行存储和访问的容器。它们使用一种特定的数据结构（通常是二叉搜索树或哈希表）来实现元素的快速查找。关联式容器中的元素通常是按照键值的排序顺序进行存储。常见的关联式容器包括：

1. set：集合，存储唯一的元素，并按照键值进行排序。
2. map：映射，存储键值对，并按照键值进行排序。
3. multiset：多重集合，存储允许重复的元素，并按照键值进行排序。
4. multimap：多重映射，存储允许重复的键值对，并按照键值进行排序。

unordered_set和unordered_map

unordered_set 和 unordered_map 都是C++标准库中的关联式容器，它们的底层实现都基于哈希表，主要区别在于它们存储的内容和用途，unordered_set 是一种用于存储唯一值的容器。它类似于一个集合，其中每个值都是唯一的，重复值将被忽略，主要用途是在不需要关联键值对的情况下，仅存储一组唯一的值，并支持高效的插入、查找和删除操作。unordered_map 是用于存储键值对的容器，其中每个键都对应一个唯一的值。它提供了一种通过键来查找值的机制，主要用途是将键与数据进行关联，支持通过键高效地查找、插入和删除值。

哈希表

unordered_map和unordered_set与map和set的用法基本相似，在熟悉了map和set的用法之后，在上手这两个就不是什么难事了，但是已经有了map和set之后，为什么C++11还要加入这两个呢？那必然是有它的独到之处的，就是他那在平均情况下实现常数时间复杂度的插入、查找和删除操作。如此高的效率，它的底层实现也是很值得让人去查探一番。

概念

哈希表是一种常用的数据结构，用于实现关联数组或映射。它通过将键映射到值来实现快速的数据查找和插入操作。哈希表的基本思想是利用哈希函数将键映射到一个固定大小的数组（通常称为哈希表或散列表）的索引位置上。哈希函数将键转换为一个整数，然后使用该整数作为数组的索引，将值存储在对应的位置上。

哈希函数与哈希冲突

哈希函数的设计很重要，它应该能够将键均匀地映射到数组的不同位置上，以避免冲突。哈希冲突也叫哈希碰撞，即不同关键字通过相同哈希哈数计算出相同的哈希地址。又将具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

当我们在插入3或者5时，根据哈希函数的映射规则，会将要新插入的数映射到一个已经存在有数据的位置，这就会导致哈希冲突。引起哈希冲突的一个极其重要的原因可能是：哈希函数设计不够合理。哈希函数的设计是哈希表的关键部分，一个好的哈希函数应该具备以下设计原则：

• 确定性：相同的输入应该始终映射到相同的哈希值。这是哈希函数的基本要求，确保在相同的键上进行查找或插入操作时能够得到一致的结果。

• 均匀性：好的哈希函数应该能够将不同的输入均匀地分布在哈希表的各个位置上，以减少冲突的发生。这可以提高哈希表的性能，因为冲突会导致查找、插入和删除操作的时间复杂度增加。

• 高效性：哈希函数应该能够快速计算出哈希值，以确保操作的效率。理想情况下，哈希函数的计算时间应该是常数时间。

• 低碰撞率：碰撞是指多个不同的键映射到相同的哈希值的情况。好的哈希函数应该尽量减少碰撞的发生，但完全消除碰撞是不可能的。

• 最小冲突影响：当发生碰撞时，哈希函数应该能够将冲突的影响最小化，例如通过开放寻址法或链表法等方法来处理碰撞。

• 适应性：哈希函数应该适应不同大小的哈希表，而不仅仅适用于特定大小的表格。

常用的哈希函数

我们常用的哈希函数主要有两个，分别是直接定址法和除留余数法。

直接定址法

直接定址法使用键的某个线性函数（通常是哈希表大小的乘法因子）来计算哈希值。具体步骤如下：

1. 对于给定的键，使用一个线性函数计算哈希值：hash(key) = a * key + b，其中a和b是常数。
2. 将哈希值作为数组的索引，将键存储在该位置。

直接定址法的优点是简单快速，不需要处理冲突，但它要求哈希表的大小足够大，以避免冲突的发生。如果哈希表的大小不够大，可能会导致较高的冲突率。

除留余数法

除留余数法使用键除以哈希表的大小，然后取余数作为哈希值。具体步骤如下：

1. 对于给定的键，计算哈希值：hash(key) = key % table_size，其中table_size是哈希表的大小。
2. 将哈希值作为数组的索引，将键存储在该位置。

除留余数法的优点是简单易实现，适用于哈希表大小不变的情况。然而，如果哈希表的大小改变，可能会导致哈希值的分布不均匀，增加冲突的概率。

哈希冲突处理方案

哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。理论上只要存放数据的数组足够大，能够保证每个数据都有自己独立的空间，这样就不会出现冲突。先不说这种设想的可能性，单是空间的利用率就已经让人望而生畏。因此就还需要一个能够让冲突的概率和空间利用率处于一种相对平衡状态的方案，于是负载因子应运而生。负载因子通常表示为λ（lambda），是哈希表中已存储元素的数量与哈希表总容量之间的比值。它用来衡量哈希表的填充程度，即已存储元素占哈希表容量的百分比。一般来说，常见的负载因子阈值为0.7或0.8，即当哈希表中已存储元素的数量占总容量的70%或80%时，触发动态扩展操作。这样可以在保持较好性能的同时，避免过度消耗内存。

开放定址法

开放定址法也叫闭散列，当发生冲突时，继续探测数组中的下一个位置，直到找到一个空闲的位置来存储值。 寻找下一个空闲位置的方法有线性探测和二次探测，当发生冲突时，线性探测会依次检查下一个哈希表位置，直到找到一个空的位置为止。这意味着如果位置i被占用，线性探测会尝试位置i+1，然后i+2，以此类推。

二次探测使用二次函数来确定下一个探测位置，例如，如果位置i被占用，二次探测会尝试位置(i+k^2)%size（k=1，2，3…），以此类推。这有助于减少线性探测可能出现的聚集问题。

链地址法

链地址法也叫开散列，在链地址法中，每个散列表的槽都会链接一个链表，当发生冲突时，新元素会被添加到相应槽的链表中，而不是覆盖已存在的元素。这种方法允许多个元素共享同一个槽，并通过链表将它们串联在一起。当需要查找特定元素时，散列表首先计算元素的散列值，然后定位到相应的槽，最后在链表中搜索。

开放定地址法和链地址法对比

应用链地址法处理冲突时，需要增设链接指针，这似乎增加了存储开销。而事实上，由于开放定址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求负载因子小于等于 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开放定址法节省存储空间。

开放定址法实现

如果使用线性探测，在开放定址法的实现中，首先需要一个顺序表用来存储映射的数据，由于线性探测的特性，如果在删除操作时直接将数据进行删除，那么就会影响其他元素的查找，例如：

在上述的查找中，如果直接将3删除后，在查找2的时候，在经过哈希函数的计算从下标为2的地方开始查找，不等于2则向后走，走到下标为3的时候发现该位置没有数据，则认为表中不存在元素2，查找失败。因此线性探测应该采用标记的伪删除法来删除一个元素，就可以这样定义顺序表中存储的数据，如下代码：

enum State { EMPTY, EXIST, DELETE };
template<class K, class V>
struct Elem
{
	pair<K, V> _val;
	State _state;
};
1
2
3
4
5
6
7

对于哈希表，除了定义一个顺序表之外，还需要又一个size来记录有效元素个数以及一个totalsize来记录顺序表中的总元素个数，如下代码：

vector<Elem> _ht;
size_t _size;  
size_t _totalSize; 
1
2
3

除此之外还需要一个哈希函数和一个检查扩容的函数，哈希函数采用除留余数法，由于key的类型不确定，因此还需要提供一个仿函数来将不能直接进行取模运算的类型转换成为可以进行取模运算的类型，就有如下代码：

size_t HashFunc(const K& key)
{
	return HF()(key) % _ht.size();
}
1
2
3
4

检查扩容函数就是检查负载因子是否超过阈值，如果超过阈值就需要对顺序表进行扩容并且对其中的有效数据进行重新映射和更新totalsize。如下代码：

void CheckCapacity()
{
	if (_totalSize * 10 / _ht.size() >= 6)
	{
		HashTable<K, V> ht(_ht.size() * 2);
		for (auto& e : _ht)
		{
			if (e._state == EXIST)
			{
				ht.Insert(e._val);
			}
		}
		Swap(ht);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

然后就可以对哈希表来进行各种操作了，如插入，删除，查找等。如下代码：

// 插入
		bool Insert(const pair<K, V>& val)
		{
			CheckCapacity();
			size_t ret = Find(val.first);
			if (ret != -1) return false;
			int hashi = HashFunc(val.first);
			while (1)
			{
				if (_ht[hashi % _ht.size()]._state == EMPTY)
				{
					_ht[hashi % _ht.size()] = { val, EXIST };
					_size++;
					_totalSize++;
					break;
				}
				hashi++;
			}
			return true;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

再插入操作中，首先对负载因子进行检查，然后在对要插入元素的key值进行查找，看看是否存在相同key值，如果存在则插入失败，否则就计算该key值的映射位置，对该位置进行线性探测，插入完成后跳出循环返回true。

代码中的循环不会造成死循环，因为负载因子的控制保证了顺序表中必然存在空的位置来进行插入，二次线性探测也是类似，只需要修改hashi的步长逻辑即可。

// 查找
size_t Find(const K& key)
{
	int hashi = HashFunc(key);
	while (hashi < _ht.size() && _ht[hashi]._state != EMPTY)
	{
		if (_ht[hashi]._state != DELETE && _ht[hashi]._val.first == key)
		{
			return hashi;
		}
		hashi++;
	}			
	return -1;
}

// 删除
bool Erase(const K& key)
{
	size_t ret = Find(key);
	if (ret == -1)
	{
		return false;
	}
	_ht[ret]._state = DELETE;
	_size--;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

链地址法实现

要链地址法首先还是需要一个顺序表，里面存放指向数据元素的指针，数据元素里面除了存放数据也需要有一个指针将冲突元素链接起来，因此就可以定义一个结构体对象，如下代码：

template<class T>
struct HashBucketNode
{
	HashBucketNode(const T& data)
		: _pNext(nullptr)
		, _data(data)
	{}
	HashBucketNode<T>* _pNext;
	T _data;
};
1
2
3
4
5
6
7
8
9
10

哈希表的定义除了一个顺序表外还需要一个size用来记录表中的元素个数，如下代码：

vector<Node*> _table;
size_t _size;
1
2

与开放定址法类似，由于节点中data的类型不确定，因此对data的哈希映射时不能直接进行取模，还需要提供一个仿函数对key值进行转换，这样就可以通过仿函数将key值过滤一遍在进行取模运算。如下代码：

size_t HashFunc(const K& key)
{
	return HF()(key) % _table.size();
}
1
2
3
4

链地址法也需要维护负载因子来减少冲突的概率，因此也需要一个检查扩容的函数，又因为date的类型不确定，因此还需要提供一个仿函数用来提取元素的key值，如下代码：

void CheckCapacity()
{
	if (_size * 10 / _table.size() >= 7)
	{
		_table.resize(_table.size() * 2);
		for (int i = 0; i < _table.size(); i++)
		{
			while (_table[i] != nullptr)
			{
				int hashi = HashFunc(KeyOfT()(_table[i]->_data));
				if (hashi == i) break;
				Node* p = _table[i];
				_table[i] = p->_pNext;						
				p->_pNext = _table[hashi];
				_table[hashi] = p;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

最后可以对哈希表进行插入、删除和查找了，如下代码：

pair<iterator, bool> Insert(const T& data)
{
	KeyOfT keyoft;
	int hashi = HashFunc(keyoft(data));
	Node* p = _table[hashi];
	while (p)
	{
		if (keyoft(p->_data) == keyoft(data)) 
			return make_pair(iterator(nullptr, this), false);
		p = p->_pNext;
	}
	CheckCapacity();
	hashi = HashFunc(keyoft(data));
	Node* node = new Node(data);
	node->_pNext = _table[hashi];
	_table[hashi] = node;
	_size++;
	return make_pair(iterator(node, this), true);
}

bool Erase(const K& key)
{
	KeyOfT keyoft;
	int hashi = HashFunc(key);
	if (_table[hashi] == nullptr) return false;
	Node* cur = _table[hashi];
	if (keyoft(cur->_data) == key)
	{
		_table[hashi] = cur->_pNext;
		delete cur;
		_size--;
		return true;
	}
	else
	{
		Node* prev = cur;
		cur = cur->_pNext;
		while (cur)
		{
			if (keyoft(cur->_data) == key)
			{
				prev->_pNext = cur->_pNext;
				delete cur;
				_size--;
				return true;
			}
			prev = prev->_pNext;
			cur = cur->_pNext;
		}	
		return false;
	}
}

iterator Find(const K& key)
{
	KeyOfT keyoft;
	int hashi = HashFunc(key);
	Node* p = _table[hashi];
	while (p)
	{
		if (keyoft(p->_data) == key) return iterator(p, this);
		p = p->_pNext;
	}
	return end();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

除此之外还可以给哈希表加上迭代器，迭代器需要有指向元素的指针，为了方便对迭代器进行++操作，还需要一个哈希表，如下代码：

template<class K, class T, class KeyOfT, class Ref, class Ptr, class HF>
class HBIterator
{
	typedef HashBucket<K, T, KeyOfT, HF> HashBucket;
	typedef HashBucketNode<T> Node;
	typedef HBIterator<K, T, KeyOfT, Ref, Ptr, HF> self;
public:
	HBIterator(Node* node, const HashBucket* ht)
		:_pnode(node), _ht(ht)
	{}
	HBIterator(const self& it)
		:_pnode(it._pnode)
		,_ht(it._ht)
	{}

	Ref operator*()
	{
		return _pnode->_data;
	}
	Ptr operator->()
	{
		return &(_pnode->_data);
	}
	bool operator==(const self& it)
	{
		return _pnode == it._pnode;
	}
	bool operator!=(const self& it)
	{
		return _pnode != it._pnode;
	}
	self operator++()
	{
		if (_pnode->_pNext)
		{
			_pnode = _pnode->_pNext;
		}
		else
		{
			int hashi = HF()(KeyOfT()(_pnode->_data)) % _ht->_table.size();
			hashi++;
			while (hashi < _ht->_table.size())
			{
				if (_ht->_table[hashi])
				{
					_pnode = _ht->_table[hashi];
					break;
				}
				else
				{
					++hashi;
				}
			}
			if (hashi == _ht->_table.size())
			{
				_pnode = nullptr;
			}
		}
		return *this;
	}
private:
	Node* _pnode;
	const HashBucket* _ht;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

unordered_map和unordered_set的实现

在实现了链地址法的哈希表后，对于unordered_map和unordered_set的实现就可以用这个哈希表做底层容器，直接复用代码即可简单完成unordered_map和unordered_set。如下代码：

template<class K, class V, class HF = HashFunc<K>>
class unordered_map
{
public:
	struct KeyOfT
	{
		const K& operator()(const std::pair<K, V>& data)
		{
			return data.first;
		}
	};
	typedef HashBucket<K, std::pair<K, V>, KeyOfT, HF> HT;
	typedef typename HashBucket<K, std::pair<K, V>, KeyOfT, HF>::iterator iterator;
public:
	unordered_map(size_t num = 10)
		:_map(num)
	{}
	unordered_map(const HT& map)
		:_map(map)
	{}
	~unordered_map()
	{}
	iterator begin()
	{
		return _map.begin();
	}
	iterator end()
	{
		return _map.end();
	}
	pair<iterator, bool> insert(const std::pair<K, V>& data)
	{
		return _map.Insert(data);
	}
	iterator find(const K& key)
	{
		return _map.Find(key);
	}
	bool erase(const K& key)
	{
		return _map.Erase(key);
	}
	size_t size()
	{
		return _map.Size();
	}
	size_t count()
	{
		return _map.BucketCount();
	}
private:
	HT _map;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

template<class K, class HF = HashFunc<K>>
class unordered_set
{
	struct KeyOfT
	{
		const K& operator()(const K& data)
		{
			return data;
		}
	};
	typedef HashBucket<K, K, KeyOfT, HF> HT;
	typedef HBIterator<K, K, KeyOfT, K&, K*, HF> iterator;
public:
	unordered_set(size_t num = 10)
		:_set(num)
	{}
	unordered_set(const HT& set)
		:_set(set)
	{}
	~unordered_set()
	{}
	iterator begin()
	{
		return _set.begin();
	}
	iterator end()
	{
		return _set.end();
	}
	bool insert(const K& data)
	{
		return _set.Insert(data);
	}
	iterator find(const K& data)
	{
		return _set.Find(data);
	}
	bool erase(const K& data)
	{
		return _set.Erase(data);
	}
	size_t size()
	{
		return _set.Size();
	}
	size_t count()
	{
		return _set.BucketCount();
	}
private:
	HT _set;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

总结

文章对C++unordered_map和unordered_set的底层哈希表进行了详细介绍，但是对unordered_map和unordered_set的用法并没有进行介绍，因为这两者和map、set的用法并没有太大差异，如果能够使用map和set那么使用unordered系列的容器也就没多大难度，反而是底层的不同更值得让我们进行研究。因为代码篇幅太长，所以文章中只是对代码截取，如果需要查看源码的话可以跳转到gitees上查看，gitee链接已放置在文章顶部。码文不易，如果觉得文章对你有帮助的话，你的声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】