C++ 进阶之哈希（unordered_map/set 的使用及其模拟）

作者：雪芙花

2022-10-22
湖南
本文字数：5263 字
阅读完需：约 17 分钟

一：unordered_map/set 的使用

unordered_map 是存储<key, value>键值对的关联式容器，其允许通过 keys 快速的索引到与其对应的 value。
在 unordered_map 中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map 没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 value，unordered_map 将相同哈希值的键值对放在相同的桶中。
unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps 实现了直接访问操作符(operator[])，它允许使用 key 作为参数直接访问 value。
它的迭代器是单向迭代器。

特殊接口的说明：

unordered_map 的查询

注意：unordered_map 中 key 是不能重复的，因此 count 函数的返回值最大为 1

unordered_map 的修改操作

unordered_map 的桶操作

unordered_set 类似

二：哈希概念的介绍

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为 O(N)，平衡树中为树的高度，即 O(N)，搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法是可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素，则复杂度为 O(1)非常的高效，而计数排序用的即是这种思想

哈希的思想就是信息压缩的思想，可以将一些信息量庞大的数据通过特殊的哈希函数压缩成信息量比较小的数据，再通过哈希桶，位图等容器存储起来。

当向该结构中：插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

1.哈希冲突

对于两个数据元素的关键字和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？

2. 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数：

直接定制法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀缺点：需要事先

知道关键字的分布情况使用场景：适合查找比较小且连续的情况 2. 除留余数法--(常用)

设散列表中允许的地址数为 m，取一个不大于 m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key%p(p<=m),将关键码转换成哈希地址

3. 闭散列

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的“下一个” 空位置中去

线性探测：

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，即 newindexi=（index+i)%capacity 线性探测实现非常简单，但是一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低

二次探测：

从发生的冲突的位置开始，不逐个往后找，而是以平方个位置找，即计算位置为 newindexi=（index+i^2)%capacity 二次探测可以较为有效的方式减小哈希冲突的概率

闭散列扩容

使用除留余数定制法时，对于扩容后的哈希表对应的哈希函数的除数的值会发生相应的改变，导致下一次查找定制的位置可能不同，所以需要对原来的数据进行再次映射到新的位置上

4 .开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

实现步骤：

插入

通过哈希函数找到对应的映射位置，然后头插，但是在插入之前需要进行遍历桶节点查看是否存在与插入的值相同的节点，没有才进行头插。

删除/查找

通过哈希函数映射到对应的位置，进行对该位置通的遍历再进行删除或查找

开散列增容桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容。开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容

除留余数法，最好模一个素数

代码实现：

//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式size_t GetNextPrime(size_t prime){  const int PRIMECOUNT = 28;  static const size_t primeList[PRIMECOUNT] =  {    53ul, 97ul, 193ul, 389ul, 769ul,    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,    1610612741ul, 3221225473ul, 4294967291ul  };
  size_t i = 0;  for (; i < PRIMECOUNT; ++i)  {    if (primeList[i] > prime)      return primeList[i];  }
  return primeList[i];}

复制代码

开散列代码实现：

