剖析 std::unordered_map 插入过程

观前提醒，横屏有助于提升阅读体验。

上一节剖析 std::unordered_map 具有O(1)时间复杂度的原理中讲解了std::unordered_map应对hash冲突、退化，实现O(1)时间复杂度的原理。这一节从源码角度看看它底层实现细节。

在本节，由于C++的STL中模板参数较多，为便于描述：

  • 将模板参数较多的返回类型使用auto替代
  • 将类的成员函数实现中的类模板参数以...替代

insert

下面从insert方法开始：

1
2
3
4
5
6
7
int main(int argc, char const *argv[]) {
    
    std::unordered_map<int, int> hash_map;
    hash_map.insert({1, 1});

    return 0;
}

insert函数，内部是调用_Hashtable对象_M_h.insert(...)来实现的。为避免不必要的复制，会使用移动语义将{1,1}作为_M_h.inser的参数。

1
2
3
std::pair<iterator, bool>  insert(value_type&& __x) { 
     return _M_h.insert(std::move(__x)); 
}

_M_h.insert函数是由_Hashtable的父类_Insert 实现，因此该hash_map.insert(...)函数实际上调用的是hashtable_policy.h/_Insert::insert(...)方法：

1
2
3
4
5
6
7
8
9
10
11
template<...>
 struct _Insert<...> { 
     //...
    template<typename _Pair, typename = _IFconsp<_Pair>>
    __ireturn_type insert(_Pair&& __v) 
     {
      __hashtable& __h = this->_M_conjure_hashtable();		// 从父类转换为子类
      return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
    }
    //..
 }

函数__unique_keys()的值是std::true_type类型，其值在std::unordered_map初始化时就已确定，是用于区分 std:;unordered_map 和 std::unordered_multimap：

  • 对于 std::unordered_map，__unique_keys 是std::true_type类型
  • 对于 std::unordered_multimap，__unique_keys 是std::false_type类型

因此，__unique_keys()默认构造函数，就能确定当前是哪种类型。 其初始化过程见下四步：

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
template <bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
struct _Hashtable_traits
{
    using __hash_cached = __bool_constant<_Cache_hash_code>;
    using __constant_iterators = __bool_constant<_Constant_iterators>;
    using __unique_keys = __bool_constant<_Unique_keys>;	//1) 在此定义
};

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>; 	// 2) 特化为 true
	
template<typename _Key,
         typename _Tp,
         typename _Hash  = hash<_Key>,
         typename _Pred  = std::equal_to<_Key>,
         typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
         typename _Tr    = __umap_traits<__cache_default<_Key, _Hash>::value>> //3) 特化后在此传入
using __umap_hashtable = _Hashtable<_Key, 
                                    std::pair<const _Key, _Tp>,
                                    _Alloc, 
                                    __detail::_Select1st,
                                    _Pred, 
                                    _Hash,
                                    __detail::_Mod_range_hashing,
                                    __detail::_Default_ranged_hash,
                                    __detail::_Prime_rehash_policy, 
                                    _Tr>;  
template<typename _Key, 
		typename _Tp,
		typename _Hash  = hash<_Key>,
		typename _Pred  = equal_to<_Key>,
		typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
class unordered_map
{
  typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
  _Hashtable _M_h;   // 4) 此时  __unique_keys() 即 std::true_type 类型
  //...
}

_Hashtable::_M_emplace

因此，insert函数内部将会调用如下实例化版本：

1
__h._M_emplace(std::true_type, std::forward<_Pair>(__v));

_M_emplace函数的执行步骤如下：

  1. 构造新的节点__node：先为新的节点分配内存，并以传入的参数调用构造函数
  2. 使用__node->key的来计算hashcode
  3. 根据hashcode计算将要插入的桶索引__bkt
  4. 为了确保__node这个节点在_Hashtable中并没有存储过，因此要先在桶的链表中查找
    • 如果找到，则不插入
    • 如果没有找到，则调用 _M_insert_unique_node 函数插入节点。在此过程中可能会发送 Rehash行为

