STL源码剖析（十六）关联式容器之hashtable

布满荆棘的人生 2023-06-04 03:56 12阅读 0赞

# STL源码剖析（十六）关联式容器之hashtable #

### 文章目录 ###

*  STL源码剖析（十六）关联式容器之hashtable
 *   *  一、hashtable的数据结构
     *  二、hashtable的迭代器
     *  三、hashtable的操作
     *   *  3.1 构造函数
         *  3.2 析构函数
         *  3.3 插入元素
         *  3.4 删除元素
         *  3.5 其他操作

hashtable 是哈希表的意思，它并不是 STL 标准的，也就是 STL 并没有要求实现它。hashtable 并不会对使用者直接开放，它作为 hash\_set、hash\_multiset、hash\_map、hash\_multimap 的底部支撑

在 C++11 中 STL 基于哈希表实现的 set 和 map，叫做 unordered\_set 和 unordered\_map

本文将讨论 hashtable

## 一、hashtable的数据结构 ##

STL 中使用的哈希表是一种比较经典的结构，就是一排bucket，每个bucket都维护一个链表，来解决哈希碰撞，如下所示

![åœ¨è¿™é‡Œæ’å¥å›¾ç‰‡æè¿°][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

下面看一下 hashtable 的定义

template <class Value, class Key, class HashFcn,
              class ExtractKey, class EqualKey,
              class Alloc>
    class hashtable {
      ...
    private:
      hasher hash; //哈希函数
      key_equal equals; //判断key值是否相等
      ExtractKey get_key; //从value中获取key
    
      typedef __hashtable_node<Value> node;
    
      vector<node*,Alloc> buckets; //桶
      size_type num_elements; //元素个数
    
      ...
    };

首先是三个仿函数，这些仿函数都是从模板参数指定的，然后在构造函数中赋值

*  hash：用于获取 key 对应的哈希值，以确定要放到哪一个 bucket 中
 *  equals：用于判断 key 是否相等
 *  get\_key：用于从 value 中取得 key，前面说过 value = key + data

接下来是 buckets 和 num\_elements

*  buckets：维护哈希表的 bucket，是一直指针数组，每个元素都是 node\* 类型
 *  num\_elements：元素的个数

下面再来看哈希表中每个节点的定义

template <class Value>
    struct __hashtable_node
    {
      __hashtable_node* next;
      Value val;
    };

*  next：指向下一个节点的指针
 *  val：该节点对应的value（key+data）

下面再来看 hashtable 的迭代器

## 二、hashtable的迭代器 ##

hashtable 的迭代器定义如下

template <class Value, class Key, class HashFcn,
              class ExtractKey, class EqualKey, class Alloc>
    struct __hashtable_iterator {
      /* STL迭代器的设计规范 */
      typedef forward_iterator_tag iterator_category;
      typedef ptrdiff_t difference_type;
      typedef size_t size_type;
      typedef Value& reference;
      typedef Value* pointer;
    
      node* cur;
      hashtable* ht;
      ...
    };

*  cur：指向当前的节点
 *  ht：指向对应的 hashtable，主要是能够在哈希表中跳转

下面看一下迭代器的操作

**operator++**

template <class V, class K, class HF, class ExK, class EqK, class A>
    __hashtable_iterator<V, K, HF, ExK, EqK, A>&
    __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
    {
      const node* old = cur;
      cur = cur->next; //跳到下一个节点
      if (!cur) { //如果这个 bucket 链表到达尾部，那么跳到下一个 bucket
        size_type bucket = ht->bkt_num(old->val); //当前在哪个bucket中
        
        /* 跳转到下一个不为空的bucket */
        while (!cur && ++bucket < ht->buckets.size())
          cur = ht->buckets[bucket];
      }
      return *this;
    }

首先跳转到下一个节点，如果该节点不为空，那么就返回。如果为空，表示该bucket链表到达底部，那么就跳转到下一个不为空的bucket，首先获取当前 bucket 的位置，然后往后移动，直到 bucket 不为空

**operator**\*

reference operator*() const { return cur->val; }

## 三、hashtable的操作 ##

### 3.1 构造函数 ###

hashtable(size_type n,
              const HashFcn&    hf,
              const EqualKey&   eql)
      : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
    {
      initialize_buckets(n);
    }

首先初始化三个仿函数，然后调用 initialize\_buckets 来初始化哈希表

initialize\_buckets 定义如下

void initialize_buckets(size_type n)
    {
      const size_type n_buckets = next_size(n);
      buckets.reserve(n_buckets);
      buckets.insert(buckets.end(), n_buckets, (node*) 0);
      num_elements = 0;
    }

其中的 buckets 别忘了是一个 vector

首先确定 bucket 的数量，然后通过 reserve 初始化，然后再通过 insert 将所有的 bucket 初始化为 NULL

最后将元素个数填为0

### 3.2 析构函数 ###

~hashtable() { clear(); }

template <class V, class K, class HF, class Ex, class Eq, class A>
    void hashtable<V, K, HF, Ex, Eq, A>::clear()
    {
      for (size_type i = 0; i < buckets.size(); ++i) { //遍历所有的bucket
        node* cur = buckets[i];
        /* 遍历每个bucket链表 */
        while (cur != 0) {
          /* 删除该链表上所有的节点 */
          node* next = cur->next;
          delete_node(cur);
          cur = next;
        }
        buckets[i] = 0;
      }
      num_elements = 0;
    }

首先遍历所有的 bucket，然后遍历对应 bucket 链表的所有元素，调用 delete\_node 将每个节点释放

delete\_node 的定义如下

void delete_node(node* n)
    {
      destroy(&n->val);
      node_allocator::deallocate(n);
    }

首先析构对象，然后再释放内存

### 3.3 插入元素 ###

hash\_table 只支持 insert 方法，有两个 insert，一个是 insert\_unique，不允许键值重复，一个是 insert\_equal ，允许键值重复

**insert\_unique**

插入元素，不允许键值重复

pair<iterator, bool> insert_unique(const value_type& obj)
    {
      resize(num_elements + 1); //确保 bucket 的数目大于元素个数
      return insert_unique_noresize(obj);
    }

首先调用 reseize，确保 bucket 的数目大于元素的个数

resize 的定义如下

template <class V, class K, class HF, class Ex, class Eq, class A>
    void hashtable<V, K, HF, Ex, Eq, A>::resize(size_type num_elements_hint)
    {
      const size_type old_n = buckets.size(); //获取旧的bucket个数
      if (num_elements_hint > old_n) { //如果元素个数大于bucket个数，扩展bucket
        const size_type n = next_size(num_elements_hint); //获取下一个扩展的bucket个数
        if (n > old_n) {
          vector<node*, A> tmp(n, (node*) 0); //定义一个临时的vector
          
          /* 将旧的bucket搬到新的bucket中 */
          for (size_type bucket = 0; bucket < old_n; ++bucket) {
            node* first = buckets[bucket];
            while (first) { //遍历对应的bucket，将所有元素插入到新的bucket中
              size_type new_bucket = bkt_num(first->val, n); //新的bucket位置
              buckets[bucket] = first->next;
              first->next = tmp[new_bucket];
              tmp[new_bucket] = first;
              first = buckets[bucket];          
            }
          }
          /* 交换两个容器的内容 */
          buckets.swap(tmp);
        }
      }
    }

如果元素个数大于bucket个数，那么就需要进行扩容，首先通过 next\_size 获取下一个应该扩容的bucket个数

next\_size 定义如下

static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] =
    {
      53,         97,           193,         389,       769,
      1543,       3079,         6151,        12289,     24593,
      49157,      98317,        196613,      393241,    786433,
      1572869,    3145739,      6291469,     12582917,  25165843,
      50331653,   100663319,    201326611,   402653189, 805306457, 
      1610612741, 3221225473ul, 4294967291ul
    };
    
    /* 获取桶的数量 */
    inline unsigned long __stl_next_prime(unsigned long n)
    {
      const unsigned long* first = __stl_prime_list;
      const unsigned long* last = __stl_prime_list + __stl_num_primes;
      const unsigned long* pos = lower_bound(first, last, n); //>=
      return pos == last ? *(last - 1) : *pos;
    }
    
    size_type next_size(size_type n) const { return __stl_next_prime(n); }

