C++ STL:std::unorderd_map 物理结构详解

拉链法的 unordered_map 和你想象中的不一样

根据数组+拉链法的描述,我们很快能想到下面这样的拉链法实现的哈希表,但真的是这样吗?一起看下源码里的实现是怎么样的。

C++ STL:std::unorderd_map 物理结构详解

深入STL源码

代码不会骗人的,可以写一个简单的代码研究一下实现,然后通过gdb跟踪执行:

#include <vector>
#include <unordered_map>

int main() {
  std::unordered_map<int, int> hashmap;
  hashmap[26] = 26;
}

编译和打开gdbgui:

g++ -g hashmap.cc  -std=c++11 -o hashmap_test
gdbgui -r -p 8000 ./hashmap_test

gdb 跟进发现代码会走到 hashtable_policy.h 的 operator[] 函数中,代码我做了一些简化,只提取了关键代码:

auto operator[](const key_type& __k) -> mapped_type&
{
	__hashtable* __h = static_cast<__hashtable*>(this);
	
	// 根据 key 获得 hashcode
	__hash_code __code = __h->_M_hash_code(__k);
	// 根据 key 和 hashcode 获得 bucket 的 index:n
	std::size_t __n = __h->_M_bucket_index(__k, __code);
	// 在 bucket n 内尝试找到节点key为k的节点
	__node_type* __p = __h->_M_find_node(__n, __k, __code);

	if (!__p)
	{
		// 如果找到的节点为 nullptr,那么就重新分配一个节点并且将新节点插入到 hash 表中。
		__p = __h->_M_allocate_node(k);
		return __h->_M_insert_unique_node(__n, __code, __p)->second;
	}
	return __p->_M_v().second;
}

operator[]函数的功能是计算key的hash值,再通过hash值找到对应的bucket n,最后在这个bucket内查找是不是有一个key=k的节点,
如果没有找到需要的节点,就会新分配并且插入一个新的节点。

那么这个节点如何插入的呢?跟进下插入函数 _h->_M_insert_unique_node(__n, __code, __p):

auto _M_insert_unique_node(__bkt, __code, __node, size_type __n_elt = 1) -> iterator
{
	  // 判断是否需要 rehash
	const __rehash_state& __saved_state = _M_rehash_policy._M_state();
	std::pair<bool, std::size_t> __do_rehash
	= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
					  __n_elt);
	if (__do_rehash.first)
	{
		_M_rehash(__do_rehash.second, __saved_state);
		__bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
	}
	this->_M_store_code(__node, __code);

	// Always insert at the beginning of the bucket.
	// 将节点插入到 bucket 的开始位置
	_M_insert_bucket_begin(__bkt, __node);
	++_M_element_count;
	return iterator(__node);
}

_M_insert_unique_node() 这个插入函数主要作用是判断如果新插入节点,这个hash表的负载会不会过高?需不需要重新扩容,完成扩容后通过_M_insert_bucket_begin()再插入到 bucket 的 begin 的位置,这里 rehash 的过程我们暂时不关注,先看下_M_insert_bucket_begin() 这个函数是怎么实现的:

    _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
    {
	// 判断bucket n 是否为空
      if (_M_buckets[__bkt])
	{
		// Bucket is not empty, we just need to insert the new node
		// after the bucket before begin.
		// 如果 bucket 不为空,用头插法将节点插入到开头
		__node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
		_M_buckets[__bkt]->_M_nxt = __node;
	}
      else
	{
	  // The bucket is empty, the new node is inserted at the
	  // beginning of the singly-linked list and the bucket will
	  // contain _M_before_begin pointer.
	  // 如果节点不为空,
	  __node->_M_nxt = _M_before_begin._M_nxt;
	  _M_before_begin._M_nxt = __node;
	  if (__node->_M_nxt)
		// 如果 __node->_M_nxt 也就是原来的 _M_before_begin._M_nxt 不为空,
		// 那么就要就要把 _M_before_begin._M_nxt 指向新的 node__。
	    // We must update former begin bucket that is pointing to
	    // _M_before_begin.
	    _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
	  // 将 _M_before_begin 赋值给 bucket n。
	  _M_buckets[__bkt] = &_M_before_begin;
	}
    }

现在就到了插入节点的精彩部分了,当前 bucket 是否为空将函数划分成了两个部分,接下来将用图例的方式来展示整个插入过程。

插入第一个节点

首先先看为空的情况:

C++ STL:std::unorderd_map 物理结构详解

在进入函数前,有:

  • 预先创建好的(hashmap 构造函数) buckets
  • 一个成员变量_M_before_begin
  • 一个新分配出来的插入节点__p

当前插入的值为26,做完哈希计算n = 26 % 7 = 5,那么就会在bucket[5]做插入:

C++ STL:std::unorderd_map 物理结构详解

bucket[5] 为空的插入代码为:

__node->_M_nxt = _M_before_begin._M_nxt; // ①
_M_before_begin._M_nxt = __node; // ②
if (__node->_M_nxt)
	_M_buckets[_M_bucket_index(__node->_M_next())] = __node;
_M_buckets[__bkt] = &_M_before_begin; // ③
  1. ①、②两步就是经典链表的头插法,插入到两个节点中间。
  2. 因为这里 __node->_M_nxt 是指向nullptr的,具体的逻辑先跳过。
  3. 然后第③步将_M_before_begin的地址赋值给bucket[n]

于是得到了一个头插法后的链表:

C++ STL:std::unorderd_map 物理结构详解

