STL之hash_set和hash_multiset、hash_map和hash_multimap详解

客官°小女子只卖身不卖艺 2022-05-29 13:28 265阅读 0赞

# hash\_set #

**1、介绍**  
虽然STL只规范复杂度和接口，并不规范实现方法，但STL set多半以RB-tree为底层机制。

SGI在标准之外提供了hash\_set，以hashtable作为底层机制。用set为的是能快速搜寻元素。这一点无论底层是RB-tree还是hashtable都能实现。但RB-tree有自动排序能力(二叉树特性)而hashtable（肯定没有啊）没有，其结果就是set元素会自动排序而hash\_set不会。hash\_set和set一样，只存在键值，没有像map一样存pair。

hashtable无法处理未定义类型元素（除非用户自定义hash函数），所以hash\_set也没法处理它们。  
hash\_set使用方法和set一样。`hashtable`可能需要自定义的有两种仿函数：其一就是hash函数，其二就是比较key的仿函数，很简单，我们只需要提供相应的仿函数即可。

**2、从简单的例子入手**

#include <hash_set>
    #include <iostream>
    #include <cstring>
    using namespace std;
    using namespace __gnu_cxx;
    struct eqstr//仿函数类，自己提供比较char *的方法，很简单，直接自定义即可。
    {
        bool operator()(const char* s1, const char* s2) const
        {
            return strcmp(s1, s1) == 0;
    
        }
    };
    void lookup(const hash_set< const char* , __gnu_cxx::hash<const char*> , eqstr>& Set, const char* word)
    {
        hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr>::const_iterator it = Set.find(word);
        cout << word << ": " << (it != Set.end() ? "Present" : "not Present") << endl;//没有返回0，就是尾部迭代器。一样的操作。
    
    }
    int main()
    {
    
        hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr> Set;//定义一个set，其实就是通过宏定义初始化内部的hashtable
        //hashNode里面存放的是一个char *而已。
        Set.insert("kiwi");
        Set.insert("plum");
        Set.insert("apple");
        Set.insert("mango");
        Set.insert("apricot");
        Set.insert("banana");
    
        lookup(Set, "mango");
        lookup(Set, "apple");
        lookup(Set, "durian");
    
        hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr>::const_iterator ite1 = Set.begin();
    
        for (; ite1 != Set.end() ; ++ite1)
        {
            cout << *ite1 << " " << endl;
        }
        cout << endl;
        return 0;
    }

上述重点在于给hashtable提供equel仿函数，因为在hashtable查找的时候，需要提供这个类型。上述实现也很简答，我们一会看看源代码。  
![这里写图片描述][70]

int main(void){
        hash_set<int> Myset;//int类型，STL提供了默认的hash ， 默认的比较函数
        Myset.insert(59);
        Myset.insert(63);
        Myset.insert(108);
        Myset.insert(2);
        Myset.insert(53);
        Myset.insert(55);
        for(hash_set<int>::const_iterator ite = Myset.begin() ; ite!= Myset.end() ; ite++)
            cout << *ite << endl;//2 53 55 59 63 108
        cout << endl;
        return 0;
    }

![这里写图片描述][70 1]  
这里并没有提供排序的功能，因为这里篮子个数是197，并且`int`类型，对应的hash值就是本身对篮子个数取模，所以上述看着类似有排列的功能。则们直接从内存模型上面分析，会和很简单的。

**3、源码分析**  
没什么好分析，就是包装了`hashtable`而已，将`hashtable`弄清楚了，那么就会很轻松轻松的。

