C++11 标准库源代码分析：连载之八
2018-07-09 本文已影响0人
JackZou
无序关联容器
无序关联容器（Unordered associative container）是C++11标准库中新增的类型，包括
- unordered_set
- unordered_multiset
- unordered_map
- unordered_multimap
共四种类型，它们的共同特点是
-
在容器内部，元素的排列是没有特定顺序的，这也正是它们被叫做“unordered container”的原因。
-
都是通过hast table实现的。这点我们稍后会详细介绍。
标准库中已经有了map和set，为什么还要定义unordered的map和set呢？答案还是那两个字：效率。我们知道，map和set的底层数据结构是红黑树，执行查找、插入，删除等操作的时间复杂度为O(logn)；而unordered map和unordered set的底层数据为hash table，执行查找、插入和删除等操作的时间复杂度为O(1)，明显要快很多，所以如果对元素的排列顺序没有要求，建议使用无序关联容器。
既然无序关联容器都是基于hash table的，那我们就有必要先了解一下C++ 11中的hash算法。
C++ 11中的hash算法
C++ 11标准对如何计算hash有明确的要求：
- hash方程应该是一个
function object，声明如下所示：
template<T>
struct hash {
size_t operator()(T key) const noexcept;
};
-
对于类型为
T的参数t1和t2，如果t1 == t2，则hash<T>()(t1) == hash<T>()(t2); -
对于类型为
T的参数t1和t2，如果t1 != t2，则hash<T>()(t1) == hash<T>()(t2)的概率应近似于1.0/std::numeric_limits<size_t>::max()（在我的MacBook Pro上，这个值为0.00000000000000000005.421，小数点后面19个0）。
不过，C++标准只是规定了hash方程的形式和必须满足的条件，具体到如何计算hash值，则没有要求。就libc++而言，针对不同的类型，其计算方法也不尽相同。
简单数值类型
对于简单数值类型，如bool、int、char等，libc++的hash算法也很简单：直接返回数值本身。
// header: <functional>
template<class T> struct hash; // forward declaration
// specialization for bool
template<>
struct hash<bool> : pubic unary_function<bool, size_t> {
size_t operator()(bool value) const noexcept {
return static_cast<size_t>)(value);
}
};
// specialization for int
template<>
struct hash<int> : public unary_function<int, size_t> {
size_t operator()(int value) const noexcept {
return static_cast<size_t>(value);
}
};
// specialization for char
template<>
struct hash<char> : pubic unary_function<char, size_t> {
size_t operator(char value) const noexcept {
return static_cast<size_t>(value);
}
};
浮点数值类型
针对复杂数值类型，如float、double等，libc++提供了两种hash算法：murmur2和cityhash64：
// header: <memory>
template<class Size, size_t = sizeof(Size) * 8>
struct murmur2_or_cityhash;
// use murmur2 on 32-bit system,
// because size_t is 32 bits on 32-bit system
template<class Size>
struct murmur2_or_cityhash<Size, 32> {
Size operator()(const void* key, Size len) {
// murmur2 hash算法
...
}
};
// use cityhash64 on 64-bit system,
// because size_t is 64 bits on 64-bit system
template<class Size>
struct murmur2_or_cityhash<Size, 64> {
Size operator()(const void* key, Size len) {
// cityhash64 hash算法
...
}
};
murmur2_or_cityhash::operator()接受两个参数，并不满足C++标准的要求，为了方便使用，libc++又定义了一个外敷类scalar_hash：
template<class T, size_t = sizeof(T) / sizeof(size_t)>
struct scalar_hash;
template<class T>
struct scalar_hash<T, 0> : public unary_function<T, size_t> {
size_t operator()(T value) const {
union {
T t;
size_t a;
} _u;
_u.a = 0;
_u.t = value;
return _u.a;
}
};
template <class T>
struct scalar_hash<T, 1> : public unary_function<T, size_t> {
size_t operator()(T value) const {
union{
T t;
size_t a;
} _u;
_u.t = value;
return _u.a;
}
};
template <class T>
struct scalar_hash<T, 2> : public unary_function<T, size_t> {
size_t operator()(Tp value) const {
union {
Tp t;
struct {
size_t a;
size_t b;
} s;
} _u;
_u.t = value;
return murmur2_or_cityhash<size_t>()(&_u, sizeof(_u));
}
};
template <class T>
struct scalar_hash<T, 3> : public unary_function<T, size_t> {
size_t operator()(T value) const {
union {
T t;
struct {
size_t _a;
size_t _b;
size_t _c;
} s;
} _u;
_u.t = value;
return murmur2_or_cityhash<size_t>()(&_u, sizeof(_u));
}
};
template <class T>
struct scalar_hash<T, 4> : public unary_function<T, size_t> {
size_t operator()(T value) const {
union {
T t;
struct {
size_t a;
size_t b;
size_t c;
size_t d;
} s;
} _u;
_u.t = value;
return murmur2_or_cityhash<size_t>()(&_u, sizeof(_u));
}
};
浮点数值类型最终的hash计算方法如下：
template <>
struct hash<float> : public scalar_hash<float> {
size_t operator()(float value) const
{
// -0.0 and 0.0 should return same hash
if (value == 0)
return 0;
return scalar_hash<float>::operator()(value);
}
};
template <>
struct hash<double> : public scalar_hash<double> {
size_t operator()(double value) const
{
// -0.0 and 0.0 should return same hash
if (value == 0)
return 0;
return scalar_hash<double>::operator()(value);
}
};
内置非数值类型
对于标准库中的非数值类型，比如string等，标准库也提供了hash方程：
// header: <string>
template<class CharT, class Traits, class Allocator>
struct hash<basic_string<CharT, Traits, Allocator> >
: public unary_function<basic_string<CharT, Traits, Allocator>, size_t> {
size_t operator()(const basic_string<CharT, Traits, Allocator>& val) const noexcept;
};
template<class CharT, class Traits, class Allocator>
size_t hash<basic_string<CharT, Traits, Allocator> >::operator()(
const basic_string<CharT, Traits, Allocator>& val) const noexcept {
return __do_string_hash(val.data(), val.data() + val.size());
}
__do_string_hash定义在文件<__string>中：
// header: <__string>
template<class Ptr>
inline size_t __do_string_hash(Ptr p, Ptr e) {
typedef typename iterator_traits<Ptr>::value_type value_type;
return murmur2_or_cityhash<size_t>()(p, (e-p)*sizeof(value_type));
}
自定义类型
如果你有一个类，
struct Foo {
int _i;
double _d;
std::string _s;
Foo(int i, double d, const std::string &s)
: _i(i), _d(d), _s(s) {}
};
你可以这样计算hash：
template<>
struct hash<Foo> : public unary_function<Foo, size_t> {
size_t operator()（const Foo& foo）const noexcept {
return murmur2_or_cityhash<size_t>()
(static_cast<const void*>(&foo), sizeof(Foo));
}
};
现在我们已经对hash算法有所了解，接下来我们就讲讲那些基于hash算法的容器是如何实现的。虽然C++ 11标准库中基于hash算法的容器一共有四种，但是它们的实现方式大同小异，所以我们就讲讲最典型的hash容器：unordered_map。
unordered_map
首先来看unordered_map的声明：
// file: unordered_map
template<class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_key>,
class _Alloc = allocator<pair<const _Key, _Tp> > >
class unordered_map {
public:
// types
typedef _Key key_type;
typedef _Tp mapped_type;
typedef _Hash hasher;
typedef _Pred key_equal;
typedef _Alloc allocator_type;
typedef pair<const key_type, mapped_type> value_type;
typedef pair<key_type, mapped_type> __nc_value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
private:
typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
__table __table_;
// ...
};
可以看到unordered_map的实现采用了Pimpl idiom，unordered_map只是个wrapper，真正的实现是在__hash_table中。要讲清楚__hash_table不是一件容易的事情，好在libc++的__hash_table从技术上讲并没有什么奇特之处，仍然采用了大家都很熟悉的bucket list形式，如下图所示：
下面正式进入__hash_table：
template<class _Tp, class _Hash, class _Equal, class _Alloc>
class __hash_table {
public:
typedef _Tp value_type;
typedef _Hash hasher;
typedef _Equal key_equal;
typedef _Alloc allocator_type;
private:
typedef std::allocator_traits<allocator_type> __alloc_traits;
typedef typename __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;
public:
typedef typename _NodeTypes::__node_value_type __node_value_type;
typedef typename _NodeTypes::__container_value_type __container_value_type;
typedef typename _NodeTypes::key_type key_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename __alloc_traits::pointer pointer;
typedef typename __alloc_traits::const_pointer const_pointer;
typedef typename __alloc_traits::size_type size_type;
typedef typename _NodeTypes::difference_type difference_type;
public:
// Create __node
typedef typename _NodeTypes::__node_type __node;
typedef typename std::__rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
typedef std::allocator_traits<__node_allocator> __node_traits;
typedef typename _NodeTypes::__void_pointer __void_pointer;
typedef typename _NodeTypes::__node_pointer __node_pointer;
typedef typename _NodeTypes::__node_pointer __node_const_pointer;
typedef typename _NodeTypes::__node_base_type __first_node;
typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
typedef typename _NodeTypes::__next_pointer __next_pointer;
private:
typedef typename std::__rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
typedef std::__bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
typedef std::unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
typedef std::allocator_traits<__pointer_allocator> __pointer_alloc_traits;
typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
// --- Member data begin ---
__bucket_list __bucket_list_;
std::pair<__first_node, __node_allocator> __p1_;
std::pair<size_type, hasher> __p2_;
std::pair<float, key_equal> __p3_;
public:
size_type size() const noexcept { return __p2_.first();}
float max_load_factor() const noexcept { return __p3_.first();}
};
我们来梳理一下，每一个__hash_table都有一个__bucket_list_：
__bucket_list __bucket_list_
而__bucket_list_是一个smart pointer：
typedef typename __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;
typedef typename _NodeTypes::__next_pointer __next_pointer;
typedef std::unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
这里的关键就是__make_hash_node_types：
template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
struct __hash_node_types;
template <class _NodePtr, class _Tp, class _VoidPtr>
struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
: public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>{
typedef _NodePtr __node_pointer;
typedef __hash_node_base<__node_pointer> __node_base_type;
typedef typename __node_base_type::__next_pointer __next_pointer;
// ...
};
template<class _NodeValueTp, class _VoidPtr>
struct __make_hash_node_types {
typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
typedef typename std::__rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;
typedef __hash_node_types<_NodePtr> type;
};
经过这一连串让人头晕目眩的类型代换后，__bucket_list_大致可以写成：
typedef std::pair<Key, Value> _Tp;
typedef __hash_node<_Tp, _VoidPtr>* _NodePtr;
typedef typename __hash_node_base<_NodePtr>::__next_pointer __next_pointer;
std::unique_ptr<__next_pointer[]> __bucket_list_;
__hash_node和__hash_node_base就是一切开始的地方：
// file: __hash_table
template<class _NodePtr>
struct __hash_node_base {
typedef typename std::pointer_traits<_NodePtr>::element_type __node_type;
typedef __hash_node_base __first_node;
typedef typename std::__rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;
typedef _NodePtr __node_pointer;
typedef __node_base_pointer __next_pointer;
__next_pointer __next_;
};
template<class _Tp, class _VoidPtr>
struct __hash_node
: public __hash_node_base<typename std::__rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type> {
typedef _Tp __node_value_type;
size_t __hash_;
__node_value_type __value_;
};
纵观源代码，我们会发现90%的代码其实都是类型定义和代换，大量的typedef让人头晕目眩，真不知道这样的代码是怎样构思出来的，又是怎样测试的。
写了这么多，也仅仅是了解了__hash_table的声明而已。篇幅有限，我们不能详细讲解__hash_table具体的实现了，就挑两个方法讲一下吧：
默认构造函数
默认构造函数非常简单：
// file: __hash_table
template<class _Tp, class _Hash, class _Equal, class _Alloc>
inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
: __p2_(0), __p3(1.0f) {
}
插入元素
源代码有点复杂，不过只要看懂了__hash_table声明部分的代码，这部分代码相对来说还是比较容易的。
// file: unordered_map
pair<iterator, bool> insert(const value_type& __) {
return __table_.__insert_unique(__x);
}
// file: __hash_table
pair<iterator, bool> __insert_unique(__container_value_type&& __x) {
return __emplace_unique_key_args(_NodeType::__get_key(__x), std::move(__x));
}
template<class _Tp, class _Hash, class _Equal, class _Alloc>
template<class _key, class ..._Args>
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
size_t __hash = hash_function()(__k);
size_type __bc = bucket_count();
bool __inserted = false;
__next_pointer __nd;
size_t __chash;
if (__bc != 0) {
__chash = __constrain_hash(__hash, __bc);
__nd = __bucket_list_[_chash];
if (__nd != nullptr) {
for (__nd = __nd->next; __nd != nullptr && (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
__nd = __nd->__next_) {
if (key_eq()(__nd->__upcast()->__value, __k))
goto __done;
}
}
}
{
__node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
// rehash
}
__next_pointer __pn = __bucket_list_[__chash];
if (__pn == nullptr) {
__pn = __p1_.first().__ptr();
__h->__next_ = __pn->__next_;
__pn->__next_ = __h.get()->__ptr();
__bucket_list_[__chash] = __pn;
if (__h->__next_ != nullptr)
__bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
}
else {
__h->__next_ = __pn->__next_;
__pn->__next_ = static_cast<__next_pointer>(__h.get());
}
__nd = static_cast<__next_pointer>(__h.release());
++size();
__inserted = true;
}
__done:
return pair<iterator, bool>(iterator(__nd), __inserted);
}
小结
对unordered_map的到此算是告一段落，至于其余三个unordered容器，它们的实现方法大同小异，就不一一赘述了。
