STL之hashtable详解

川长思鸟来 2022-05-29 13:27 182阅读 0赞

# hash介绍 #

前面讲解二叉树实现键和值的存储。平衡二叉树就是插入和搜寻的速度非常快。那么我们是否可以使用一种方法，将键和值都存在在一段连续的空间内呢？可以，我们只需要将键通过一个函数映射成一个整数即可。这样在时间和空间上面做到了平衡，因为查找很快，索引也很快。关键在于散列函数和碰撞处理，很简单，具体可以[参考。][Link 1]  
\*\*碰撞处理主要是线性分离（通过链表处理）和线性探测。\*\*SGI-STL采用了线性分离的方法。  
![这里写图片描述][70]  
从上图可知，指针数组通过vector，将字符串通过hash函数算出一个索引，然后将元素插入到索引数组对应的链表中。当元素过多的时候，碰撞过多，可能链表过长。这就会导致增加指针数组的维度，vector内存扩展，并且将以前元素全部重新插入。

# hashtable迭代器 #

迭代器的设计：前进操作首先尝试从目前节点出发，前进一个位置。如果目前正巧到达节点尾端，就必须可以跳到下一个（bucket身上）链表，指向其中的第一个节点。所以迭代器设计里面存储了两个指针，下面是迭代器重要的源码：  
![这里写图片描述][70 1]

template <class Value>
    struct __hashtable_node//链表存储键和值合并为Value类型，所以node长出这个样子
    {
      __hashtable_node* next;
      Value val;
    };
    
    template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
    struct __hashtable_iterator {
      typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;
      typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
      typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;
      typedef __hashtable_node<Value> node;
      typedef forward_iterator_tag iterator_category;
      typedef Value value_type;
      typedef ptrdiff_t difference_type;
      typedef size_t size_type;
      typedef Value& reference;
      typedef Value* pointer;
    
      node* cur;//指向链表中节点
      hashtable* ht;//指向hashtable本身，hashtable里面维护这vector，所以可以获取buket
    
      __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
      __hashtable_iterator() {}
    
      reference operator*() const { return cur->val; }//就是返回迭代器指向节点的Value
      pointer operator->() const { return &(operator*()); }//返回迭代器指向节点的Value指针
      iterator& operator++();
      iterator operator++(int);
      bool operator==(const iterator& it) const { 
          return cur == it.cur; //其实就是比较迭代器指向节点的指针
      }
      bool operator!=(const iterator& it) const { 
          return cur != it.cur;//其实就是比较迭代器指向节点的指针 
      }
    };

上述迭代器最重要的就是变量`cur`和`ht`，通过这两个指针，就可以遍历整个容器内部的元素。hashtable迭代器并没有重载`operator--()`，并没有定义逆序迭代器。下面重点分析`operator++()`。

template <class V, class K, class HF, class ExK, class EqK, class A>
    __hashtable_const_iterator<V, K, HF, ExK, EqK, A>&
    __hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++()//++ite
    {
      const node* old = cur;
      cur = cur->next;//找到下一个节点
      if (!cur) {
       //如果为空，则碰到当前链表尾部，需要跳转到下一个链表
        size_type bucket = ht->bkt_num(old->val);//获取当前链表对应指针数组的索引（找到篮子）
        while (!cur && ++bucket < ht->buckets.size())
          cur = ht->buckets[bucket];//通过ht获取下一个cur，直接++即可，如果下一个vector[bucket]非空，即是下一个链表头结点。
      }
      return *this;
    }

template <class V, class K, class HF, class ExK, class EqK, class A>
    inline __hashtable_iterator<V, K, HF, ExK, EqK, A>
    __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
    {
      iterator tmp = *this;
      ++*this;//调用前缀++，实现后缀++
      return tmp;
    }

上述迭代器重载方法就是为了找到下一额节点。实现起来很简单，这些东西都是配合其他数据结构一起使用的。

# hashtable数据结构 #