template <class Value, class HashFcn = hash<Value>,
              class EqualKey = equal_to<Value>,
              class Alloc = alloc>
    class hash_set
    {
    private:
      typedef hashtable<Value, Value, HashFcn, identity<Value>, 
                        EqualKey, Alloc> ht;
      ht rep;//底层机制 hashtable
    
    public:
      typedef typename ht::key_type key_type;
      typedef typename ht::value_type value_type;
      typedef typename ht::hasher hasher;
      typedef typename ht::key_equal key_equal;
    
      typedef typename ht::size_type size_type;
      typedef typename ht::difference_type difference_type;
      typedef typename ht::const_pointer pointer;
      typedef typename ht::const_pointer const_pointer;
      typedef typename ht::const_reference reference;
      typedef typename ht::const_reference const_reference;
    
      typedef typename ht::const_iterator iterator;
      typedef typename ht::const_iterator const_iterator;
    
      hasher hash_funct() const { return rep.hash_funct(); }//返回仿函数对象
      key_equal key_eq() const { return rep.key_eq(); }//返回仿函数对象
    
    public:
      hash_set() : rep(100, hasher(), key_equal()) {}//缺省使用100个篮子，最后将被调整成对应的质数193
      explicit hash_set(size_type n) : rep(n, hasher(), key_equal()) {}//不允许默认转换类型
      hash_set(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}//构造函数
      hash_set(size_type n, const hasher& hf, const key_equal& eql)//构造函数
        : rep(n, hf, eql) {}
    
      template <class InputIterator>
      hash_set(InputIterator f, InputIterator l)
        : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
      template <class InputIterator>
      hash_set(InputIterator f, InputIterator l, size_type n)
        : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
      template <class InputIterator>
      hash_set(InputIterator f, InputIterator l, size_type n,
               const hasher& hf)
        : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
      template <class InputIterator>
      hash_set(InputIterator f, InputIterator l, size_type n,
               const hasher& hf, const key_equal& eql)
        : rep(n, hf, eql) { rep.insert_unique(f, l); }
    #else
    
      hash_set(const value_type* f, const value_type* l)
        : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
      hash_set(const value_type* f, const value_type* l, size_type n)
        : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
      hash_set(const value_type* f, const value_type* l, size_type n,
               const hasher& hf)
        : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
      hash_set(const value_type* f, const value_type* l, size_type n,
               const hasher& hf, const key_equal& eql)
        : rep(n, hf, eql) { rep.insert_unique(f, l); }
    
      hash_set(const_iterator f, const_iterator l)
        : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
      hash_set(const_iterator f, const_iterator l, size_type n)
        : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
      hash_set(const_iterator f, const_iterator l, size_type n,
               const hasher& hf)
        : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
      hash_set(const_iterator f, const_iterator l, size_type n,
               const hasher& hf, const key_equal& eql)
        : rep(n, hf, eql) { rep.insert_unique(f, l); }
    #endif /*__STL_MEMBER_TEMPLATES */
    
    public:
    //方法，通过hash table实现
      size_type size() const { return rep.size(); }
      size_type max_size() const { return rep.max_size(); }
      bool empty() const { return rep.empty(); }
      void swap(hash_set& hs) { rep.swap(hs.rep); }
      friend bool operator== __STL_NULL_TMPL_ARGS (const hash_set&,
                                                   const hash_set&);
    
      iterator begin() const { return rep.begin(); }
      iterator end() const { return rep.end(); }
    
    public:
      pair<iterator, bool> insert(const value_type& obj)
        {
          pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
          return pair<iterator, bool>(p.first, p.second);
        }
    #ifdef __STL_MEMBER_TEMPLATES
      template <class InputIterator>
      void insert(InputIterator f, InputIterator l) { rep.insert_unique(f,l); }
    #else
      void insert(const value_type* f, const value_type* l) {
        rep.insert_unique(f,l);
      }
      void insert(const_iterator f, const_iterator l) {rep.insert_unique(f, l); }
    #endif /*__STL_MEMBER_TEMPLATES */
      pair<iterator, bool> insert_noresize(const value_type& obj)
      {
        pair<typename ht::iterator, bool> p = rep.insert_unique_noresize(obj);
        return pair<iterator, bool>(p.first, p.second);
      }
    
      iterator find(const key_type& key) const { return rep.find(key); }
    
      size_type count(const key_type& key) const { return rep.count(key); }
    
      pair<iterator, iterator> equal_range(const key_type& key) const
        { return rep.equal_range(key); }
    
      size_type erase(const key_type& key) {
       return rep.erase(key); }
      void erase(iterator it) { rep.erase(it); }
      void erase(iterator f, iterator l) { rep.erase(f, l); }
      void clear() { rep.clear(); }
    
    public:
      void resize(size_type hint) { rep.resize(hint); }
      size_type bucket_count() const { return rep.bucket_count(); }
      size_type max_bucket_count() const { return rep.max_bucket_count(); }
      size_type elems_in_bucket(size_type n) const
        { return rep.elems_in_bucket(n); }
    };
    
    template <class Value, class HashFcn, class EqualKey, class Alloc>
    inline bool operator==(const hash_set<Value, HashFcn, EqualKey, Alloc>& hs1,
                           const hash_set<Value, HashFcn, EqualKey, Alloc>& hs2)
    {
      return hs1.rep == hs2.rep;
    }
    
    template <class Val, class HashFcn, class EqualKey, class Alloc>
    inline void swap(hash_set<Val, HashFcn, EqualKey, Alloc>& hs1,
                     hash_set<Val, HashFcn, EqualKey, Alloc>& hs2) {
      hs1.swap(hs2);
    }

