【C++】哈希表_c++哈希表

目录

一、概念

二、底层结构

（一）哈希结构

（二）哈希函数

（1）直接定址法

（2）除留余数法

（3）平方取中法

（4）随机数法

（5）数学分析法

（三）无法直接使用哈希函数直接转换

三、冲突策略

（一）闭散列

（二）开散列

五、封装哈希表

（一）HashTable.hpp

（二）unordered_set.hpp

（三）unordered_map.hpp

六、哈希的应用

（一）位图

（二）布隆过滤器

一、概念

        在C++98中，STL提供了 set 和 map 两种序列式容器，该容器底层由红黑树实现，其查找效率比较优秀为 log(n) ，但是在插入节点时会导致频率旋转而消耗性能。

        因此在C++11中，STL新引入了两种序列式容器 unordered_set 与 unordered_map，其底层为哈西表，其插入和查找元素最好的情况时间复杂度为 O(1)，即使在极端场景下时间复杂度最坏为 O(n)。

        unordered_set 与 unordered_map 上层封装的接口其实与 set 与 map 基本一致，二类主要区别在于底层的实现方式不同。

        unordered_set并不像set那样支持反向迭代器，它的迭代器底层是一个单向迭代器。unordered_set的插入是无序的，不一定按照插入的顺序进行打印。自带去重功能。而对于unordered_map 而言，也是单向迭代器并且无序，其他功能与 map 相似。

        除此之外，set 和 map 底层是在红黑树中通过关键字的比较从而找到节点插入的位置，而 unordered_set 与 unordered_map 底层的哈希表则是通过关键字的值直接映射至插入位置。

二、底层结构

（一）哈希结构

       在顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

        而在哈希存储结构中，通过一个特定的哈希函数（hashFunc），元素的存储位置与其关键字之间可以建立唯一对应关系。因此，查找时可以通过该函数迅速定位到目标元素。在哈希表中，插入或查找元素的过程都是通过哈希函数来完成的。

（二）哈希函数

（1）直接定址法

        取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B，将计算结果直接作为哈希地址存储。

（2）除留余数法

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

（3）平方取中法

        将关键字平方后的结果每次固定取出其中几位作为哈希地址存储。如假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址。

（4）随机数法

        选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。

（5）数学分析法

        设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

（三）无法直接使用哈希函数直接转换

        在某些情况下，无法直接使用哈希函数对关键字进行映射，例如当关键字为字符串时是无法直接将字符串使用哈希函数转换为哈希地址的。

        当然STL库中已经为我们提供了关键字为字符串时的处理方法，在创建哈希表时无需传入对字符串的处理。如果我们需要对自定义类型建立哈希表，则需要传入对自定义类型的处理函数。本文为方便探讨仍拿字符串类型举例。

        针对于这类情况，我们只需要将字符串转换为整型数字即可，例如简单地将字符串中的各个字符转换为数字后相加，将该结果再通过哈希函数转换为哈希地址即可。这样就达到了将字符串作为关键字建立哈希表。

        网上有关这方面算法的探讨，这里不进行赘述了：字符串转整型相关算法

三、冲突策略

        除了哈希函数以外，哈希冲突的解决也十分重要。例如使用除留余数法，若表长为10，那么关键字1和关键字11都会被映射至同一个位置，从而产生冲突。闭散列和开散列都是哈希表处理冲突的策略。

（一）闭散列

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

        例如我们已有一个使用除留余数法的哈希表，当我们插入关键字44时，关键字经过哈希函数后的哈希地址为 4 ，但位置 4 已经存储了元素 14，所以便使用线性探测向后寻找插入位置。

       由上图我们可知，当我们插入十个元素后哈希表将满，无法再继续插入元素。此时我们需要引入一个新概念：

        负载因子=表中有效数据的个数/表的大小。负载因子越大，虽然空间利用率越高，但下一次插入时发生哈希冲突的概率越高！

        因此我们不一定得等到表满后再进行扩容，可以将负载因子达到某一状态时（例如当负载因子大于0.7）便进行扩容。

        发生扩容时我们新建一个哈希表，再将表内已有元素重新经过哈希函数（可能需要修改）重新映射进新的哈希表即可。

        查找元素与插入元素方法类似，将目标关键字经过哈希函数进行映射，得到哈希地址后按该地址进行查询，若该地址存储的元素与目标元素相同返回查找结果即可，若不相同则向后依次查找即可，直至查找至空即查找失败。

        当我们使用闭散列处理哈希函数时，不能随便删去哈希表中已有的元素，可能会影响其他元素的搜索。比如我们删除元素 14，如果真的删除了元素 14， 先不谈在数组中如何删去一个已有元素，删除后用什么值替代呢？再者如果删除了元素 14，那么就元素 44 就相当于丢失，无法再搜索到。因此线性探测采用标记的伪删除法来删除一个元素。

        整体代码：

