wordpress feedsky,东营网站seo顾问,深圳产品网站建设,推荐个做淘宝主图视频的网站#x1f44d;作者主页#xff1a;进击的1 #x1f929; 专栏链接#xff1a;【1的数据结构】 文章目录 一#xff0c;什么是哈希#xff1f;二#xff0c;哈希冲突哈希函数哈希冲突解决 unordered_map与unordered_set 一#xff0c;什么是哈希#xff1f;
首先我们要… 作者主页进击的1 专栏链接【1的数据结构】 文章目录 一什么是哈希二哈希冲突哈希函数哈希冲突解决 unordered_map与unordered_set 一什么是哈希
首先我们要知道的是哈希是一种思想----一 一映射。在以前我们讲过的容器中查找效率最高的就是二叉平衡搜索树由于其关键码与存储位置之间没有对应的关系而是通过多次比较关键码的大小来查找查找的效率取决于比较次数查找的时间复杂度可以达到O(logN) 。最理想的查找便是不经过任何的比较直接能够锁定查找值的位置因此如果能够构建一种结构通过某种函数能够使得关键码与存储位置之间一一映射便能够快速的找到要查找的值。其实有点类似与通信中的调制与解调哈。 如上图 我们根据插入元素的关键码将其通过哈希函数的计算后便可以得到该元素的存储位置。 其是一一映射的关系。 当我们要查找某元素时我们便可以根据该元素的关键码再通过哈希函数的计算后得出该元素的位置。效率是不是感觉高的起飞 我们将该方法称为哈希方法将转换函数称为哈希函数将该结构称为哈希表。 这么牛逼的想法我怎么现在才知道难道就仅仅这么简单吗 哈哈哈哈哈哈当然不会这么容易。一刚才的图为例当我们插入4411这样的值后我们就会发现其产生了冲突位置被占用了我们把这种冲突称为哈希冲突这该怎么办呢 我们下一节来进行讲解。
二哈希冲突
我们把不同关键字通过哈希函数计算得出相同的地址的这种现象称为哈希冲突。 既然元素的存储地址是通过哈希函数的计算得出的那么哈希冲突当然也与哈希函数的设计有关好的哈希函数可以减少哈希冲突的发生。
哈希函数
哈希函数的设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见的几种哈希函数
直接定址法 取关键字的某个线性函数为散列地址HashKey A*Key B。 其优点是简单均匀缺点是要提前知道关键字的分布情况。
除留余数法 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址。 那为什么最好要是质数呢 有以下结论 如果有一个数列s间隔为1那么不管模数为几都是均匀分布的因为间隔为1是最小单位
如果一个数列s间隔为模本身那么在哈希表中的分布仅占有其中的一列也就是处处冲突
数列的冲突分布间隔为因子大小同样的随机数列因子越多冲突的可能性就越大。 具体验证过程大家可以看下面这篇文章 除留余数法为什么选择质数取模
平方取中法 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况。
折叠法 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况。
随机数法 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。 通常应用于关键字长度不等时采用此法。
哈希函数设计的越好冲突就越少但冲突无法避免。
哈希冲突解决
最常见的两种解决方法闭散列与开散列。 我们先来说闭散列 当发生哈希冲突时若哈希表未满则将元素放到下一个空位置。 寻找空位置也有两种方法线性探测和二次探测。 什么叫线性探测呢从冲突的位置开始一次向后找知道找到下一个空位置。 哈希表中元素的删除 如上图所示我们采用线性探测法来寻找空位置当我们要删除元素4时便会出现一个问题若我们直接将4从表中物理删除后当再去查找44时就会出现找不到的情况。因此我们采用伪删除来解决。就是我们给哈希表中的每个位置给一个标记EMPTY / FILLED / DELETE。这样就可以避免上面的问题了。 为了使冲突尽可能的少我们哈希表的空间会被插入的元素个数要大。我们将 插入的元素个数/哈希表的大小 之比称为载荷因子。
enum State{EMPTY,DELETE,FILL};templateclass K, class Vstruct Hash_Node{pairK, V _kv;State _state EMPTY;};bool Insert(const pairK, V kv){//查找if (Find(kv)){return false;}//扩容if (_size 0 ||(_size * 10)/ _table.size() 7){size_t newsize _table.size() 0 ? 5 : _table.size() * 2;Hash_tableK, V tmp;tmp._table.resize(newsize);for (auto e : _table){if (e._state FILL){tmp.Insert(e._kv);}}_table.swap(tmp._table);}Hash _hash;size_t tablei _hash(kv.first) % _table.size();while (_table[tablei]._state FILL){tablei;tablei % _table.size();}_table[tablei]._kv kv;_table[tablei]._state FILL;_size;return true;}当超过载荷因子后要进行扩容在扩容时我们申请一个容量更大的哈希表然后将旧表的数据移到新表中这里我们采用了一个相对较聪明的写法我们将旧表遍历一遍调用插入函数进行插入。最后哈希表的底层是vector我们再调用vector的交换函数可以将两个指向不同vector对象的指针进行交换。这样就扩容完成了。
线性探测的缺点当多个哈希冲突集中在一起会发生数据堆积这样在查找时比较的次数就会增多影响效率。而二次探测就可以避免这样的问题。 二次探测在这里我们就简单了解 当我们发生冲突时设发生冲突的位置为x我们去找x1^2%表长 这个位置若还是冲突则找x-1^2%表长 这个位置若仍冲突则找x2^2%表长 这个位置…直到没有冲突。
开散列 开散列是指将关键码集合通过哈希函数计算后得出地址将具有相同地址的关键码集中在一个子集合。每一个子集合称为桶。桶中的元素通过链表链接起来哈希表中存储的是链表的头结点。 代码如下
templateclass K,class V,class HashHashFuncKclass Hash_Bucket{typedef Hash_NodeK,V Node;public:bool Insert(const pairK, V kv){Hash hash;//查找if (Find(kv)){return false;}//扩容if (_size _Bucket.size())//这里有点小问题当桶的数量等于元素数量时就扩容这样冲突小。{if (_size 0){_Bucket.resize(5);}else{vectorNode* tmp;tmp.resize(_Bucket.size() * 2);size_t i 0;for (i 0; i _Bucket.size(); i){Node* cur _Bucket[i];while (cur){size_t tmpi hash(cur-_kv.first) % tmp.size();Node* next cur-_next;cur-_next tmp[tmpi];tmp[tmpi]cur;cur next;}//_Bucket[i] nullptr;}_Bucket.swap(tmp);}}//插入size_t Bucketi hash(kv.first) % _Bucket.size();Node* cur new Node(kv);cur-_next _Bucket[Bucketi];_Bucket[Bucketi]cur;_size;return true;}bool Find(const pairK, V kv){if (_size 0){return false;}Hash hash;size_t Bucketi hash(kv.first) % _Bucket.size();Node* cur _Bucket[Bucketi];while (cur){if (cur-_kv kv){return true;}else{cur cur-_next;}}return false;}private:vectorHash_NodeK, V* _Bucket;size_t _size0;};这里我们重点讲一下开散列的扩容 首先就是什么时候扩容比较好开散列性能最好当然就是一个桶直挂一个元素的时候是最好的因此当桶的数量等于元素的数量时扩容是比较好的。接着我们讲一下扩容的具体操作。与闭散列不同的是闭散列是直接再实例化了一个哈希表对象再进行插入操作最后交换了两个指向vector的指针。而我们的开散列这样做会比较浪费空间因为我们的元素存储再一个一个的结点中因此我们不妨将这些结点再利用起来让其插入再新的哈希表中再将指向新旧哈希表的指针进行交换。
我们的哈希表只能存储key为整型的元素那么如何存储其他元素呢 我们可以提供一个能够将key转化为整型的仿函数。
templateclass Kstruct HashFunc{size_t operator() (const K key){return (size_t)key;}};templatestruct HashFuncstring//特化{size_t operator() (const string key){size_t ret 0;for (auto e : key){ret e;}return ret;}};unordered_map与unordered_set
unordered_map与unordered_set的底层结构为哈希表其封装过程及其对哈希表的改造与map与set相似这里我们就不过多阐述我们直接看代码
改造后的哈希表
templateclass Tstruct Hash_Node{Hash_Node* _next;T _data;Hash_Node(const T data):_data(data), _next(nullptr){}};templateclass K, class T, class Hash, class KeyOfTclass Hash_Bucket;templateclass K,class T,class Hash,class KeyOfTstruct _Iterator{typedef Hash_NodeT Node;typedef _Iterator Self;typedef Hash_BucketK, T, Hash, KeyOfT _Ht;Node* _node;_Ht* _pht;Hash hash;KeyOfT kot;_Iterator(Node* node,_Ht* pht):_node(node),_pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s)const{return _node ! s._node;}Self operator(){if (_node-_next){_node _node-_next;}else{size_t i hash(kot(_node-_data)) % _pht-_Bucket.size();i;for (; i _pht-_Bucket.size(); i){if (_pht-_Bucket[i]){_node _pht-_Bucket[i];break;}}if (i _pht-_Bucket.size()){_node nullptr;}}return *this;}};templateclass K,class T,class Hash,class KeyOfTclass Hash_Bucket{typedef Hash_NodeT Node;templateclass K, class T, class Hash, class KeyOfTfriend struct _Iterator;public:typedef typename _IteratorK, T, Hash, KeyOfT iterator;inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes 28;static const size_t __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, 3221225473, 4294967291};for (size_t i 0; i __stl_num_primes; i){if (__stl_prime_list[i] n){return __stl_prime_list[i];}}return -1;}pairiterator,bool Insert(const T data){KeyOfT kot;Hash hash;//查找if (Find(kot(data)).second){return Find(kot(data));}//扩容if (_size _Bucket.size()){vectorNode* tmp;tmp.resize(__stl_next_prime(_Bucket.size()),nullptr);size_t i 0;for (i 0; i _Bucket.size(); i){Node* cur _Bucket[i];while (cur){size_t tmpi hash(kot(cur-_data)) % tmp.size();Node* next cur-_next;cur-_next tmp[tmpi];tmp[tmpi]cur;cur next;}//_Bucket[i] nullptr;}_Bucket.swap(tmp);}//插入size_t Bucketi hash(kot(data)) % _Bucket.size();Node* cur new Node(data);cur-_next _Bucket[Bucketi];_Bucket[Bucketi]cur;_size;return make_pair(iterator(cur,this),true);}size_t Erase(const K key){Hash hash;KeyOfT kot;size_t Bucketi hash(key) % _Bucket.size();Node* cur _Bucket[Bucketi];Node* prev nullptr;while (cur){if (kot(cur-_data) key){//可能为头结点也可能为中间结点if (kot(_Bucket[Bucketi]-_data) key){_Bucket[Bucketi]cur-_next;delete cur;_size--;return 1;}else{prev-_nextcur-_next;delete cur;_size--;return 1;}}else{prev cur;cur cur-_next;}}return 0;}pairiterator,bool Find(const K key){KeyOfT kot;if (_size 0){return make_pair(iterator(nullptr,this),false);}Hash hash;size_t Bucketi hash(key) % _Bucket.size();Node* cur _Bucket[Bucketi];while (cur){if (kot(cur-_data) key){return make_pair(iterator(cur, this), true);}else{cur cur-_next;}}return make_pair(iterator(nullptr, this), false);}iterator begin(){for (size_t i 0; i _Bucket.size(); i){if (_Bucket[i]){return iterator(_Bucket[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}private:vectorHash_NodeT* _Bucket;size_t _size0;};封装的unordered_map
templateclass Kstruct HashFunc{size_t operator() (const K key){return (size_t)key;}};templatestruct HashFuncstring{size_t operator() (const string key){size_t ret 0;for (auto e : key){ret e;}return ret;}};templateclass K, class V,class Hash HashFuncKclass unordered_map{struct KeyOfM{const K operator() (const pairK, V kv){return kv.first;}};public:typedef typename Hash_BucketK, pairK, V, Hash, KeyOfM::iterator iterator;pairiterator,bool Insert(const pairK, V kv){return _ht.Insert(kv);}size_t 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;}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}private:Hash_BucketK, pairK,V,Hash, KeyOfM _ht;};封装的unordered_set
templateclass K, class HashHashFuncKclass unordered_set{ struct KeyOfS{const K operator() (const K key){return key;}};public:typedef typename Hash_BucketK,K,Hash,KeyOfS::iterator iterator;pairiterator, bool Insert(const K key){return _ht.Insert(key);}size_t Erase(const K key){return _ht.Erase(key);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}private:Hash_BucketK, K, Hash, KeyOfS _ht;};