插入同bucket的第二个节点

如果尝试在同一个 bucket 插入一个新的值,因为当前 bucket 有值,代码就会走到_M_insert_bucket_begin()这个函数的前半部分:

      if (_M_buckets[__bkt])
	{
		// Bucket is not empty, we just need to insert the new node
		// after the bucket before begin.
		// 如果 bucket 不为空,用头插法将节点插入到开头
		__node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
		_M_buckets[__bkt]->_M_nxt = __node;
	}

C++ STL:std::unorderd_map 物理结构详解

简化得到:

C++ STL:std::unorderd_map 物理结构详解

到目前为止和想象中的哈希表还是差不多的,不断的插入到一个 bucket 中,并且用链表连在一起,现在尝试插入一个节点到别的 bucket 中:

在不同的bucket插入一个节点

C++ STL:std::unorderd_map 物理结构详解

先会运行 bucket 为空的前两行,仍然是头插法后的结果:

__node->_M_nxt = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = __node;

C++ STL:std::unorderd_map 物理结构详解

继续运行接下来的语句:

if (__node->_M_nxt)
	// We must update former begin bucket that is pointing to
	// _M_before_begin.
	_M_buckets[_M_bucket_index(__node->_M_next())] = __node;
_M_buckets[__bkt] = &_M_before_begin;

C++ STL:std::unorderd_map 物理结构详解

此时,因为 _M_before_begin._M_nxt 不为空,并且赋值到了新节点 __node_M_nxt 上,此时就会执行逻辑:

_M_buckets[_M_bucket_index(__node->_M_next())] = __node;

__node->_M_next() 也就是 key 为 12 的那个节点,其bucket_index 应该是5,所以bucket[5]的指针将会指向新插入的这个节点。

最后再将bucket[1] 指向 _M_before_begin,得到:

C++ STL:std::unorderd_map 物理结构详解

继续简化一下,最终其实会形成一个带哨兵节点的单链表,而每个 bucket 只存有一个指向该链表相应位置的指针,其中_M_before_begin就是这个哨兵节点:

C++ STL:std::unorderd_map 物理结构详解

最终结构

  • 在bucket有值的时候,都是通过前一个指针和头插法插入到对应的 bucket 内。
  • 如果 bucket 没有值,就会把哨兵节点切换到新的 bucket 中。
    如:

C++ STL:std::unorderd_map 物理结构详解

这么复杂,有什么好处呢?
遍历的时间复杂度。

假设在这种实现下,遍历整个 hashmap 只需要从 head 指针不断的像 head->next 移动至 nullptr,如果总共有 n 个元素,k个bucket,时间复杂度也只有 O(n)

如果是最开始那种实现呢?每个bucket一个链表,需要判断所有 bucket 是否为空,并且遍历每个 bucket 内的链表,时间复杂度会到达 O(n + k),而且哈希表为了避免哈希冲突,通常会有一个比较大的数组,表达式中的 k 的影响还是挺大的。

验证

插入的代码已经理解了,验证一下理解的结构是不是真的是这样,再看下hashmap.find(key)的代码,find 的过程其实在 hashmap.operator[] 中已经有了,插入前判断是不是已经有节点了:

auto operator[](const key_type& __k) -> mapped_type&
{
	__hashtable* __h = static_cast<__hashtable*>(this);
	
	// 根据 key 获得 hashcode
	__hash_code __code = __h->_M_hash_code(__k);
	// 根据 key 和 hashcode 获得 bucket 的 index:n
	std::size_t __n = __h->_M_bucket_index(__k, __code);
	// 在 bucket n 内尝试找到节点key为k的节点
	__node_type* __p = __h->_M_find_node(__n, __k, __code);

	if (!__p)
	{
		// ... Do allocate and insert
	}
	return __p->_M_v().second;
}

跟踪下函数 __h->_M_find_node(__n, __k, __code),会调用 _M_find_before_node(__n, __k, __code):

auto _M_find_before_node(size_type __n, const key_type& __k, __hash_code __code) const -> __node_base*
{
	// _M_buckets[__n] 存储了该 bucket 的 prev,如果不存在,那么这个 bucket 就是空的
	__node_base* __prev_p = _M_buckets[__n];
	if (!__prev_p)
		return nullptr;
	
	// 从 prev->next 开始,循环到 prev->next 为nullptr 或者 prev->next 的bucket号不是当前bucket 为止。
	for (__node_type* __p = __prev_p->_M_nxt;  ; __p = __p->_M_next())
	{
	  if (this->_M_equals(__k, __code, __p))
	    return __prev_p;
	  // 循环结束判断
	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
	    break;
	  __prev_p = __p;
	}
	return nullptr;
}

现在判断当前 bucket[n] 是否有值,如果有值,就开始从 prev->next 开始遍历到 nullptr,或者 bucket 号不是当前bucket的节点。

比如,找一个bucket[2]内的节点的开始和结束:
C++ STL:std::unorderd_map 物理结构详解

总结

标准库内的 STL 的实现还是非常 Amazing 的,它的实现关键词有三个,数组、单链表和哨兵节点,在支持分桶的情况下,还支持了O(n)的遍历复杂度。

另外附上我的参考连接:

  1. 帮助我理解了_M_before_begin节点的作用 https://szza.github.io/2021/03/01/C++/2_/
上一篇:HUAWEI 机试题:全量字符集和已占用字符集


下一篇:《图解密码技术》笔记15:密码技术与现实社会-我们生活在不完美的安全中