//节点状态enum status{EMPTY,DELETE,EXIST,};//节点定义templatestruct HashNode {pair _data;status _status;HashNode(const pair data = pair()):_data(data), _status(EMPTY){}};//哈希表定义templateclass hashTable{public:typedef HashNode Data;hashTable():_n(0){_table.resize(10);}//插入元素bool insert(const pair& kv){if (_n * 10 / _table.size() >= 7){hashTable ht;ht._table.resize(2 * _table.size());for (auto& e : _table){if(e._status == EXIST)ht.insert(e._data);}_table.swap(ht._table);}size_t hashi = kv.first % _table.size();while (_table[hashi]._status == EXIST){hashi = (hashi + 1) % _table.size();}_table[hashi]._data = kv;_table[hashi]._status = EXIST;++_n;return true;}//删除元素void erase(const K& key){Data* pData = find(key);if (pData == nullptr)return;pData->_status = DELETE;--_n;}//查找元素Data* find(const K& key){size_t hashi = key % _table.size();size_t start = hashi;while (_table[hashi]._status != EMPTY){if (_table[hashi]._status == EXIST && _table[hashi]._data.first == key)return &_table[hashi];hashi = (hashi + 1) % _table.size();if (start == hashi)return nullptr;}return nullptr;}private:vector _table;size_t _n;};

（二）开散列

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

        相较于闭散列，开散列不会因为扩容消耗性能，链接结构不一定非得是单链表，在某些语言的哈希表中可以使用红黑树进行链接，而本文使用单链表作为链接结构。

        当我们插入关键字44时，关键字经过哈希函数后的哈希地址为 4 ，之后将新增节点进行头插即可。

        当我们查找元素时，关键字经过哈希函数后的哈希地址，按该地址进行链接顺序查找，如果找到元素返回即可，直到查找到空即查找失败。

        当我们删除元素时，查找到该元素的位置，需要注意的是在查找过程中需要记录前驱节点，找到节点后进行删除即可，若找不到目标元素则不进行任何操作。

五、封装哈希表

（一）HashTable.hpp

#pragma once#include #include //提前声明方便迭代使用templateclass HashTable;//节点定义templatestruct HashNode{V _data;HashNode* _next;HashNode(const V data = V()):_data(data), _next(nullptr){}};//迭代器定义templateclass HTIterator{public:typedef HTIterator Self;typedef HashTable HT;typedef HashNode Node;//构造函数HTIterator(Node* node, HT* ht):_node(node),_ht(ht){}//运算符重载V& operator*(){return _node->_data;}V* operator->(){return &_node->_data;}Self& operator++(){if (_node->_next){_node = _node->_next;}else{size_t hashi = Hash()(KeyOfVal()(_node->_data)) % _ht->_table.size() + 1;while (hashi != _ht->_table.size()){if (_ht->_table[hashi]){_node = _ht->_table[hashi];break;}++hashi;}if (hashi == _ht->_table.size())_node = nullptr;}return *this;}Self operator++(int){Self it = *this;operator++();return it;}bool operator==(const Self& it) const{return _node == it._node;}bool operator!=(const Self& it) const{return _node != it._node;}private://当前节点Node* _node;//指向哈希表HT* _ht;};//哈希表定义templateclass HashTable{typedef HashNode Node;templatefriend class HTIterator;public:typedef HTIterator iterator;typedef HTIterator const_iterator;//构造函数HashTable():_n(0){_table.resize(10);}//析构函数~HashTable(){for (auto& p : _table){Node* cur = p;while (cur){Node* next = cur->_next;delete cur;cur = next;}}_n = 0;}iterator begin(){for (auto& e : _table){if (e)return iterator(e, this);}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}//插入元素pair insert(const V& kv){iterator it = find(kv);if (it != end())return make_pair(it, false);if (_n == _table.size()){vector newTable;newTable.resize(_table.size() * 2);for (auto& p : _table){Node* cur = p;while (cur){Node* next = cur->_next;size_t hashidx = Hash()(KeyOfVal()(cur->_data)) % _table.size();cur->_next = newTable[hashidx];newTable[hashidx] = cur;cur = next;}p = nullptr;}_table.swap(newTable);}size_t hashi = Hash()(KeyOfVal()(kv)) % _table.size();Node* node = new Node(kv);node->_next = _table[hashi];_table[hashi] = node;++_n;return make_pair(iterator(node, this), true);}//删除元素bool erase(const K& key){size_t hashi = Hash()(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (KeyOfVal()(cur->_data) == key){if (prev) {prev->_next = cur->_next;}else{Node* next = cur->_next;_table[hashi] = next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}//查找元素iterator find(const K& key){size_t hashi = Hash()(key) % _table.size();Node* cur = _table[hashi];while (cur){if (KeyOfVal()(cur->_data) == key)return iterator(cur, this);cur = cur->_next;}return iterator(nullptr, this);}private:vector _table;//有效数据个数size_t _n;};

