C++ - unordered_map 源码解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介:   转自:http://zrj.me/archives/1248,转载请注明.(分析得不错)   主要尝试回答下面几个问题: 一般情况下,使用 hash 结构,需要有桶的概念,那么 unordered_map 是如何自动管理桶的,这个问题其实再细分的话是这样的:初始的桶是如何...

 

 

转自:http://zrj.me/archives/1248,转载请注明.(分析得不错)

 

主要尝试回答下面几个问题:

  1. 一般情况下,使用 hash 结构,需要有桶的概念,那么 unordered_map 是如何自动管理桶的,这个问题其实再细分的话是这样的:
    1. 初始的桶是如何设置的
    2. 当需要扩容的时候,是如何重新分布的
  2. 对于 string,unordered_map 的默认哈希函数是怎样的

 

代码位于 /usr/include/c++/4.1.2/tr1/,编译器版本比较老,在这个目录下,有这些文件

total 308K
-rw-r--r-- 1 root root 3.2K 2007-05-03 20:55 utility
-rw-r--r-- 1 root root 5.5K 2007-05-03 20:55 unordered_set
-rw-r--r-- 1 root root 5.8K 2007-05-03 20:55 unordered_map
-rw-r--r-- 1 root root 5.2K 2007-05-03 20:55 type_traits_fwd.h
-rw-r--r-- 1 root root  20K 2007-05-03 20:55 type_traits
-rw-r--r-- 1 root root 4.8K 2007-05-03 20:55 tuple_iterate.h
-rw-r--r-- 1 root root  11K 2007-05-03 20:55 tuple
-rw-r--r-- 1 root root  41K 2007-05-03 20:55 repeat.h
-rw-r--r-- 1 root root 1.9K 2007-05-03 20:55 ref_wrap_iterate.h
-rw-r--r-- 1 root root 2.0K 2007-05-03 20:55 ref_fwd.h
-rw-r--r-- 1 root root 2.3K 2007-05-03 20:55 mu_iterate.h
-rw-r--r-- 1 root root 2.0K 2007-05-03 20:55 memory
-rw-r--r-- 1 root root  63K 2007-05-03 20:55 hashtable
-rw-r--r-- 1 root root  28K 2007-05-03 20:55 functional_iterate.h
-rw-r--r-- 1 root root  36K 2007-05-03 20:55 functional
-rw-r--r-- 1 root root  24K 2007-05-03 20:55 boost_shared_ptr.h
-rw-r--r-- 1 root root 8.1K 2007-05-03 20:55 bind_repeat.h
-rw-r--r-- 1 root root 2.8K 2007-05-03 20:55 bind_iterate.h
-rw-r--r-- 1 root root 7.4K 2007-05-03 20:55 array

需要注意的是,unorder_map 和 unorder_set,其实都是一个封装而已,底下用的是 hashtable,所以分析也着重分析 hashtable

先来看一个典型的操作,[ ] 运算符,在 679 行附近,有这样的代码

  template<typename K, typename Pair, typename Hashtable>
    typename map_base<K, Pair, extract1st<Pair>, true, Hashtable>::mapped_type&
    map_base<K, Pair, extract1st<Pair>, true, Hashtable>::
    operator[](const K& k)
    {
      Hashtable* h = static_cast<Hashtable*>(this);
      typename Hashtable::hash_code_t code = h->m_hash_code(k);
      std::size_t n = h->bucket_index(k, code, h->bucket_count());

      typename Hashtable::node* p = h->m_find_node(h->m_buckets[n], k, code);
      if (!p)
	return h->m_insert_bucket(std::make_pair(k, mapped_type()),
				  n, code)->second;
      return (p->m_v).second;
    }

可以看到,这是典型的 hash 操作的写法

  1. 先对 key 算出 hash code
  2. 找到这个 hash code 对应的桶
  3. 在这个桶里面,遍历去找这个 key 对应的节点
  4. 把节点返回

需要注意的是,如果找不到节点,不是返回空,而是会创建一个新的空白节点,然后返回这个空白节点,这里估计是受到返回值的约束,因为返回值声明了必须为一个引用,所以总得搞一个东西出来才能有的引用

接下来看初始化过程,gdb 跟踪代码可以发现,在 /usr/include/c++/4.1.2/tr1/unordered_map:86,有下面这样的代码,可以看到,初始化的桶大小,被写死为 10。

      explicit
      unordered_map(size_type n = 10,
		    const hasher& hf = hasher(),
		    const key_equal& eql = key_equal(),
		    const allocator_type& a = allocator_type())
      : Base(n, hf, Internal::mod_range_hashing(),
	     Internal::default_ranged_hash(),
	     eql, Internal::extract1st<std::pair<const Key, T> >(), a)
      { }

但是,我们看一下下面这个代码的输出

#include <tr1/unordered_map>
#include <string>
#include <stdio.h>

int main() {
    std::tr1::unordered_map<std::string, int> m;
    printf("%d\n", m.bucket_count());
    return 0;
}

输出是 11。为什么呢,这个涉及到 rehash。他是初始化为 10,然后 rehash 为 11 了。

rehash 有两个问题,一个是判断什么时候需要 rehash,一个是怎么 rehash。

need_rehash 在 hasttable 的 614 附近:

  inline std::pair<bool, std::size_t>
  prime_rehash_policy::
  need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const
  {
    if (n_elt + n_ins > m_next_resize)
      {
	float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
	if (min_bkts > n_bkt)
	  {
	    min_bkts = std::max(min_bkts, m_growth_factor * n_bkt);
	    const unsigned long* const last = X<>::primes + X<>::n_primes;
	    const unsigned long* p = std::lower_bound(X<>::primes, last,
						      min_bkts, lt());
	    m_next_resize =
	      static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
	    return std::make_pair(true, *p);
	  }
	else
	  {
	    m_next_resize =
	      static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));
	    return std::make_pair(false, 0);
	  }
      }
    else
      return std::make_pair(false, 0);
  }