先看整个流程，再分叙各个细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
auto _Hashtable<_...>::_M_emplace(std::true_type, _Args && ...__args) {
    // 分配节点
    __node_type *__node = this->_M_allocate_node(std::forward<_Args>(__args)...);
    // 取出节点的 key
    const key_type &__k = this->_M_extract()(__node->_M_v()); 
    // 键对应的 hashcode
    __hash_code __code;                                         
    __try {
        __code = this->_M_hash_code(__k);
    }
    __catch(...) {
        this->_M_deallocate_node(__node);
        __throw_exception_again;
    }
    // 节点对应的桶索引
    size_type __bkt = _M_bucket_index(__k, __code);    
    if (__node_type *__p = _M_find_node(__bkt, __k, __code)) {
        // 如果在 _M_bucket 中已经有这个 __node， 则不插入
        this->_M_deallocate_node(__node);
        return std::make_pair(iterator(__p), false);
    }
    // 插入新节点
    return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), true);
}

_Hashtable::_M_find_node

_M_find_node 函数，在_M_bucket[__btk]指向的链表中查找是否有hashcode是__code的键__k ，时间复杂度是O(N)。其内部是调用_M_find_before_node函数来查找待插入节点__node：

  • 如果已存在__node，则_M_find_before_node 函数返回__node的前一个位置，
  • 否则返回nullptr

_M_find_node 函数实现如下：

1
2
3
4
5
6
__node_type* _M_find_node(size_type __bkt, const key_type &__key, __hash_code __c) const {
    __node_base *__before_n = _M_find_before_node(__bkt, __key, __c);
    if (__before_n)
        return static_cast<__node_type *>(__before_n->_M_nxt);
    return nullptr;
}

_M_find_before_node 函数，即在_M_buckets[__btk]中查找是否存在__node，由_M_equals函数判断两个节点是否相同。如果遍历完整个链表也没发现存在__node，则返回nullptr。

其中，当前节点不存在此链表，有两种可能：

  • _M_bucket_index(__p->_M_next()) != __n：表示下一个节点的位置不位于当前桶中。

    这是因为，为了能遍历std::unordered_map，每个桶_M_bucket[__btk]指向的链表的最后一个节点，是另一个桶的哨兵节点（这在后面Rehash函数中会更加详细的说明），当_M_bucket_index(__p->_M_next()) != __n时，即当前链表中不存在__node节点。

  • __p->_M_nxt == nullptr：这个整个_Hashtable的最后一节点

因此，当没有load_factor <= max_load_factor限制，这个链表可能会很长，使得_Hashtable的时间复杂度恶化至O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto _Hashtable<...>::_M_find_before_node(size_type __n, const key_type& __k, __hash_code __code){
       __node_base *__prev_p = _M_buckets[__n]; // 每个桶的哨兵节点
       // 这是个空桶，则直接return
       if (!__prev_p) return nullptr;

       // 从首节点开始遍历
       for (__node_type *__p = static_cast<__node_type *>(__prev_p->_M_nxt);;__p = __p->_M_next()) {
           // 已存在键__k的节点，直接返回前一个节点
           if (this->_M_equals(__k, __code, __p))
               return __prev_p;

           // 如果 __p->_M_next == nullptr，或者不在当前桶了，
           // 直接break，返回 nullptr
           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
               break;
           __prev_p = __p;
       }
       return nullptr;
   }

视线再回到_Hashtable<...>::_M_emplace函数：

  • 如果已经存在待插入节点__node，则直接返回std::make_pair(iterator(__p), false);，iterator(__p)指向__node的位置
  • 如果不存在，则先调用_M_insert_unique_node函数，将__node插入到_Hashtable中，再返回std::make_pair(iterator(__p), true);，其中iterator(__p)是_M_insert_unique_node函数的返回值。

_M_emplace函数剩余过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
auto _Hashtable<_...>::_M_emplace(std::true_type, _Args && ...__args) {  
    //...
    // 如果在 _M_bucket 中已经有这个 __node， 则不插入
    if (__node_type* __p = _M_find_node(__bkt, __k, __code)) {
        // There is already an equivalent node, no insertion
        this->_M_deallocate_node(__node);
        return std::make_pair(iterator(__p), false);
    }

    // 插入节点
    return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), true);   
}

_Hashtable::_M_insert_unique_node