# hash\_multiset #

hash\_multimap与multimap唯一的差别在于底层机制是hashtable，因此hash\_multimap元素不会被自动排序（迭代器遍历不会是排序的）。没啥好说的

# hash\_map #

SGI在STL标准外提供了hash\_map，以hashtable作为底层机制。运用map为的是能够根据键值快速搜索元素，这一点RB-tree或是hashtable都能够实现。但RB-tree有自动排序能力而hashtable没有，其结果就是set元素会自动排序而hash\_set不会。map和hash\_map一样，拥有键和值，它们的使用方法也一样。  
需要很简单：  
1、hash函数（库有则使用库，没有则自己提供仿函数）。  
2、key大小比较函数（库有，则使用库提供的模板实例化类，否则自己编写仿函数）  
3、没有了。使用很简单，插入的时候，注意`insert`和`[]`方法的不同。

int main(void){
        hash_map<const char * , int , __gnu_cxx::hash<const char*> , eqstr> Mymap;
        Mymap["January"] = 31;//设置map特有的操作符重载，下面重点讲解，将hashmap键和值可以用来计算键的次数
        Mymap["February"] = 28;
        Mymap["March"] = 31;
        Mymap["April"] = 30;
        Mymap["May"] = 31;
        Mymap["June"] = 30;
        Mymap["July"] = 31;
        Mymap["August"] = 31;
        Mymap["September"] = 30;
        Mymap["October"] = 31;
        Mymap["November"] = 30;
        Mymap.insert( pair<const char * , int>("December" , 31) );//产生临时对象，并pair起来
    
        //测试输出对应的键和值
        cout << "December " << Mymap["December"] << endl;
        cout << "June " << Mymap["June"] << endl;
        cout << "April " << Mymap["April"] << endl;
        cout << "March " << Mymap["March"] << endl;
    
        cout << endl << "测试遍历操作" << endl;
        for(hash_map<const char * , int , __gnu_cxx::hash<const char*> , eqstr>::const_iterator ite = Mymap.begin() ; ite!= Mymap.end() ; ite++)
            cout << (*ite).first << " " << ite->second << endl;//记住这两种操作符重载类型
        cout << endl;
    }

源代码：讲解一个地方