来看他是怎么做的,首先是用一个 m_max_load_factor 的因子来判断目前的容量需要多少个哈希桶,如果需要 rehash,那么使用素数表来算出新的桶需要多大。

素数表在 491 行附近:

template<int ulongsize>
    const unsigned long X<ulongsize>::primes[256 + 48 + 1] =
    {
      2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,

初始的时候,m_max_load_factor(1), m_growth_factor(2), m_next_resize(0),根据 std::lower_bound 来找到比 10 大的最小素数是 11,于是就分配为 11 个桶。

rehash 就很平淡无奇了,一个一个重算,然后重新填进去,没有什么特别的。

  template<typename K, typename V,
	   typename A, typename Ex, typename Eq,
	   typename H1, typename H2, typename H, typename RP,
	   bool c, bool ci, bool u>
    void
    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
    m_rehash(size_type n)
    {
      node** new_array = m_allocate_buckets(n);
      try
	{
	  for (size_type i = 0; i < m_bucket_count; ++i)
	    while (node* p = m_buckets[i])
	      {
		size_type new_index = this->bucket_index(p, n);
		m_buckets[i] = p->m_next;
		p->m_next = new_array[new_index];
		new_array[new_index] = p;
	      }
	  m_deallocate_buckets(m_buckets, m_bucket_count);
	  m_bucket_count = n;
	  m_buckets = new_array;
	}
      catch(...)
	{
	  // A failure here means that a hash function threw an exception.
	  // We can't restore the previous state without calling the hash
	  // function again, so the only sensible recovery is to delete
	  // everything.
	  m_deallocate_nodes(new_array, n);
	  m_deallocate_buckets(new_array, n);
	  m_deallocate_nodes(m_buckets, m_bucket_count);
	  m_element_count = 0;
	  __throw_exception_again;
	}
    }

然后就是 hash 函数了。hash 函数位于 /usr/include/c++/4.1.2/tr1/functional:1194,对于 std::string,用的是下面这种 hash 函数

  template<>
    struct Fnv_hash<8>
    {
      static std::size_t
      hash(const char* first, std::size_t length)
      {
	std::size_t result = static_cast<std::size_t>(14695981039346656037ULL);
	for (; length > 0; --length)
	  {
	    result ^= (std::size_t)*first++;
	    result *= 1099511628211ULL;
	  }
	return result;
      }
    };

这个叫 FNV hash,http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function,FNV 有分版本,例如 FNV-1 和 FNV-1a,区别其实就是先异或再乘,或者先乘在异或,这里用的是 FNV-1a,为什么呢,维基里面说,The small change in order leads to much better avalanche characteristics,什么叫 avalanche characteristics 呢,这个是个密码学术语,叫雪崩效应,意思是说输入的一个非常微小的改动,也会使最终的 hash 结果发生非常巨大的变化,这样的哈希效果被认为是更好的。

 
目录
相关文章
|
2月前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
2月前
|
存储 设计模式 算法
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
|
2月前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: • 代理模式 • 适配器模式 • 装饰者模式 • 桥接模式 • 外观模式 • 组合模式 • 享元模式
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
37 1
|
21天前
|
自然语言处理 数据处理 索引
mindspeed-llm源码解析(一)preprocess_data
mindspeed-llm是昇腾模型套件代码仓,原来叫"modelLink"。这篇文章带大家阅读一下数据处理脚本preprocess_data.py(基于1.0.0分支),数据处理是模型训练的第一步,经常会用到。
40 0
|
2月前
|
安全 编译器 C++
C++ `noexcept` 关键字的深入解析
`noexcept` 关键字在 C++ 中用于指示函数不会抛出异常,有助于编译器优化和提高程序的可靠性。它可以减少代码大小、提高执行效率,并增强程序的稳定性和可预测性。`noexcept` 还可以影响函数重载和模板特化的决策。使用时需谨慎,确保函数确实不会抛出异常,否则可能导致程序崩溃。通过合理使用 `noexcept`,开发者可以编写出更高效、更可靠的 C++ 代码。
49 1
|
2月前
|
存储 程序员 C++
深入解析C++中的函数指针与`typedef`的妙用
本文深入解析了C++中的函数指针及其与`typedef`的结合使用。通过图示和代码示例,详细介绍了函数指针的基本概念、声明和使用方法,并展示了如何利用`typedef`简化复杂的函数指针声明,提升代码的可读性和可维护性。
97 1
|
3月前
|
缓存 监控 Java
Java线程池提交任务流程底层源码与源码解析
【11月更文挑战第30天】嘿,各位技术爱好者们,今天咱们来聊聊Java线程池提交任务的底层源码与源码解析。作为一个资深的Java开发者,我相信你一定对线程池并不陌生。线程池作为并发编程中的一大利器,其重要性不言而喻。今天,我将以对话的方式,带你一步步深入线程池的奥秘,从概述到功能点,再到背景和业务点,最后到底层原理和示例,让你对线程池有一个全新的认识。
72 12
|
2月前
|
PyTorch Shell API
Ascend Extension for PyTorch的源码解析
本文介绍了Ascend对PyTorch代码的适配过程,包括源码下载、编译步骤及常见问题,详细解析了torch-npu编译后的文件结构和三种实现昇腾NPU算子调用的方式:通过torch的register方式、定义算子方式和API重定向映射方式。这对于开发者理解和使用Ascend平台上的PyTorch具有重要指导意义。

推荐镜像

更多