//哈希储存的数据类型template<class K,class V>struct HashNode{  pair<K,V> _kv;  HashNode* _next;
  HashNode(const pair<K,V>& kv)    :_kv(kv)    , _next(nullptr)  {}};//取值比较仿函数及其特化template<class K>struct HashFunc{  size_t operator()(const K& key)  {    return key;  }};template<>struct HashFunc<string>{  size_t operator()(const string& str)  {    size_t hash = 0;    for (int i = 0; i < str.size(); i++)    {      hash = hash * 131 + str[i];    }    return hash;  }};//获取下一个质数（接近二倍开辟）,比较科学减少冲突的取扩容大小的方式size_t GetNextPrime(size_t prime){  const int PRIMECOUNT = 28;  static const size_t primeList[PRIMECOUNT] =  {    53ul, 97ul, 193ul, 389ul, 769ul,    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,    1610612741ul, 3221225473ul, 4294967291ul  };
  size_t i = 0;  for (; i < PRIMECOUNT; ++i)  {    if (primeList[i] > prime)      return primeList[i];  }
  return primeList[i];}template<class K, class V, class Hash=HashFunc<K>>class HashTable{  typedef HashNode<K,V> Node;public:  typedef HashTable<K, V, Hash> HT;  HashTable()    :_n(0)  {}  HashTable(const HT& ht)//拷贝构造    :_n(ht._n)  {    if (ht._table.size() == 0)//空栈      return;
    _table.resize(ht._table.size(), nullptr);//开辟空间并初始化    for (int i = 0; i < ht._table.size(); i++)//遍历深拷贝    {      Node* cur = ht._table[i];      while (cur)//遍历桶      {        Node* newnode = new Node(cur->_kv);        newnode->_next = _table[i];//头插        _table[i] = newnode;
        cur = cur->_next;      }    }  }  HT& operator=(const HT& ht)//赋值重载（现代式）  {    if (&ht != this)    {      HT temp(ht);//拷贝构造      _table.swap(temp._table);      _n = ht._n;    }    return *this;  }  ~HashTable()//析构-释放资源  {    for (int i = 0; i < _table.size(); i++)    {      Node* cur = _table[i];      while (cur)      {        Node* next = cur->_next;        delete cur;        cur = next;      }      _table[i] = nullptr;//置空    }    _n = 0;  }  bool Insert(const pair<K,V>& kv)  {    Hash hf;    //空哈希或者负载因子达到1时进行扩容    if (_table.size() == _n)    {      //size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;      size_t newsize = GetNextPrime(_table.size());//获取新的扩容大小      vector<Node*> newdata;      newdata.resize(newsize, nullptr);//开新的数组并扩容      //将原数组中的节点重新映射插入到新数组      for (size_t i = 0; i < _table.size(); ++i)      {        Node* cur = _table[i];        while (cur)//挂有节点        {          Node* next = cur->_next;//记录下一个节点          size_t index = hf(cur->_kv.first) % newsize;//重新计算下标                    cur->_next = newdata[index];//头插          newdata[index] = cur;
          cur = next;//移动        }        _table[i] = nullptr;//原数组置空      }      _table.swap(newdata);    }
    size_t index = hf(kv.first) % _table.size();    Node* cur = _table[index];//遍历查看桶数据知否相等    while (cur)    {      if (cur->_kv.first == kv.first)//相等        return false;      else        cur = cur->_next;    }    //头插    Node* newnode = new Node(kv);    newnode->_next = _table[index];    _table[index] = newnode;    ++_n;    return true;  }  Node* Find(const K& key)  {    //空哈希    if (_table.size() == 0)      return nullptr;    Hash hf;    size_t index = hf(key) % _table.size();    Node* cur = _table[index];    while (cur)    {      if (cur->_kv.first == key)        return cur;      else        cur = cur->_next;    }    return nullptr;  }  bool Erase(const K& key)  {    //空哈希    if (_table.size() == 0)      return false;    Hash hf;    size_t index = hf(key) % _table.size();    Node* cur = _table[index];    Node* parent = nullptr;    while (cur)    {      if (cur->_kv.first == key)      {        if (parent == nullptr)//头结点进行头删          _table[index] = cur->_next;        else          parent->_next = cur->_next;        delete cur;        --_n;        return true;      }      else      {        parent = cur;        cur = cur->_next;      }    }    return false;  }private:  vector<Node*> _table;  size_t _n;};

复制代码

三：模拟实现

namespace ymh{  template<class K , class Hash = HashFunc<K>>  class unordered_set  {    struct SetOfKey    {      const K& operator()(const K& key)const      {        return key;      }    };    typedef HashNode<K> Node;  public:    typedef HashTable<K, K, Hash, SetOfKey> HT;    typedef typename HT::Iterator iterator;    iterator begin()    {      return _ht.begin();    }    iterator end()    {      return _ht.end();    }    pair<iterator, bool> insert(const K& key)    {      return _ht.Insert(key);    }    /*V& operator[](const K& key)    {      auto ret = insert(make_pair(key, V()));      return ret.first->second;    }*/    Node* find(const K& key)    {      return _ht.Find(key);    }    bool erase(const K& key)    {      return _ht.Erase(key);    }  private:    HT _ht;  };  void test_unordered_set()  {    unordered_set<int> set;    int arr[] = { 1,2,22,34,3,4,54,4,2,6,18,48,56,16,45,16,23,156,49,153,45,81,6,6,16,16,151,84894,11,6 };    for (auto e : arr)    {      set.insert(e);    }    for (auto& e : set)    {      cout << e << endl;    }    auto ret = set.find(4);    cout << ret << endl;    set.erase(4);    for (auto& e : set)    {      cout << e << endl;    }    for (auto e : arr)    {      set.erase(e);    }    for (auto& e : set)    {      cout << e<< endl;    }  }}

复制代码

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/3a092b73b55aed55fd161f949】。未经作者许可，禁止转载。

雪芙花

关注

还未添加个人签名 2022-04-28 加入

还未添加个人简介

发布

暂无评论

创作场景

C++ 进阶之哈希（unordered_map/set 的使用及其模拟）

一：unordered_map/set 的使用

二：哈希概念的介绍

1.哈希冲突

2. 哈希函数

3. 闭散列

4 .开散列

三：模拟实现

雪芙花

评论