重要在于传入的6个参数，下面注释已经说明了参数的含义。下面慢慢解释对应的操作函数。一个hashtable容器其实就仅仅需要24字节控制而已，内部全部通过指针操作。

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
    };//指针数组vector的初始维度从这里面取，防止扩充计算。首先vector会是53素数大小
    
    
    /* Value:键和值的合体叫做Value Key:key节点键的类别 HashFcn:hash函数 ExtractKey:如何从Value里面提取出Key(函数或者仿函数) EqualKey:如何比较key(函数或者仿函数) Alloc:内存分配 */
    
    template <class Value, class Key, class HashFcn,
              class ExtractKey, class EqualKey,
              class Alloc>
    class hashtable {
    public:
      typedef Key key_type;
      typedef Value value_type;
      typedef HashFcn hasher;
      typedef EqualKey key_equal;
    
      typedef size_t            size_type;
      typedef ptrdiff_t         difference_type;
      typedef value_type*       pointer;
      typedef const value_type* const_pointer;
      typedef value_type&       reference;
      typedef const value_type& const_reference;
    
      hasher hash_funct() const { return hash; }
      key_equal key_eq() const { return equals; }
    
    //私有变量5个变量
    private:
      hasher hash;        //仿函数为空 1字节
      key_equal equals;   //仿函数为空 1字节
      ExtractKey get_key; //仿函数为空 1字节
    
      typedef __hashtable_node<Value> node;//链表节点定义
      typedef simple_alloc<node, Alloc> node_allocator;//分配一个节点内存
    
      vector<node*,Alloc> buckets;//bucket是指针数组，存储链表头指针 12字节 
      size_type num_elements;//元素个数 4字节
      //总共19字节，然后4字节对齐，占用24字节。
    
      void initialize_buckets(size_type n)//初始化buckets（vector）大小
      {
        const size_type n_buckets = next_size(n);//返回最接近n并大于n的质数
        buckets.reserve(n_buckets);
        buckets.insert(buckets.end(), n_buckets, (node*) 0);//并将vector里面元素全部清0
        num_elements = 0;
      } 
    
    //hashtable返回开始和结束的迭代器
      iterator begin()
      { 
        for (size_type n = 0; n < buckets.size(); ++n)
          if (buckets[n])
            return iterator(buckets[n], this);//node和当前hashtable指针初始化
        return end();
      }
      iterator end() { return iterator(0, this); }//尾部node为0，表示没有元素
    
    
    
    
    //hashtable提供的构造函数，作用在于构造内部参数/
    //构造函数
    hashtable(size_type n,
                const HashFcn&    hf,
                const EqualKey&   eql,
                const ExtractKey& ext)
        : hash(hf), equals(eql), get_key(ext), num_elements(0)
      {
        initialize_buckets(n);
      }
     //构造重载，通过ExtractKey()生成临时对象，初始化get_key
      hashtable(size_type n,
                const HashFcn&    hf,
                const EqualKey&   eql)
        : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
      {
        initialize_buckets(n);
      }
     //通过ht初始化ht，这个也不复杂。
      hashtable(const hashtable& ht)
        : hash(ht.hash), equals(ht.equals), get_key(ht.get_key), num_elements(0)
      {
        copy_from(ht);
      }
      ~hashtable() { clear(); }//析构hashtable占用的内存。
    //hashtable///
    
        hashtable& operator= (const hashtable& ht)
      {
        if (&ht != this) {
          clear();
          hash = ht.hash;
          equals = ht.equals;
          get_key = ht.get_key;
          copy_from(ht);
        }
        return *this;
      }//重载=运算符,赋值运算符
      //重载==运算符
      friend bool
      operator== __STL_NULL_TMPL_ARGS (const hashtable&, const hashtable&);
    
    
      //当插入元素时候，需要考虑hashtable是否需要重新建立表格，当链表节点元素和
      //buckets大小一样时候，那么需要重新分配buckets并重新将元素插入hashtable
      //这个过程比较复杂，可以暂时不用考虑了，返回pair对象,因为这里的key不能重复。
      pair<iterator, bool> insert_unique(const value_type& obj)
      {
        resize(num_elements + 1);//是否需要重建表格，重建表格涉及到内存分配，加上重新插入的过程，非常复杂。内部代码不必深究。
        return insert_unique_noresize(obj);//插入，并返回迭代器，和是否成功。
      }
    
      //这里的key可以重复，因此返回一个新节点的迭代器，这是必须的。
      iterator insert_equal(const value_type& obj)
      {
        resize(num_elements + 1);
        return insert_equal_noresize(obj);
      }
    
    //比较两个hashtable是否相等，每个元素必须是相等的，才相等。这个方法没多大用
    template <class V, class K, class HF, class Ex, class Eq, class A>
    bool operator==(const hashtable<V, K, HF, Ex, Eq, A>& ht1,
                    const hashtable<V, K, HF, Ex, Eq, A>& ht2)
    {
      typedef typename hashtable<V, K, HF, Ex, Eq, A>::node node;
      if (ht1.buckets.size() != ht2.buckets.size())
        return false;
      for (int n = 0; n < ht1.buckets.size(); ++n) {
        node* cur1 = ht1.buckets[n];
        node* cur2 = ht2.buckets[n];
        for ( ; cur1 && cur2 && cur1->val == cur2->val;
              cur1 = cur1->next, cur2 = cur2->next)
          {}
        if (cur1 || cur2)
          return false;
      }
      return true;
    } 
    
    //找出含有key值节点的个数，先hash，然后在对应篮子里面找
     size_type count(const key_type& key) const
      {
        const size_type n = bkt_num_key(key);
        size_type result = 0;
    
        for (const node* cur = buckets[n]; cur; cur = cur->next)
          if (equals(get_key(cur->val), key))
            ++result;
        return result;
      }
     //找出篮子中节点的个数
     size_type elems_in_bucket(size_type bucket) const
      {
        size_type result = 0;
        for (node* cur = buckets[bucket]; cur; cur = cur->next)
          result += 1;
        return result;
      }
      //返回篮子个数，vector大小
    size_type bucket_count() const { return buckets.size(); }

其中桶子的大小通过`next_size`函数从 `__stl_prime_list`数组中取。实现起来就比较简单了。

/* 将计算出来的hash值取余，对应到 */
      size_type bkt_num_key(const key_type& key) const
      {
        return bkt_num_key(key, buckets.size());
      }
      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) const//获取key的hash值并对N取模获取key和value应该放在第几个链表。
      {
        return bkt_num_key(get_key(obj));
      }
    
      size_type bkt_num(const value_type& obj, size_t n) const//n对应与vector的大小
      {
        return bkt_num_key(get_key(obj), n);
      }
    
      //返回，含有key节点的迭代器，这是const类型，不允许通过其修改值，没有则返回(0,this)
      const_iterator find(const key_type& key) const
      {
        size_type n = bkt_num_key(key);
        const node* first;
        for ( first = buckets[n];
              first && !equals(get_key(first->val), key);
              first = first->next)
          {}
        return const_iterator(first, this);
      }

