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]

c++11, shared_ptr使用数组

2014年8月19日 21:52

最近被项目垃圾的内存管理搞的特别头大，正好这段时间在看《深入理解C++11：C++11新特性解析与应用》，了解了些c++11的特性。于是想着用c++11高大上的智能指针来做内存管理。

所谓高大上，相对于各种天生就支持垃圾回收的语言（如：java，python）来说也是个废才。支持个数组都麻烦的很，各方考证，下面写一个关于 shared_ptr 使用数组的小样例，主要参考 http://stackoverflow.com/questions/14957359/problems-with-shared-ptrt-wrapping-a-dynamic-array

基于shared_ptr的vector

下面是一个基于shared_ptr的vector模板。当然完全没有必要使用 shared_ptr去实现vector，vector的内存管理本来就是透明的。这个地方就是为了展示shared_ptr怎么使用数组。

template <class T>
class Vector {
    shared_ptr<T> ptr_;
    int size_, capacity_;
public:
    
    Vector()
    :ptr_(shared_ptr<T>(new T[initial_capacity], std::default_delete<T[]>())),
    capacity_(initial_capacity), size_(0) {}
    
    int size() const {
        return size_;
    }
    
    void push_back(const T &x) {
        if (size_ == capacity_) {
            capacity_ *= 2;
            T* new_memory = new T[capacity_];
            for (int i = 0; i < size_; ++i) {
                new_memory[i] = ptr_.get()[i];
            }
            ptr_ = shared_ptr<T>(new_memory, std::default_delete<T[]>());
        }
        ptr_.get()[size_++] = x;
    }
    
    const T& operator[] (int idx) const {
        return ptr_.get()[idx];
    }
    
    T& operator[] (int idx) {
        return ptr_.get()[idx];
    }
    static const int initial_capacity = 2;
};

这里有两个必须要注意的地方

  1. 除了使用指向内存的指针初始化 shared_ptr外，还需要传入析够数组的函数。不然当内存的引用数降到0时，会调用 delete 释放一个数组，直接导致程序崩溃，std::default_delete<T[]>()指明调用的是 delete[] 
    shared_ptr<T>(new T[size], std::default_delete<T[]>());
  2. 既然没有直接支持数组，shared_ptr 也就没有重载 operator [] 了。查看相关文档https://gcc.gnu.org/onlinedocs/gcc-4.6.0/libstdc++/api/a00267.html才知道，shared_ptr 只支持了两个 operator，外加一个获取内存指针的get方法 
    std::add_lvalue_reference< _Tp >::type operator* () const
_Tp * operator-> () const;
_Tp * get () const;
    因此想要通过下标访问数组元素就可以使用get() 获取原始数组指针，然后使用[]访问，或者直接把这个操作封装起来 
    T& operator[] (int idx) {
    return ptr_.get()[idx];
}

简单的测试

最后写一个简单的测试程序测试下 Vector 是不是能够zhe，测试程序如下：

class Point {
public:
    Point(int x = 0, int y = 0) { ++counter_; }
    ~Point() { --counter_; }
    static int counter() { return counter_; }
    int x, y;
private:
    static int counter_;
};

int Point::counter_ = 0;

void test_function() {
    Vector<Point> vec;
    Point p;
    for (int i = 0; i < 4; ++i) {
        p.x = i;
        vec.push_back(p);
    }
    cout << vec[vec.size() - 1].x << endl;
}

int main(int argc, const char * argv[]) {
    test_function();
    cout << Point::counter() << endl;
    return 0;
}

测试程序输出如下：

3
0

最后一行输出0，说明 test_function函数退出后 Point 类全部析够，正常！

Posted by xhSong Filed in C++ Tagged by 数组 array c++11 shared_ptr 智能指针 Comments[6]