当决定要插入一个节点时，如下步骤：

  • 先调用_M_need_rehash函数，判断_Hashtable是否要Rehash
    • 如果需要，则调用_M_rehash函数进行Rehash，然后重新计算要插入的桶索引__btk
    • 如果不需要，则直接使用原来的桶索引__btk
  • 将待插入节点__node插入到桶_M_bucket[__btk]的头部
  • 更新一些参数
  • 将__node迭代器，返回给 _M_emplace 函数，使其进一步返回std::make_pair(iterator(__node), 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
28
29
auto _Hashtable<...>::_M_insert_unique_node(size_type 	 __bkt, 
                                            __hash_code	 __code, 
                                            __node_type* __node, 
                                            size_type 	 __n_elt)
{
    const __rehash_state &__saved_state = _M_rehash_policy._M_state();
    auto __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count,
                                                       _M_element_count,
                                                       __n_elt);
    __try {
        // 如果确实需要rehash
        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); // __node->_M_hash_code = __code                  

        // 在 _M_bucket[__bkt] 前面插入
        _M_insert_bucket_begin(__bkt, __node);
        ++_M_element_count;
        return iterator(__node);
    }
    __catch(...) {
        this->_M_deallocate_node(__node);
        __throw_exception_again;
    }
}

_Power_rehash_policy::_M_need_rehash

_M_need_rehash 函数，判断是否需要Rehash，其函数的参数含义如下：

  • __n_bkt：_Hashtable的桶的个数
  • __n_elt：_Hashtable的元素个数
  • __n_ins：此次要插入的节点数

__n_elt + __n_ins 则是此次插入完成后_Hashtable的节点数。那么根据最大负载因子max_load_factor，可以计算出存储__n_elt + __n_ins 个节点需要的至少需要的桶数是 __min_btks。

1
long double __min_bkts = (__n_elt + __n_ins) / (long double)_M_max_load_factor; // 新的桶个数

进一步，如果这个至少需要的桶数__min_btks >= __n_btks，则表示当前桶容量不够，无法满足load_factor <= max_load_factor的限制条件，就需要对_Hashtable执行Rehash，返回std::make_pair(true, count)，count是新的桶数。

如果以上条件都不满足，不需要Rehash，则直接返回std::make_pair(false, 0)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
auto _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) noexcept {
    // 需要 rehash
    if (__n_elt + __n_ins >= _M_next_resize) {
        long double __min_bkts = (__n_elt + __n_ins) / (long double)_M_max_load_factor; 
        if (__min_bkts >= __n_bkt)
            return std::make_pair(true,
                                  _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
                                                                    __n_bkt * _S_growth_factor)));

        _M_next_resize = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
        return std::make_pair(false, 0);
    }
    
    return std::make_pair(false, 0);
}

_Hashtable::_M_rehash

_M_rehash函数，内部是调用_M_rehash_aux实现的，__unique_keys()由前面可知，在std::unordered_map中初始化为std::true_type类型。

1
2
3
4
5
6
7
8
9
 void  _Hashtable<...>::_M_rehash(size_type __n, const __rehash_state &__state) {
    __try {
        _M_rehash_aux(__n, __unique_keys());
    }
    __catch(...){
        _M_rehash_policy._M_reset(__state);
        __throw_exception_again;
    }
}

_Hashtable::_M_rehash_aux

_M_rehash_aux函数，执行步骤如下：

1) 分配内存

为__n个新桶分配内存__new_buckets

1
2
3
4
5
6
7
8
void _Hashtable<>::_M_rehash_aux(size_type __n, std::true_type) {
     __bucket_type *__new_buckets = _M_allocate_buckets(__n); // 分配 n 个新的桶
     __node_type *__p = _M_begin();                           // 旧桶的哨兵节点
    	
     _M_before_begin._M_nxt = nullptr;						// 初始化			
     std::size_t __bbegin_bkt = 0;
    //...
}

2) 数据迁移

将旧桶__M_bucket中的节点数据重新插入到__new_buckets中，在插入的过程中需要维持__new_buckets各个桶之间的联系，即当前空桶指向的链表的最后一个节要指向前一个空桶的哨兵节点。没明白吗？不急，往下看。

_Hashtable有一个哨兵节点_M_before_begin， 它总是最后一个插入节点的空桶的哨兵节点：当一个节点__p要插入一个空桶__new_buckets[__btk]时，_M_before_begin就会指向变成__new_buckets[__btk]的哨兵节点，即：

1
__new_buckets[__btk] = &_M_before_begin;

_Hashtable需要借助 _M_before_begin 节点在当前空桶和上一个空桶之间建立联系，那么当数据插入完毕，整个_Hashtable才能变成一条“链表”：_M_before_begin._M_nxt指向的就是最后一个空桶的首届点，从_M_before_begin._M_nxt开始遍历，最后一个节点的__lastNode->_M_next即nullptr。