当迭代器++的时候，需要从Value类型，获取当前链表所处的桶子，以便跳到下一个非空的桶子，那么就需要此函数再一次hash获取了，实现起来也非常简单。

template <class V, class K, class HF, class Ex, class Eq, class A>
    typename hashtable<V, K, HF, Ex, Eq, A>::reference 
    hashtable<V, K, HF, Ex, Eq, A>::find_or_insert(const value_type& obj)
    {
      resize(num_elements + 1);//是否需要扩容，提前准备
    
      size_type n = bkt_num(obj);//通过key hash 获取对应的篮子
      node* first = buckets[n];
    
      for (node* cur = first; cur; cur = cur->next)//发现则返回对应的Value（可能是一个pair）
        if (equals(get_key(cur->val), get_key(obj)))
          return cur->val;//返回pair，依据传进的Value_Type而定，很牛逼
    
      node* tmp = new_node(obj);//否则插入
      tmp->next = first;
      buckets[n] = tmp;
      ++num_elements;
      return tmp->val;//并返回Value_Type
    }

这个也是一个重要的方法，在`hash_map`里面有使用。

## hashtable的例子 ##

例子可以和上述描述一一对应起来

#include<string>
    #include<stdio.h>
    //#include<hash_set>
    #include<hashtable.h>
    using namespace std;
    using namespace __gnu_cxx;
    int main()
    {
    
        hashtable<int,
                  int,
                  __gnu_cxx::hash<int>,
                  _Identity<int>,
                  equal_to<int> >
                MyHashtable(50 , __gnu_cxx::hash<int>() , equal_to<int>() );
    //1、模板参数指定都是类。注意__gnu_cxx必须匹配，否则出现巨大问题。
    //2、对象构造函数初始化：通过类产生临时对象来初始化对象里面变量。
    //3、指定保留50个bucket(桶),并指定内存分配器，内存分配器通过Value类型确定，其实主要是分配HashNode。
    
        cout << MyHashtable.size() << endl;         //0
        cout << MyHashtable.bucket_count() << endl; //虽然初始化为50，但是会选取53这是STL提供的最小质数
        cout<<MyHashtable.max_bucket_count()<<endl; //桶子最大，也就是最后的质数4294967291
    
        MyHashtable.insert_unique(59);
        MyHashtable.insert_unique(63);
        MyHashtable.insert_unique(108);
        MyHashtable.insert_unique(2);
        MyHashtable.insert_unique(53);
        MyHashtable.insert_unique(55);
        cout << MyHashtable.size() << endl; //6,此即hashtable<T>::num_elements
    
        //声明一个hashtable迭代器
        hashtable<int,
                  int,
                  __gnu_cxx::hash<int>,
                  _Identity<int>,
                  equal_to<int> >::iterator
         ite = MyHashtable.begin();//返回指向哈希表中首节点的指针
    
        for(int i = 0 ; i < MyHashtable.size() ; i++ , ite++)
            cout<< *ite <<' ';    //输出：53 55 2 108 59 63 并没有顺序
        cout << endl;
    
        /*遍历所有buckets,如果其节点个数不为0，就打印节点个数，为0不打印*/
        for(int i = 0 ; i < MyHashtable.bucket_count() ; i++)
        {
            int n = MyHashtable.elems_in_bucket(i);
            if(n != 0)
                cout<<"bucket["<<i<<"] has " << n << " elems."<<endl;
        }
        /* 输出： bucket[0] has 1 elems. bucket[2] has 3 elems. bucket[6] has 1 elems. bucket[10] has 1 elems. */
    
        /*为了验证“bucket(list)”的容量就是buckets vector的大小(这是从 hashtable<T>::resize()得知的结果)，刻意将元素加到54个， 看看是否发生重建表*/
    
        for(int i = 0 ; i < 48 ; i++)//再次插入48个数
            MyHashtable.insert_equal(i);//允许重复key
    
        cout << MyHashtable.size() << endl;        //6+48 = 54
        cout << MyHashtable.bucket_count() << endl;//取了后面质数97确实扩容了(重建)
    
        for (int i = 0; i < MyHashtable.bucket_count();i++ )
        {
            int n = MyHashtable.elems_in_bucket(i);
            if(n!=0)
                cout << "bucket["<<i<<"] has " << n << " elems."<<endl;
        }
        /*打印的结果 bucket[2]到bucket[11]的节点个数为2 其余的bucket[0]~bucket[47]的节点个数为1 此外，bucket[53],[55],[59],[63]的节点个数均为1*/
    
        /*以迭代器变量hashtable,将所有节点打印出来*/
        ite = MyHashtable.begin();
        for(;ite != MyHashtable.end() ; ite++)
            cout << *ite <<' ';
        cout << endl;
    
        cout << *(MyHashtable.find(2) )<<endl;//2
        cout << MyHashtable.count(2) << endl;//2,遍历整个迭代器，找出key为2的元素
        return 0;
    
    }

![这里写图片描述][70 2]  
上述的运行之后的结果，由前面的分析，已经看很清楚了，使用起来简单粗暴。下面是对应的内存分配模型，也很简单。  
![这里写图片描述][70 3]  
![这里写图片描述][70 4]

[Link 1]: https://blog.csdn.net/u010710458/article/details/78492890#t7
[70]: /images/20220529/ff1605bd0a5f4cde818e4432f56ac737.png
[70 1]: /images/20220529/96abe1eaa57a4808adf703d51006d14b.png
[70 2]: /images/20220529/93b78a888bfa41588732e422702b6db0.png
[70 3]: /images/20220529/d9b6b55dee694106bcf38b7b13bf6eaa.png
[70 4]: /images/20220529/af340f488d2942d189e884f8fd0bc602.png