template <class Key, class T, class HashFcn = hash<Key>,
     class EqualKey = equal_to<Key>, class Alloc = alloc> class hash_map { private: typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T> >, EqualKey, Alloc> ht; ht rep; public: typedef typename ht::key_type key_type; typedef T data_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::size_type size_type; typedef typename ht::difference_type difference_type; typedef typename ht::pointer pointer; typedef typename ht::const_pointer const_pointer; typedef typename ht::reference reference; typedef typename ht::const_reference const_reference; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; hasher hash_funct() const { return rep.hash_funct(); } key_equal key_eq() const { return rep.key_eq(); } public: hash_map() : rep(100, hasher(), key_equal()) {} explicit hash_map(size_type n) : rep(n, hasher(), key_equal()) {} hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {} hash_map(size_type n, const hasher& hf, const key_equal& eql) : rep(n, hf, eql) {} template <class InputIterator> hash_map(InputIterator f, InputIterator l) : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); } template <class InputIterator> hash_map(InputIterator f, InputIterator l, size_type n) : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); } template <class InputIterator> hash_map(InputIterator f, InputIterator l, size_type n, const hasher& hf) : rep(n, hf, key_equal()) { rep.insert_unique(f, l); } template <class InputIterator> hash_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, const key_equal& eql) : rep(n, hf, eql) { rep.insert_unique(f, l); } #else hash_map(const value_type* f, const value_type* l) : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); } hash_map(const value_type* f, const value_type* l, size_type n) : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); } hash_map(const value_type* f, const value_type* l, size_type n, const hasher& hf) : rep(n, hf, key_equal()) { rep.insert_unique(f, l); } hash_map(const value_type* f, const value_type* l, size_type n, const hasher& hf, const key_equal& eql) : rep(n, hf, eql) { rep.insert_unique(f, l); } hash_map(const_iterator f, const_iterator l) : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); } hash_map(const_iterator f, const_iterator l, size_type n) : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); } hash_map(const_iterator f, const_iterator l, size_type n, const hasher& hf) : rep(n, hf, key_equal()) { rep.insert_unique(f, l); } hash_map(const_iterator f, const_iterator l, size_type n, const hasher& hf, const key_equal& eql) : rep(n, hf, eql) { rep.insert_unique(f, l); } #endif /*__STL_MEMBER_TEMPLATES */ public: size_type size() const { return rep.size(); } size_type max_size() const { return rep.max_size(); } bool empty() const { return rep.empty(); } void swap(hash_map& hs) { rep.swap(hs.rep); } friend bool operator== __STL_NULL_TMPL_ARGS (const hash_map&, const hash_map&); iterator begin() { return rep.begin(); } iterator end() { return rep.end(); } const_iterator begin() const { return rep.begin(); } const_iterator end() const { return rep.end(); } public: pair<iterator, bool> insert(const value_type& obj) { return rep.insert_unique(obj); } #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> void insert(InputIterator f, InputIterator l) { rep.insert_unique(f,l); } #else void insert(const value_type* f, const value_type* l) { rep.insert_unique(f,l); } void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); } #endif /*__STL_MEMBER_TEMPLATES */ pair<iterator, bool> insert_noresize(const value_type& obj) { return rep.insert_unique_noresize(obj); } iterator find(const key_type& key) { return rep.find(key); } const_iterator find(const key_type& key) const { return rep.find(key); } T& operator[](const key_type& key) { return rep.find_or_insert(value_type(key, T())).second; }//这个是最重要的方法，区别与set的，很重要 size_type count(const key_type& key) const { return rep.count(key); } pair<iterator, iterator> equal_range(const key_type& key) { return rep.equal_range(key); } pair<const_iterator, const_iterator> equal_range(const key_type& key) const { return rep.equal_range(key); } size_type erase(const key_type& key) {return rep.erase(key); } void erase(iterator it) { rep.erase(it); } void erase(iterator f, iterator l) { rep.erase(f, l); } void clear() { rep.clear(); } public: void resize(size_type hint) { rep.resize(hint); } size_type bucket_count() const { return rep.bucket_count(); } size_type max_bucket_count() const { return rep.max_bucket_count(); } size_type elems_in_bucket(size_type n) const { return rep.elems_in_bucket(n); } }; template <class Key, class T, class HashFcn, class EqualKey, class Alloc> inline bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1, const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2) { return hm1.rep == hm2.rep; } template <class Key, class T, class HashFcn, class EqualKey, class Alloc> inline void swap(hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1, hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2) { hm1.swap(hm2); }

这是最重要的地方，通过key获取对应的value。如果key存在，则返回value的引用，如果key不存在，则插入并且将value初始化为默认值并返回其引用，对应`int`，就相当于`int()`那么就是0。

T& operator[](const key_type& key) {
        return rep.find_or_insert(value_type(key, T())).second;
      }//这个是最重要的方法，区别与set的，很重要，直接调用了find_or_insert

`find_or_insert`的功能在前一讲`hashtable`已经详细说明，反正返回的是`hashtable`第一个模板参数类型。若`key`存在则返回存在的，否则插入`hashtable`并返回对应的引用。  
所以这里可以将IP地址作为key，IP出现的频率作为value，用来统计每个IP出现的频率，在大数据的时候特别有用，所以这个就是`map`牛逼的地方，存储和查找都非常块。

# hash\_multimap #

没啥可以讲解的，和multimap完全一样，只是底层通过hashtable存储对应的数据结构。这里存储的大多数是指针，存储对应对应的操作即可，总之这些关键都是在于如何管理一块内存，如何实现内存的高效存储。

[70]: /images/20220529/cea64f6a660f40fcbf5018dc3ed74746.png
[70 1]: /images/20220529/b77c650aca19492e8038a1ba9a578a2d.png