STL源码分析--hashtable-阿里云开发者社区

0 相关文件

1 函数对象hash

1.1 字符串求哈希

1.2 对数值求哈希

2 hashtable

2.1 hashtable的数据结构

2.2 hashtable的增删查

2.3 hashtable中的迭代器

2.4 hashtable的扩容策略

2.5 hashtable如何实现hash_set/hash_map/hash_multiset/hash_multimap

0 相关文件

stl_hash_fun.h
stl_hashtable.h
hashtable.h

1 函数对象hash

hash是一个函数对象，它对各种不同类型的值进行哈希，并返回size_t类型的哈希值。在x64平台下，size_t的长度为8 Byte。

template <class _Key> struct hash { };

1.1 字符串求哈希

这里的哈希算法还是非常简单的。假设字符串长度为n, 最终哈希值为在

的基础上根据size_t的长度做截断。

__STL_TEMPLATE_NULL struct hash<char*>
{
  size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
}
inline size_t __stl_hash_string(const char* __s)
{
  unsigned long __h = 0; 
  for ( ; *__s; ++__s)
    __h = 5*__h + *__s;
  return size_t(__h);
}

1.2 对数值求哈希

直接将数值强转成size_t即可

__STL_TEMPLATE_NULL struct hash<char> {
  size_t operator()(char __x) const { return __x; }
}
__STL_TEMPLATE_NULL struct hash<short> {
  size_t operator()(short __x) const { return __x; }
}
__STL_TEMPLATE_NULL struct hash<int> {
  size_t operator()(int __x) const { return __x; }
}
__STL_TEMPLATE_NULL struct hash<long> {
  size_t operator()(long __x) const { return __x; }
};

2 hashtable

2.1 hashtable的数据结构

STL中hashtable使用桶+链表实现。

hashtable中模板参数众多，其中

_Val, 链表中每个节点中包含的数据类型。

_Key, 哈希表的key的类型

_HashFcn：用于将key映射到桶中对应的slot。已知_Key值，桶中bucket_slot = _HashFcn(_Key) % buckets_num，其中buckets_num表示桶的大小。

_ExtractKey: 用于将_Key值从_Value值中抽取出来。已知_Value值，key=_ExtractKey(value)。注意：这里切莫将key和value等同于把std::map中的key和value，对应关系稍后见分晓。

_EqualKey: 用于判断两个_Key值是否相等的函数对象(并非所有key的类型都定义了比较函数)

_Alloc: 链表节点的内存分配器

template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
class hashtable {
public:
  typedef _Key key_type;
  typedef _Val value_type;
  typedef _HashFcn hasher;
  typedef _EqualKey key_equal;
...

桶的实现如下，它由一个数组组成。数组中元素类型为指向_Hashtable_node<_Val>结构的指针，数组中每个元素即一个单向链表的header

...
private:
  typedef _Hashtable_node<_Val> _Node;
  vector<_Node*,_Alloc> _M_buckets;
...
template <class _Val>
struct _Hashtable_node
{
  _Hashtable_node* _M_next;
  _Val _M_val;
};

2.2 hashtable的增删查

查找实现如下：

首先使用_HashFcn类型的_M_hash函数对象对__key求哈希值，再对桶的大小取模，得到bucket slot位置

根据bucket slot得到链表，从头到尾遍历该链表，对于每个节点，使用_ExtractKey类型的_M_get_key函数对象从节点中取出key值，再使用_EqualKey类型的函数对象_M_equals判断当前key是否等于__key。如果等于，则返回当前位置对应的迭代器

iterator find(const key_type& __key) 
  {
    size_type __n = _M_bkt_num_key(__key);
    _Node* __first;
    for ( __first = _M_buckets[__n];
          __first && !_M_equals(_M_get_key(__first->_M_val), __key);
          __first = __first->_M_next)
      {}
    return iterator(__first, this);
  }

插入(此为不允许重复版本，允许重复版本留待读者自行分析)实现如下:

首先从__obj中分离出__key, 根据__key找到bucket slot位置，并得到链表头指针

遍历链表，如果发现当前节点的key值等于__key，提前返回; 否则创建新节点，值为__obj，插入到链表头部

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool> 
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::insert_unique_noresize(const value_type& __obj)
{
  const size_type __n = _M_bkt_num(__obj);
  _Node* __first = _M_buckets[__n];
  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
      return pair<iterator, bool>(iterator(__cur, this), false);
  _Node* __tmp = _M_new_node(__obj);
  __tmp->_M_next = __first;
  _M_buckets[__n] = __tmp;
  ++_M_num_elements;
  return pair<iterator, bool>(iterator(__tmp, this), true);
}

删除实现如下：

首先根据__key值找到bucket slot位置，并得到链表头指针

从头到尾遍历链表，如果发现当前节点的key值等于__key, 则删除之

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type 
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key)
{
  const size_type __n = _M_bkt_num_key(__key);
  _Node* __first = _M_buckets[__n];
  size_type __erased = 0;
  if (__first) {
    _Node* __cur = __first;
    _Node* __next = __cur->_M_next;
    while (__next) {
      if (_M_equals(_M_get_key(__next->_M_val), __key)) {
        __cur->_M_next = __next->_M_next;
        _M_delete_node(__next);
        __next = __cur->_M_next;
        ++__erased;
        --_M_num_elements;
      }
      else {
        __cur = __next;
        __next = __cur->_M_next;
      }
    }
    if (_M_equals(_M_get_key(__first->_M_val), __key)) {
      _M_buckets[__n] = __first->_M_next;
      _M_delete_node(__first);
      ++__erased;
      --_M_num_elements;
    }
  }
  return __erased;
}