从定义好的数组中，找到第一个大于等于指定值得数

bucket 个数得所有取值定义在 \_\_stl\_prime\_list 数组中

接下俩回到 resize 函数

在获取扩容的bucket个数后，定义一个临时的buckets，然后遍历旧的bucket，获取每个元素新的哈希值，然后插入到新的buckets对应的位置中，最后交换两个buckets

分析完 resize 函数，我们继续回到 insert\_unique 函数

insert\_unique 调用 resize 后，会调用 insert\_unique\_noresize 来插入元素，其定义如下

template <class V, class K, class HF, class Ex, class Eq, class A>
    pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, bool> 
    hashtable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const value_type& obj)
    {
      const size_type n = bkt_num(obj); //计算得到该对象应该存放在哪个bucket
      node* first = buckets[n]; //得到指定的bucket
    
      /* 遍历bucket链表，如果找到相同的key，则插入失败 */
      for (node* cur = first; cur; cur = cur->next) 
        if (equals(get_key(cur->val), get_key(obj))) //如果找到相等的键值，那么就退出
          return pair<iterator, bool>(iterator(cur, this), false);
    
      /* 否则生成新节点，插入到指定的bucket中 */
      node* tmp = new_node(obj);
      tmp->next = first;
      buckets[n] = tmp;
      ++num_elements;
      return pair<iterator, bool>(iterator(tmp, this), true);
    }