begin()和end()迭代器即如此实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// _Hashtable::begin()
iterator begin() noexcept
{
    return iterator(_M_begin());
}

__node_type* _M_begin() const
{
    return static_cast<__node_type *>(_M_before_begin._M_nxt);
}

// _Hashtable::end()
 iterator end() noexcept
 {
     return iterator(nullptr);
 }

下面是最精彩的部分！！！

空桶中插入节点

当待插入节点__p将要插入到一个空桶时，那么需要在这个空桶和上一个空桶（已经不是空桶了）之间建立联系，建立步骤如下三步：

1
2
3
__p->_M_nxt = _M_before_begin._M_nxt;	  // 1	
_M_before_begin._M_nxt = __p;		 	 // 2
_new_buckets[__bkt] = &_M_before_begin;	  // 3

  • 由于采用头部插入法在每个链表中插入新节点，因此第一个插入到空桶_new_buckets[__bkt]的节点__p将会成为这个链表的最后一个节点。因此第一步的代码，就实现了让空桶_new_buckets[__bkt]的最后一个节点指向前一个空桶的首节点。

    1
    __p->_M_nxt = _M_before_begin._M_nxt;	 // 前一个空桶的哨兵节点是_M_before_begin

  • _M_before_begin 总是作为哨兵节点，当有一个节点__p插入空桶时，_M_before_begin就将作为新空桶的哨兵节点，那么_M_before_begin->next就应该是此刻空桶__new_buckets[__btk]第一个节点，即__p，因此就有了第2、3步。

    1
    2
    _M_before_begin._M_nxt = __p;			 // 指向第一个节点
    _new_buckets[__bkt] = &_M_before_begin;	  // 将 _M_before_begin 作为哨兵节点

    那还有什么没有完成？

    _M_before_begin已经是当前空桶的哨兵节点，那么前一个空桶的哨兵节点就不能再是_M_before_begin。由于在上面的第一步中，将__p->next指向了前一个空桶的首节点，则顺理成章地将__p变成前一个空桶的哨兵节点。

    当然，当__p是整个_Hashtable的第一个节点，那么当前空桶就是第一个空桶，此时__p->_M_next就是nullptr。

    1
    2
    3
     if (__p->_M_nxt)
        __new_buckets[__bbegin_bkt] = __p;	// 将 __p 作为前一个桶的哨兵节点
    __bbegin_bkt = __bkt;				   // __bbegin_bkt 记录前一个空桶索引

非空桶中插入节点

如果_new_buckets[__btk] 中已经有节点，则直接在头部插入即可，没有复杂性。

1
2
__p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
_new_buckets[__bkt]->_M_nxt = __p;

3） 数据迁移完成

当数据迁移完成，即_M_buckets中节点全更新到_new_buckets中，需要释放_M_buckets的内存，并且将_M_buckets指向_new_buckts，再更新其他参数即可。

完整的代码细节过程如下。

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
void _Hashtable<>::_M_rehash_aux(size_type __n, std::true_type) {
     __bucket_type *__new_buckets = _M_allocate_buckets(__n); // 分配 n 个新的桶
     __node_type *__p = _M_begin();                           // 旧桶的哨兵节点
     _M_before_begin._M_nxt = nullptr;					
     std::size_t __bbegin_bkt = 0;
  
    // 将旧桶中的节点迁移至新桶中
     while (__p) {
         __node_type* __next = __p->_M_next();
         // 节点 p 在新桶中的索引
         std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 
         // __new_buckets[__bkt] 是个空桶插入新节点
         if (!__new_buckets[__bkt]) {
             __p->_M_nxt = _M_before_begin._M_nxt;  
             _M_before_begin._M_nxt = __p;
             __new_buckets[__bkt] = &_M_before_begin;

             if (__p->_M_nxt)
                 __new_buckets[__bbegin_bkt] = __p;
             __bbegin_bkt = __bkt;
         }
         else{
             // 非空桶，则直接在头部插入
             __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
             __new_buckets[__bkt]->_M_nxt = __p;
         }
         __p = __next;  // 迭代
     }
     // 释放旧桶及更新参数
     _M_deallocate_buckets();
     _M_bucket_count = __n;
     _M_buckets = __new_buckets;
 }

至此，已完全讲解了hash_map是如何插入一个节点。