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

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

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

• 本文更好的阅读体验，可以点击：源码剖析std::unordered_map解决hash冲突的过程
• 更多硬核知识，vx搜一搜: look_code_art，等你发现，
• 也可以添加个人 vx: fibonaccii_，交流技术

insert

下面从insert方法开始：

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的参数。

   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(...)方法：

 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()默认构造函数，就能确定当前是哪种类型。 其初始化过程见下四步：

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::Memplace

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

__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行为

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

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::Mfind_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 函数实现如下：

__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).

 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函数剩余过程如下：

    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::Minsert_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);

插入一个节点的流程如下。

    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::Mneed_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。

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)。

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::Mrehash

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

 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::Mrehash_aux

_M_rehash_aux函数，执行步骤如下：

1) 分配内存

为__n个新桶分配内存__new_buckets

   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]的哨兵节点，即：

__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()迭代器即如此实现：

// _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将要插入到一个空桶时，那么需要在这个空桶和上一个空桶（已经不是空桶了）之间建立联系，建立步骤如下三步：

__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]的最后一个节点指向前一个空桶的首节点。

  __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步。

  _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。

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

非空桶中插入节点

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

__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，再更新其他参数即可。

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

   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是如何插入一个节点。

int main(int argc, char const *argv[]) {

    std::unordered_map<int, int> hash_map;

    hash_map.insert({1, 1});

    return 0;
}