2.3 hashtable中的迭代器

hashtable中迭代器由两个指针组成，一个指向hashtable，一个指向链表节点。

...
public:
  typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
          iterator;
...
template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
struct _Hashtable_iterator {
  ...
  _Node* _M_cur;
  _Hashtable* _M_ht;
  ...

hashtable迭代器属于前向迭代器，即只能向正向前进无法反向后退(想想为啥无法向后退？)

_Hashtable_iterator::operator++用于迭代器递进，其实现如下：

如果迭代器中_M_cur指针指向的节点在链表尾端，则更新_M_cur指向下一个bucket slot中链表的头部。

如果迭代器中_M_cur指针指向的节点不在链表尾端，则_M_curr = _M_cur->_M_next

template <class _Val, class _Key, class _HF, class _ExK, class _EqK, 
          class _All>
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
{
  const _Node* __old = _M_cur;
  _M_cur = _M_cur->_M_next;
  if (!_M_cur) {
    size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
    while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
      _M_cur = _M_ht->_M_buckets[__bucket];
  }
  return *this;
}

2.4 hashtable的扩容策略

每次insert数据时，判断当前元素数量是否大于桶的大小，如果是，则触发哈希表的扩容策略：

首先创建更大的新桶

将老桶中的所有数据复制到新桶。老桶中数据在新桶上的bucket slot位置需要重新分布。

在新桶上插入元素

注意：这样做容易造成性能不稳定，如果insert正好触发了扩容，则本次操作执行时间将远大于没有扩容的情况

template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
  ::resize(size_type __num_elements_hint)
{
  const size_type __old_n = _M_buckets.size();
  if (__num_elements_hint > __old_n) {
    const size_type __n = _M_next_size(__num_elements_hint);
    if (__n > __old_n) {
      vector<_Node*, _All> __tmp(__n, (_Node*)(0),
                                 _M_buckets.get_allocator());
      __STL_TRY {
        for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
          _Node* __first = _M_buckets[__bucket];
          while (__first) {
            size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
            _M_buckets[__bucket] = __first->_M_next;
            __first->_M_next = __tmp[__new_bucket];
            __tmp[__new_bucket] = __first;
            __first = _M_buckets[__bucket];          
          }
        }
        _M_buckets.swap(__tmp);
      }
  }

2.5 hashtable如何实现hash_set/hash_map/hash_multiset/hash_multimap

首先，对于hash_set或hash_multiset：

_HashFcn缺省为hash函数对象(见1)

_EqualKey缺省为equal_to<_Value>

_Key和_Value类型相同，因为set中只有key, 没有value。

_ExtractKey为_Identify<_Value>``, 即_Value值和_Key`值相等

hash_set和hash_multiset的定义如下, hash_set和hash_multiset唯一的区别在于是否容忍重复key的存在

template <class _Value,
          class _HashFcn  __STL_DEPENDENT_DEFAULT_TMPL(hash<_Value>),
          class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Value>),
          class _Alloc =  __STL_DEFAULT_ALLOCATOR(_Value) >
class hash_set;
template <class _Value,
          class _HashFcn  __STL_DEPENDENT_DEFAULT_TMPL(hash<_Value>),
          class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Value>),
          class _Alloc =  __STL_DEFAULT_ALLOCATOR(_Value) >
class hash_multiset

对于hash_map, hash_multimap:

_HashFcn默认为hash函数对象

_EqualKey默认为equal_to<_Key>, _Value为pair<const _Key, Tp>。已知_Value值，可通过_Select1st<pair<const _Key,_Tp> >得到对应的_Key值

同理，hash_map和hash_multimap的区别在于是否容忍重复key的存在。

template <class _Key, class _Tp,
          class _HashFcn  __STL_DEPENDENT_DEFAULT_TMPL(hash<_Key>),
          class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Key>),
          class _Alloc =  __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map;
template <class _Key, class _Tp,
          class _HashFcn  __STL_DEPENDENT_DEFAULT_TMPL(hash<_Key>),
          class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Key>),
          class _Alloc =  __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_multimap;

STL源码分析--hashtable