首先根据 bkt\_num 计算得到应该插入到哪个 bucket 中，其定义如下

size_type bkt_num_key(const key_type& key, size_t n) const
    {
      return hash(key) % n; //获取哈希值，然后求余，确保计算结果在桶的数量内
    }
    
    size_type bkt_num(const value_type& obj, size_t n) const
    {
      return bkt_num_key(get_key(obj), n);
    }

回到 insert\_unique\_noresize，在计算完应该插入到哪个 bucket 之后，获取指定的 bucket，然后遍历该 bucket 链表，如果该链表上有一个节点的 key 和 插入元素的 key 相等，那么就返回插入失败。否则，生成一个新的节点，然后插入到指定的 bucket 链表中

**insert\_equal**

插入元素，运行键值重复

iterator insert_equal(const value_type& obj)
    {
      resize(num_elements + 1); //确保 bucket 的数目大于元素个数
      return insert_equal_noresize(obj);
    }

首先调用 resize 函数，确保桶的数量大于元素个数，然后调用 insert\_equal\_noresize 插入元素

insert\_equal\_noresize 的定义如下

template <class V, class K, class HF, class Ex, class Eq, class A>
    typename hashtable<V, K, HF, Ex, Eq, A>::iterator 
    hashtable<V, K, HF, Ex, Eq, A>::insert_equal_noresize(const value_type& obj)
    {
      const size_type n = bkt_num(obj); //找到指定的bucket
      node* first = buckets[n];
    
      /* 遍历对应的bucket链表，如果找到key相等的节点，那么就在此处插入 */
      for (node* cur = first; cur; cur = cur->next) 
        if (equals(get_key(cur->val), get_key(obj))) {
          node* tmp = new_node(obj);
          tmp->next = cur->next;
          cur->next = tmp;
          ++num_elements;
          return iterator(tmp, this);
        }
    
      /* 如果没有找到相等的节点，就在bucket链表头插入 */
      node* tmp = new_node(obj);
      tmp->next = first;
      buckets[n] = tmp;
      ++num_elements;
      return iterator(tmp, this);
    }

首先确定要在哪一个bucket插入，然后遍历bucket链表，如果找到相等的节点，那么就在该节点处插入。否则，在bucket链表头插入

### 3.4 删除元素 ###

template <class V, class K, class HF, class Ex, class Eq, class A>
    typename hashtable<V, K, HF, Ex, Eq, A>::size_type 
    hashtable<V, K, HF, Ex, Eq, A>::erase(const key_type& key)
    {
      const size_type n = bkt_num_key(key);
      node* first = buckets[n];
      size_type erased = 0;
    
      if (first) {
        node* cur = first;
        node* next = cur->next;
        while (next) {
          if (equals(get_key(next->val), key)) {
            cur->next = next->next;
            delete_node(next);
            next = cur->next;
            ++erased;
            --num_elements;
          }
          else {
            cur = next;
            next = cur->next;
          }
        }
        if (equals(get_key(first->val), key)) {
          buckets[n] = first->next;
          delete_node(first);
          ++erased;
          --num_elements;
        }
      }
      return erased;
    }

首先找到指定的bucket，然后从第二个元素开始遍历，如果节点的 key 等于指定的 key，将将其删除。最后再检查第一个元素的 key，如果等于指定的 key，那么就将其删除

### 3.5 其他操作 ###

**begin**

指向第一个元素的迭代器

iterator begin()
    { 
      /* 遍历所有bucket，找到第一个不为空的bucket，返回首元素 */
      for (size_type n = 0; n < buckets.size(); ++n)
        if (buckets[n])
          return iterator(buckets[n], this);
        
        return end();
    }

**end**

返回指向结尾的迭代器

iterator end() { return iterator(0, this); }

**find**

查找指定 key 的节点

iterator find(const key_type& key) 
    {
      size_type n = bkt_num_key(key);
      node* first;
      for ( first = buckets[n];
            first && !equals(get_key(first->val), key);
            first = first->next)
        {}
      return iterator(first, this);
    }

首先找到对应的bucket，然后遍历bucket链表查找等于指定 key 的节点

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: /images/20230601/cdb42e5695124ef9846cef8dcfb925bb.png