unordered_set 算法剖析

2015年3月12日 23:28

从C转到C++时，被内部结构为红黑树的 set 的吸引，他的存在让我从手写二叉树的痛苦中解脱。

C++11 后我被 unordered_set  的执行效率深深的折服。于是写了这篇博客来解析下 unordered_set 的内部结构和实现细节。

本文使用 libstdc++-v3 的源代码进行分析，其他库或不同版本的库可能会略有不同。

unordered_set 内部结构

unordered_set 继承自 __unordered_set 继承自 _Hashtable。_Hashtable 维护一个数组形式的哈希表(bucket)，并且使用拉链法解决冲突。__unordered_set 构造函数中预设bucket的大小为10。

接下来从hash值计算，hash表扩容与缩容，自定义类型使用 unordered_set 三个方面来剖析 unordered_set。

hash 值的计算

将key 哈希成一个 size_t 类型的变量，然后用它对 bucket 的大小取模算得hash值。

内建数据类型的 hash

unordered_set 为内建数据类型提供了默认的hash函数。那么这些hash函数是怎么实现的呢？

查阅libstdc++-v3源代码 /include/tr1/functional_hash.h 可知

std::hash 被定义成一个仿函数模版，其返回值为 size_t。

  1. 基本上所有整数数据类型的 hash 函数只是简单的把数值强转(static_cast)为size_t 类型。这些类型包括：指针类型, `bool`, `char`, `unsigned char`, `wchar_t`, `short`, `int`, `long`, `long long`, `unsigned short`, `unsigned int`, `unsigned long`, `unsigned long long
  2. float, double, long double 的hash分别有对应的函数进行
    1. float: 如果值等于0.0f 则为0，否则使用下面函数计算hash 
         template<>
    struct _Fnv_hash_base<4>
    {
      template<typename _Tp>
        static size_t
        hash(const _Tp* __ptr, size_t __clength)
        {
	  size_t __result = static_cast<size_t>(2166136261UL);
	  const char* __cptr = reinterpret_cast<const char*>(__ptr);
	  for (; __clength; --__clength)
	    {
	      __result ^= static_cast<size_t>(*__cptr++);
	      __result *= static_cast<size_t>(16777619UL);
	    }
	  return __result;
	}
    };
    2. double: 如果值等于0.0 则为0，否则使用下面函数计算hash值  
        template<>
    struct _Fnv_hash_base<8>
    {
      template<typename _Tp>
        static size_t
        hash(const _Tp* __ptr, size_t __clength)
        {
	  size_t __result
	    = static_cast<size_t>(14695981039346656037ULL);
	  const char* __cptr = reinterpret_cast<const char*>(__ptr);
	  for (; __clength; --__clength)
	    {
	      __result ^= static_cast<size_t>(*__cptr++);
	      __result *= static_cast<size_t>(1099511628211ULL);
	    }
	  return __result;
	}
    };
    3. long double: 这个类型使用的比较少，hash值计算也比较特殊，这里就不贴源代码了，如需查阅，请看 /src/hash-long-double-tr1-aux.cc。
  3. string 和 wstring 最终都是通过如下hash函数计算hash值  
      template<size_t>
    struct _Fnv_hash_base
    {
      template<typename _Tp>
        static size_t
        hash(const _Tp* __ptr, size_t __clength)
        {
	  size_t __result = 0;
	  const char* __cptr = reinterpret_cast<const char*>(__ptr);
	  for (; __clength; --__clength)
	    __result = (__result * 131) + *__cptr++;
	  return __result;
	}
    };

​用户自定义数据类型的hash函数

用户自定义类型设置 hash 有两种方法

1. 用户自定义类型重载函数类型转换接口`size_t operator()(_Tp __val) const;` 进行类型转换

2. 使用自定义仿函数进行哈希，形如 unordered_set<Point, point_hash_functional>  point_set;

hash 表扩容

查阅/include/tr1/unordered_set.h 可知unordered_set 使用__detail::_Prime_rehash_policy 进行扩容和缩容控制。_Prime_rehash_policy 包含一个 _M_max_load_factor（最大负载因子）和一个_M_growth_factor（扩容因子）。最大负载因子的默认值为1，扩容因子默认值为2.0。

扩容

当向unordered_set 中添加k个元素时，如果插入这k歌元素后，负载因子大于最大负载因子时进行扩容。扩充后的容量为__prime_list(素数列表)中大于等于 max((当前大小+k)/负载因子), 当前大小 * _M_growth_factor) 的数。这个素数列表定义在 /src/shared/hashtable-aux.cc 中，一共有257个素数(sizeof(unsigned long)==4)。

判断是否扩容的代码如下：

  inline std::pair<bool, std::size_t>
  _Prime_rehash_policy::
  _M_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* __p =
	      std::lower_bound(__prime_list, __prime_list + _S_n_primes,
			       __min_bkts);
	    _M_next_resize = static_cast<std::size_t>
	      (__builtin_ceil(*__p * _M_max_load_factor));
	    return std::make_pair(true, *__p);
	  }
	else 
	  {
	    _M_next_resize = static_cast<std::size_t>
	      (__builtin_ceil(__n_bkt * _M_max_load_factor));
	    return std::make_pair(false, 0);
	  }
      }
    else
      return std::make_pair(false, 0);
  }

素数表如下：

namespace __detail
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
  extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
  {
    2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
    37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
    83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
    157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
    277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
    503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
    953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
    1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
    3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
    5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
    11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
    19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
    33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
    57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
    99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
    159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
    256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
    410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
    658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
    1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
    1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
    2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
    4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
    6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
    11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
    16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
    24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
    36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
    54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
    80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
    118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
    176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
    260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
    386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
    573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
    849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
    1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul,
    1866894511ul, 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul,
    2767159799ul, 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul,
    4101556399ul, 4294967291ul,
    // Sentinel, so we don't have to test the result of lower_bound,
    // or, on 64-bit machines, rest of the table.
#if __SIZEOF_LONG__ != 8
    4294967291ul
#else
    6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul,
    25769803693ul, 34359738337ul, 51539607367ul, 68719476731ul,
    103079215087ul, 137438953447ul, 206158430123ul, 274877906899ul,
    412316860387ul, 549755813881ul, 824633720731ul, 1099511627689ul,
    1649267441579ul, 2199023255531ul, 3298534883309ul, 4398046511093ul,
    6597069766607ul, 8796093022151ul, 13194139533241ul, 17592186044399ul,
    26388279066581ul, 35184372088777ul, 52776558133177ul, 70368744177643ul,
    105553116266399ul, 140737488355213ul, 211106232532861ul, 281474976710597ul,
    562949953421231ul, 1125899906842597ul, 2251799813685119ul,
    4503599627370449ul, 9007199254740881ul, 18014398509481951ul,
    36028797018963913ul, 72057594037927931ul, 144115188075855859ul,
    288230376151711717ul, 576460752303423433ul,
    1152921504606846883ul, 2305843009213693951ul,
    4611686018427387847ul, 9223372036854775783ul,
    18446744073709551557ul, 18446744073709551557ul
#endif
  };
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail

缩容

unordered_set 可以自动扩容，但是无法自动缩容。用户可以使用  rehash(size_type n) 进行缩容，该函数将hash容量调整成在__prime_list 中，大于等于n并且使负载因子小于等于最大负载因子的数。当然该函数也可以用于扩容。

不管是扩容还是缩容，都需要对所有的数进行重新hash 所有扩容和缩容的时间复杂度至少是 O(n) 的。

 

自定义类型使用 unordered_set 

前面已经说过，自定义hash 函数的两种方法。除此之外，要使用 unordered_set 还需要自定义类型是可判断相等的，也就是重载了 operator == 或者是有全局的 operator==()运算。

技巧与注意事项

  1. 当自定义类型中有多个整数类型参与计算hash值时，可以通过位运算得到hash值，如 struct Point{ int x, y; } 可以用 hash = size_t(x) << (sizeof(size_t) * 4) | y;
  2. 当自定义类型中有一个或多个字符串类型，可以调用std::hash 函数计算单个字符串的hash值。并将所有部分的hash做异或操作设置为整体的hash值。如：struct City{ double lat, lon; string name; } 可以用 hash = std::hash<double>()(lon) ^ std::hash<double>()(lat) ^ std::hash<string>()(name);
  3. 对于 char * str类型，std::hash<char*>()(str) 只是更具指针进行hash，std::hash<string>()(str) 才是更具指向的内容hash

Posted by xhSong Filed in C++ Tagged by hash unordered_set hashtable Comments[1]