（二）unordered_set.hpp

#pragma once#include \"HashTable.hpp\"namespace mh{//哈希函数templatestruct HashFunc{size_t operator()(const K& data){return data;}};templatestruct HashFunc{size_t operator()(const string& data){size_t ret = 0;for (auto& e : data){ret += ret * 131 + e;}return ret;}};//unordered_set封装template<class K, class Hash = HashFunc>class unordered_set {templatestruct KeyOfVal{K operator()(const K& key){return key;}};public:typedef HashTable<K, const K, KeyOfVal, Hash> HT;typedef typename HashTable<K, const K, KeyOfVal, Hash>::iterator iterator;iterator begin(){return _tb.begin();}iterator end()const{return _tb.end();}pair insert(const K& key){return _tb.insert(key);}bool erase(const K& key){return _tb.erase(key);}iterator find(const K& key){return _tb.find(key);}private:HT _tb;};}

（三）unordered_map.hpp

#pragma once#include \"HashTable.hpp\"namespace mh{ //哈希函数templatestruct HashFunc{size_t operator()(const K& data){return data;}};templatestruct HashFunc{size_t operator()(const string& data){size_t ret = 0;for (auto& e : data){ret += ret * 131 + e;}return ret;}};//unordered_map封装template<class K, class V, class Hash = HashFunc>class unordered_map{templatestruct KeyOfVal{K operator()(const pair& kv){return kv.first;}};public:typedef HashTable<K, pair, KeyOfVal, Hash> HT;typedef typename HashTable<K, pair, KeyOfVal, Hash>::iterator iterator;iterator begin(){return _tb.begin();}iterator end(){return _tb.end();}V& operator[](const K& key){pair ret = insert(make_pair(key, V()));return ret.first->second;}pair insert(const pair& kv){return _tb.insert(kv);}bool erase(const K& key){return _tb.erase(key);}iterator find(const K& key){return _tb.find(key);}private:HT _tb;};}

六、哈希的应用

        哈希的思想并不是仅仅只能应用于哈希表，这种思想也有很多可以变迁的地方。

（一）位图

        位图就是拿一个比特位来表示数据的存放状态，它适用于处理海量的数据。例如如下情况：

        给40亿个不重复无序的无符号整数，如何快速判断一个目标数是否在这40亿个数中？

        40亿个整数，假如一个整数4个字节，那么40亿个整数160亿个字节，也就是相当于接近16GB，无论是用红黑树还是哈希表都会使用到大量存储空间，这显然是难以实现的。这时候就要采用位图的思想。

        如果我们拿一个比特位来表示一个整数的存储状态，那么总共则需要40亿个比特位，也就是5亿个字节即接近500MB，这是可以达到的。这就是位图的思想。

        在具体实现方面我们可以使用 char 或者 int 类型进行空间开辟。

        STL库中也为我们提供了位图：biteset，下面是模式实现：

#pragma once#include #include template class bitset{ public: bitset(){_bits.resize(N / 8 + 1, 0);}public:void set(size_t x)//将某个比特位标记为1{size_t i = x / 8;size_t j = x % 8;_bits[i] |= (1 << j);}void reset(size_t x)//将某个比特位标记为0{size_t i = x / 8;size_t j = x % 8;_bits[i] &= (~(1 << j));}bool test(size_t x)//测试这个值在不在位图中{size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);}private:std::vector _bits;};

（二）布隆过滤器

        由上图我们了解位图的思想，但有时候关键字不一定为整数，也有可能是字符串，虽然我们提供了将字符串转成整数的策略，但是在数据量非常大的时候很有可能两个不同的字符串会转换为通过一个整数进而产生误判（即数据并不在位图中，但转换后进行映射的地址状态为却为1）。

        上述情况位图并不能满足要求了，因此引入了布隆过滤器的概念。

        布隆过滤器实际上是一种基于位图和多个哈希函数的数据结构，其采用多个哈希函数进行地址映射，也就是说一个如果要插入一个关键字，会将该关键字分别进行不同的哈希函数进行映射，再将多个位置修改为1。当我们需要查询某个关键字是否存在于位图中时候，只需将该关键字进行不同哈希函数进行映射，检查各个位置的状态位是否为1，只有都为1才表明该数据存在于位图中。

        当然，增加了多个哈希函数会需要更多存储大小的要求，除此之外，布隆过滤器只是降低了误判的概率，并不能完全杜绝误判的情况，在一些极端场景下仍然会产生误判的情况。

        需要注意的是，布隆过滤器不支持删除元素，因为位图上的一个状态位，很有可能是多个关键字经过映射后的结果，因此不能将状态位由1置0。同时，布隆过滤器也不支持统计数据的个数，其只能统计目标数据是否存在。如果要实现统计次数的功能，就必须给每个位置添加一个变量用于存储数据的个数，也就是该位置被映射的次数。