青岛企业网站建站模板,网页版微信二维码怎么生成,广告设计公司排行,wordpress 分类目录 插件哈希一、unordered系列关联式容器二、哈希原理2.1 哈希映射2.2 哈希冲突2.2.1 闭散列—开放地址法2.2.2 代码实现2.2.3 开散列—拉链法2.2.4 代码实现三、哈希封装unordered_map/unordered_set3.1 基本框架3.2 迭代器实现3.2.3 operator*和operator-和operator!3.2.4 opera…
哈希一、unordered系列关联式容器二、哈希原理2.1 哈希映射2.2 哈希冲突2.2.1 闭散列—开放地址法2.2.2 代码实现2.2.3 开散列—拉链法2.2.4 代码实现三、哈希封装unordered_map/unordered_set3.1 基本框架3.2 迭代器实现3.2.3 operator*和operator-和operator!3.2.4 operator与构造函数3.2.5 begin()和end()3.2.6 operator[]3.2.7 const迭代器问题四、哈希源码一、unordered系列关联式容器
map和set的底层是用红黑树实现的在最差的情况下也能在高度次查询到节点。但是当节点数量非常多的时候效率并不理想所以C11引入了unorderedmap与unorderedset能极快的查找到元素节点但是它们的底层不是用搜索树实现的所以不能保证有序。
二、哈希原理
2.1 哈希映射
红黑树我们需要进行比较查找才能找到对应节点。而进过哈希映射函数让key值跟存储位置建立映射关系那么在查找时通过该函数可以很快找到该元素。 像计数排序就可以看作一个简单的哈希映射叫做直接定址法但是得范围集中才行。 如果范围不集中就可以用除留余数法我们可以用元素的值去模上容器的大小。这样所有的元素就一定能存入表中。
2.2 哈希冲突
上面的除留余数法可能会导致两个元素要存储在同一个位置。我们把这种情况称为哈希冲突。而解决哈希冲突的方法有两种
2.2.1 闭散列—开放地址法
闭散列的大致方法就是当映射的地方已经有值了那么就按规律找其他位置。而查找空位的方法又分为线性探测和二次探测。
【线性探测】 插入 用除留余数法求出key值的关键码并将它放到对应的位置上。如果该位置已经存在数据被占用了那么继续寻找下一个位置也就是1的位置如果1的位置已经有数据那么继续1直到寻找到下一个空位置为止。
查找 查找就是取余后往后探索知道找到空位置就停止这里要注意如果删除了一个数据而要查找的元素在删除位置的后边就会在删除的地方停下来导致本来存在的元素查找不到。 解决这种情况的方式 可以再设置一种状态枚举将数组中每个数据的状态记录一下所以就有了存在空和删除这三种状态。删除的位置状态时删除查找的时候不会停下。 这里要注意有一种情况是整个闭散列全部都存在或者为删除状态边插入边删除不会扩容所以最多循环一圈。
负载因子 表中的有效数据个数/表的大小载荷因子不能超过1。为了减小冲突一般到0.7就会扩容。
字符串哈希 这里要注意如果key是字符串就不能使用除法取余所以我们需要一个仿函数把字符串转换成数字。
【二次探测】 我们知道线性探测如果发生了冲突并且冲突连在一起就会引起数据堆积导致搜索效率降低为了解决这种情况就有了二次探测。 二次探测的方法就是以i的2次方去进行探测如果要找的位置Idx被占下次找Idx 1^2如果再次被占则找Idx 2^2以此类推。
2.2.2 代码实现
// 状态
enum Sta
{EXIST,DELETE,EMPTY,
};// 数据类型
template class K, class V
struct HashData
{pairK, V _kv;Sta _state EMPTY;
};template class K
struct HashKey
{size_t operator()(const K key){return (size_t)key;}
};// 字符串哈希
template
struct HashKeystring
{size_t operator()(const string key){size_t ans 0;for (int i 0; i key.size(); i){ans * 131;ans i;}return ans;}
};// 哈希表结构
template class K, class V, class GetKey HashKeyK
class HashTable
{typedef HashDataK, V data;
public:HashTable(): _n(0){_tables.resize(7);}bool insert(const pairK, V kv){// 重复if (find(kv.first)) return false;// 负载因子size_t load _n * 10 / _tables.size();if (load 10){// 出作用域后销毁HashTableK, V newhash;newhash._tables.resize(2 * _tables.size());for (auto e : _tables){if (e._state EXIST){newhash.insert(e._kv);}}_tables.swap(newhash._tables);}GetKey Get;size_t hashI Get(kv.first) % _tables.size();while (_tables[hashI]._state EXIST){hashI;hashI % _tables.size();}_tables[hashI]._kv kv;_tables[hashI]._state EXIST;_n;return true;}data* find(const K key){GetKey Get;size_t hashI Get(key) % _tables.size();size_t startI hashI;// 最多循环一圈while (_tables[hashI]._state ! EMPTY){if (_tables[hashI]._state EXIST _tables[hashI]._kv.first key){return _tables[hashI];}hashI;hashI % _tables.size();if (hashI startI) break;}return nullptr;}bool erase(const K key){data* node find(key);if (node){node-_state DELETE;return true;}return false;}
private:vectordata _tables;size_t _n;// 有效数据个数
};2.2.3 开散列—拉链法
闭散列解决哈希冲突的办法就是抢占别人的位置而开散列不一样冲突的元素可以一起在同一个位置。 首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 【增容】 随着插入的数量增加可能导致一个桶的节点数目非常多为了应对这种情况在一定情况下需要增容。一般当负载因子为1的时候扩容。
2.2.4 代码实现
template class K, class V
struct HashNode
{HashNode(const pairK, V kv): _kv(kv), _next(nullptr){}pairK, V _kv;HashNodeK, V* _next;
};template class K, class V, class GetKey HashKeyK
class HashTable
{typedef HashNodeK, V Node;
public:HashTable(): _n(0){_tables.resize(10);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}bool insert(const pairK, V kv){// 重复if (find(kv.first))return false;// 负载因子为1扩容if (_tables.size() _n){vectorNode* newtable;newtable.resize(2 * _n);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t idx GetKey()(cur-_kv.first) % newtable.size();cur-_next newtable[idx];newtable[idx] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtable);}GetKey Get;size_t hashI GetKey()(kv.first) % _tables.size();Node* newnode new Node(kv);newnode-_next _tables[hashI];_tables[hashI] newnode;_n;return true;}Node* find(const K key){size_t idx GetKey()(key) % _tables.size();Node* cur _tables[idx];while (cur){if (cur-_kv.first key)return cur;elsecur cur-_next;}return nullptr;}bool erase(const K key){size_t idx GetKey()(key) % _tables.size();Node* cur _tables[idx];Node* pre nullptr;while (cur){if (cur-_kv.first key){if (pre nullptr){_tables[i] nullptr;}else{pre-_next cur-_next;}delete cur;--_n;return true;}else{pre cur;cur cur-_next;}}return false;}
private:vectorNode* _tables;size_t _n 0;
};三、哈希封装unordered_map/unordered_set
3.1 基本框架
这里的封装跟红黑树的类似我们需要改变一下节点的结构不管传入的是key还是pair都用模板参数T接收。
template class T
struct HashNode
{HashNode(const T data): _data(data), _next(nullptr){}T _data;HashNodeT* _next;
};根据前面红黑树的封装可以知道传入的时候第一个参数主要用来查找和删除第二个参数决定节点是什么类型。 代码如下
// unordered_Set.h
template class K, class Hash HashKeyK
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:
bool insert(const K key)
{return _ht.insert(key);
}
private:hashbucket::HashTableK, K, Hash, SetKeyOfT _ht;
};// unordered_Map.h
template class K, class V, class Hash HashKeyK
class unordered_map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:bool insert(const T data){return _ht.insert(data);}
private:hashbucket::HashTableK, pairK, V, Hash, MapKeyOfT _ht;
};3.2 迭代器实现
3.2.3 operator*和operator-和operator!
解引用operator*是将一个指针指向的内容取出来它返回的是哈希节点的数据。operator-是将指针指向内容的地址取出来也就是节点指向数据的地址。
T operator*()
{return _node-_data;
}T* operator-()
{return _node-_data;
}bool operator!(const self it) const
{return _node ! it._node;
}3.2.4 operator与构造函数
如果这个桶没有走完那么直接遍历当前迭代器指向节点的下一个节点。如果这个桶走完了要遍历下一个桶。但是既然要遍历那么一定需要_tables的大小而_tables又是一个私有成员随意我们可以用友元类来访问。
templateclass K, class T, class GetKey, class KeyOfT
friend struct HashIterator;// 迭代器需要访问私有而且我们还需要_tables所以在构造迭代器的时候要传进来个_tables的指针。
HashIterator(HT* ht, Node* node)// 传递指针: _node(node), _ht(ht)
{}operator代码如下
self operator()
{if (_node-_next){_node _node-_next;}else{// 找下一个桶KeyOfT kot;Hash hash;size_t idx hash(kot(_node-_data)) % _ht-_tables.size();idx;while (idx _ht-_tables.size()){if (_ht-_tables[idx] ! nullptr){_node _ht-_tables[idx];break;}else{idx;}}if (idx _ht-_tables.size()){_node nullptr;}}return *this;
}3.2.5 begin()和end()
begin就是找到_tables表的第一个不为空的桶的头节点如果找到了返回第一个位置的迭代器因为迭代器的构造需要节点指针和哈希表的指针那么哈希表的指针是什么呢哈希表的指针就是thisthis代表了整个哈希表的指针。将this指针传给迭代器的构造那么我们就能取到_table。 而end就是最后一个节点的下一个地址也就是nullptr。
template class K, class T, class GetKey, class KeyOfT
class HashTable
{typedef HashNodeT Node;templateclass K, class T, class GetKey, class KeyOfTfriend struct HashIterator;// 迭代器需要访问私有
public:typedef HashIteratorK, T, GetKey, KeyOfT iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(this, _tables[i]);}}return iterator(this, nullptr);}iterator end(){return iterator(this, nullptr);}
};3.2.6 operator[]
[]在前面的红黑树的封装也出现过operator[]只有map中有因为operator[]可以对插入的值进行增加查找。如果该值第一次出现那么operator[]充当的是插入如果该值第二次出现那么operator[]就充当的是修改。 既然是对是否成功插入做判断那么insert和find都要做出修改。
// unordered_Map.h
V operator[](const K key)
{pairiterator, bool ret _ht.insert(make_pair(key, V()));return ret.first-second;
}// HashTable.h
pairiterator, bool insert(const T data)
{// 重复iterator it find(KeyOfT()(data));if (it ! end()){return make_pair(it, false);}// 负载因子为1扩容if (_tables.size() _n){vectorNode* newtable;newtable.resize(2 * _n);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t idx GetKey()(KeyOfT()(data)) % newtable.size();cur-_next newtable[idx];newtable[idx] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtable);}size_t hashI GetKey()(KeyOfT()(data)) % _tables.size();Node* newnode new Node(data);newnode-_next _tables[hashI];_tables[hashI] newnode;_n;return make_pair(iterator(this, newnode), true);
}iterator find(const K key)
{size_t idx GetKey()(key) % _tables.size();Node* cur _tables[idx];while (cur){if (KeyOfT()(cur-_data) key)return iterator(this, cur);elsecur cur-_next;}return end();
}bool erase(const K key)
{size_t idx GetKey()(KeyOfT()(key)) % _tables.size();Node* cur _tables[idx];Node* pre nullptr;while (cur){if (cur-_data key){if (pre nullptr){_tables[idx] nullptr;}else{pre-_next cur-_next;}delete cur;--_n;return true;}else{pre cur;cur cur-_next;}}return false;
}3.2.7 const迭代器问题 在stl源码中可以看到并没有用以前的方法使用
typedef _list_iteratorT, T, T* iterator;
typedef _list_iteratorT, const T, const T* const_iterator;原因是如果使用const版本传递那么_tables使用[]返回的就是const。而用const迭代器去构造 HT* _ht; Node* _node;就会导致权限放大无法构造。但是如果改成 const HT* _ht; const Node* _node;又会导致[]不能修改的问题。 所以我们需要再写一个const版本迭代器
template class K, class T, class Hash, class KeyOfT
struct ConstHashIterator
{typedef HashNodeT Node;typedef ConstHashIteratorK, T, Hash, KeyOfT self;typedef HashTableK, T, Hash, KeyOfT HT;ConstHashIterator(const HT* ht, const Node* node)// 传递指针: _node(node), _ht(ht){}const T operator*() const{return _node-_data;}const T* operator-() const{return _node-_data;}bool operator!(const self it) const{return _node ! it._node;}self operator(){if (_node-_next){_node _node-_next;}else{// 找下一个桶KeyOfT kot;Hash hash;size_t idx hash(kot(_node-_data)) % _ht-_tables.size();idx;while (idx _ht-_tables.size()){if (_ht-_tables[idx] ! nullptr){_node _ht-_tables[idx];break;}else{idx;}}if (idx _ht-_tables.size()){_node nullptr;}}return *this;}const HT* _ht;const Node* _node;
};往HashTable写入友元类
template class K, class T, class Hash, class KeyOfT
friend struct ConstHashIterator;添加cbegin()与cend()。
// unordered_Set.h
typedef typename hashbucket::HashTableK, K, Hash, SetKeyOfT::const_iterator const_iterator;const_iterator cbegin()
{return _ht.cbegin();
}const_iterator cend()
{return _ht.cend();
}//unordered_Map.h
typedef typename hashbucket::HashTableK, pairK, V, Hash, MapKeyOfT::const_iterator const_iterator;const_iterator cbegin()
{return _ht.cbegin();
}const_iterator cend()
{return _ht.cend();
}四、哈希源码
unordered_set.h:
#pragma once
#include HashTable.hnamespace yyh
{template class K, class Hash HashKeyKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hashbucket::HashTableK, K, Hash, SetKeyOfT::iterator iterator;typedef typename hashbucket::HashTableK, K, Hash, SetKeyOfT::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator cbegin(){return _ht.cbegin();}const_iterator cend(){return _ht.cend();}pairiterator, bool insert(const K key){return _ht.insert(key);}bool find(const K key){return _ht.find(key);}bool erase(const K key){return _ht.erase(key);}private:hashbucket::HashTableK, K, Hash, SetKeyOfT _ht;};
}unordered_map.h:
#pragma once
#include HashTable.hnamespace yyh
{template class K, class V, class Hash HashKeyKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename hashbucket::HashTableK, pairK, V, Hash, MapKeyOfT::iterator iterator;typedef typename hashbucket::HashTableK, pairK, V, Hash, MapKeyOfT::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator cbegin(){return _ht.cbegin();}const_iterator cend(){return _ht.cend();}pairiterator, bool insert(const pairK, V kv){return _ht.insert(kv);}bool find(const K key){return _ht.find(key);}bool erase(const K key){return _ht.erase(key);}V operator[](const K key){pairiterator, bool ret _ht.insert(make_pair(key, V()));return ret.first-second;}private:hashbucket::HashTableK, pairK, V, Hash, MapKeyOfT _ht;};
}HashTable.h
#pragma once#include iostream
#include vector
#include string
using namespace std;template class K
struct HashKey
{size_t operator()(const K key){return (size_t)key;}
};// 字符串哈希
template
struct HashKeystring
{size_t operator()(const string key){size_t ans 0;for (size_t i 0; i key.size(); i){ans * 131;ans i;}return ans;}
};namespace hashbucket
{template class Tstruct HashNode{HashNode(const T data): _data(data), _next(nullptr){}T _data;HashNodeT* _next;};// 前置声明template class K, class T, class Hash, class KeyOfTclass HashTable;template class K, class T, class Hash, class KeyOfTstruct HashIterator{typedef HashNodeT Node;typedef HashIteratorK, T, Hash, KeyOfT self;typedef HashTableK, T, Hash, KeyOfT HT;HashIterator(HT* ht, Node* node)// 传递指针: _node(node), _ht(ht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const self it) const{return _node ! it._node;}self operator(){if (_node-_next){_node _node-_next;}else{// 找下一个桶KeyOfT kot;Hash hash;size_t idx hash(kot(_node-_data)) % _ht-_tables.size();idx;while (idx _ht-_tables.size()){if (_ht-_tables[idx] ! nullptr){_node _ht-_tables[idx];break;}else{idx;}}if (idx _ht-_tables.size()){_node nullptr;}}return *this;}HT* _ht;Node* _node;};template class K, class T, class Hash, class KeyOfTstruct ConstHashIterator{typedef HashNodeT Node;typedef ConstHashIteratorK, T, Hash, KeyOfT self;typedef HashTableK, T, Hash, KeyOfT HT;ConstHashIterator(const HT* ht, const Node* node)// 传递指针: _node(node), _ht(ht){}const T operator*() const{return _node-_data;}const T* operator-() const{return _node-_data;}bool operator!(const self it) const{return _node ! it._node;}self operator(){if (_node-_next){_node _node-_next;}else{// 找下一个桶KeyOfT kot;Hash hash;size_t idx hash(kot(_node-_data)) % _ht-_tables.size();idx;while (idx _ht-_tables.size()){if (_ht-_tables[idx] ! nullptr){_node _ht-_tables[idx];break;}else{idx;}}if (idx _ht-_tables.size()){_node nullptr;}}return *this;}const HT* _ht;const Node* _node;};template class K, class T, class GetKey, class KeyOfTclass HashTable{typedef HashNodeT Node;templateclass K, class T, class GetKey, class KeyOfTfriend struct HashIterator;// 迭代器需要访问私有template class K, class T, class Hash, class KeyOfTfriend struct ConstHashIterator;public:typedef HashIteratorK, T, GetKey, KeyOfT iterator;typedef ConstHashIteratorK, T, GetKey, KeyOfT const_iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(this, _tables[i]);}}return iterator(this, nullptr);}iterator end(){return iterator(this, nullptr);}const_iterator cbegin(){for (size_t i 0; i _tables.size(); i){if (_tables[i]){return const_iterator(this, _tables[i]);}}return const_iterator(this, nullptr);}const_iterator cend(){return const_iterator(this, nullptr);}HashTable(): _n(0){_tables.resize(10);}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}pairiterator, bool insert(const T data){// 重复iterator it find(KeyOfT()(data));if (it ! end()){return make_pair(it, false);}// 负载因子为1扩容if (_tables.size() _n){vectorNode* newtable;newtable.resize(2 * _n);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t idx GetKey()(KeyOfT()(data)) % newtable.size();cur-_next newtable[idx];newtable[idx] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtable);}size_t hashI GetKey()(KeyOfT()(data)) % _tables.size();Node* newnode new Node(data);newnode-_next _tables[hashI];_tables[hashI] newnode;_n;return make_pair(iterator(this, newnode), true);}iterator find(const K key){size_t idx GetKey()(key) % _tables.size();Node* cur _tables[idx];while (cur){if (KeyOfT()(cur-_data) key)return iterator(this, cur);elsecur cur-_next;}return end();}bool erase(const K key){size_t idx GetKey()(KeyOfT()(key)) % _tables.size();Node* cur _tables[idx];Node* pre nullptr;while (cur){if (cur-_data key){if (pre nullptr){_tables[idx] nullptr;}else{pre-_next cur-_next;}delete cur;--_n;return true;}else{pre cur;cur cur-_next;}}return false;}private:vectorNode* _tables;size_t _n 0;};
}
