源码剖析unordered_map解决hash冲突的过程
在前文 剖析 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函数的执行步骤如下：
- 构造新的节点
__node：先为新的节点分配内存，并以传入的参数调用构造函数 - 使用
__node->key的来计算hashcode - 根据hashcode计算将要插入的桶索引
__bkt - 为了确保
__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;
} #C/C++##学习路径#
