前言哈希又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立一个哈希映射关系查找时通过这个哈希函数计算出Key存储的位置进行快速查找。1.直接定址法当关键字的范围比较集中时直接定址法就是非常简单高效的方法如一组关键字都在[0,99]之间那么我们开一个100个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母那么我们开一个26个数的数组每个关键字ascii码-a就是存储位置的下标也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。字符串中的第一个唯一字符1234567891011classSolution {public:intfirstUniqChar(string s) {//桶思想vectorint cnt(26,0);//统计次数for(auto i:s) cnt[i-a];for(size_ti0;is.size();i)if(cnt[s[i]-a]1)returni;return-1;}};2.哈希冲突直接定址法的缺点也非常明显当关键字的范围比较分散时就很浪费内存甚至内存不够用。假设只有数据范围是[0,9999]的N个值要映射到一个M个空间的数组中一般情况下MN那么就要借助哈希函数hash functionhf关键字key被放在数组的hkey位置要注意的是hkey计算出的值必须在[0,M)之间。这里存在的一个问题就是两个不同的key可能会映射到同一个位置这种问题叫哈希冲突或哈希碰撞。理想情况是找出一个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的方案。3.负载因子假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子N/M负载因子有些地方也翻译为荷载因子/装载因子英文为load factor。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低。4.将关键字转成整数将关键字映射到数组中位置一般是整数好做映射计算若不是整数要想办法转换成整数。5.哈希函数一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是要尽量往这个方向去考量设计。5.1除法散列法/除留余数法●除法散列法也叫除留余数法顾名思义假设哈希表的大小为M那么通过key除以M的余数作为映射位置的下标也就是哈希函数为hkeykey%M。●当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。若是2^x那么key%2^x本质相当于保留key的后x位那么后x位相同的值计算出的哈希值都是一样的就冲突了。如{6331}看起来没有关联的值若M是16也就是2^4那么计算出的哈希值都是15因为63的二进制后8位是0011111131的二进制后8位是00111111。若是10^x就更明显了保留的都是10进制的后x位如{112,12312}若M是100也就是10^2那么计算出的哈希值都是12。●当使用除法散列法时建议M取不太接近2的整数次幂的一个质数素数。●需要说明的是Java的HashMap采用除法散列法时就是2的整数次幂做哈希表的大小M这样的话就不用取模而可以直接位运算相对而言位运算比模更高效一些。但它不是单纯的去取模比如M是2^16次方本质是取后16位那么用keykey16然后把key和key异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内但是尽量让key所有的位都参与计算这样映射出的哈希值更均匀一些。所以建议M取不太接近2的整数次幂的一个质数的理论是大多数数据结构书籍中写的理论但实践中需灵活运用。5.2乘法散列法了解●乘法散列法对哈希表大小M没有要求它的大思路第一步用关键字K乘上常数A0A1)并抽出K*A的小数部分。第二步后再用M乘以K*A的小数部分在向下取整。●hkeyfloorMxAxkey%1.0其中floor表示对表达式进行向下取整A∈01这里最重要的是A的值应该如何设定Knuth认为A√5-1/20.6180339887……黄金分割点比较好。●乘法散列法对哈希表大小M是没有要求的假设M位1024key为1234A0.6180339887A*key762.6539420558取小数部分为0.6539420558MxAxkey%1.00.6539420558*1024669.6366651392那么h1234669。5.3全域散列法了解●若存在一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中。这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决方法就是给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。●hkeyaxkeyb%P%MP需要选一个足够大的质数a可以随机选[1,P-1]之间的任意整数b可以随机选[0,P-1]之间的任意整数这些函数构成了一个P*P-1组全域散列函数组。假设P17M6a3b4则h83x84%17%65。●需要注意每次初始化哈希表时随机选取全域散列函数组中的一个散列函数使用后续增删查改都固定使用这个散列函数否则每次哈希都是随机选一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致找不到插入的key了。5.4其它方法了解●上面的几种方法是《算法导论》书籍中讲解的方法。●《殷人昆 数据结构用面向对象方法与C语言描述第二版》和《数据结构C语言版 严蔚敏_吴伟民》等教材型书籍上面还给出平方取中法、折叠法、随机数法、数学分析法等这些方法相对更适用于一些局限的特定场景。6.处理哈希冲突实际中哈希表一般还是选择除法散列法作为哈希函数当然哈希表无论选择什么哈希函数也避免不了冲突那么插入数据时如何解决冲突主要有两种方法开放定址法和链地址法。6.1开放定址法在开放定址法中所有的元素都放在哈希表中当一个关键字key用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于1的。这里的规则有三种线性探测、二次探测、双重探测。线性探测●从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止若走到哈希表尾则绕回到哈希表头的位置。●hkeyhash0key%Mhash0位置冲突了则线性探测公式为hckeyihashihash0i%Mi{123…M-1}因为负载因子小于1则最多探测M-1次一定能找到一个存储key的位置。●线性探测的比较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。下面的二次探测可以一定程度改善这个问题。●下面演示{193053613202112}等这一组值映射到M11的表中。h198h308h55h363h132h209h2110h121二次探测●从发生冲突的位置开始依次左右二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止若往右走到哈希表尾则回绕到哈希表头的位置若往左走到哈希表头则绕回到哈希表尾的位置●h(keyhash0key%Mhash0位置冲突了则二次探测公式为hckeyihashihash0∓i^2)%Mi{123…M/2}●二次探测当hashihash0-i^2%M时当hashi0时需要hashiM●下面演示{193052631122}等这一组值映射到M11的表中。h198h308h528h638h110h220双重散列了解●第一个哈希函数计算出的值发生冲突使用第二个哈希函数计算出一个跟key相关的偏移量值不断往后探测直到寻找到下一个没有存储数据的位置为止。●h1keyhash0key%Mhash0位置冲突了则双重探测公式为hckeyihashihash0i*h2key%Mi{123…M}。●要求h2keyM且h2key和M互为质数有两种简单的取值方法1、当M为2整数幂时h2key从[0,M-1]任选一个奇数2、当M为质数时h2keykey%M-11●保证h2key与M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群若最大公约数pg c dMh1key)1那么所能寻址的位置的个数为M/PM使得对于一个关键字来说无法充分领用整个散列表。例若初始探测位置为1偏移量为3整个散列表大小为12那么所能寻址的位置为{14710}寻址个数为12/g c d1234●下面演示{19305274}等这一组值映射到M11的表中设h2keykey%1016.2开放定址法代码实现开放地址法在实践中不如下面链地址法因为开发定址法解决冲突不管使用哪种方法占用的都是哈希表中的空间始终存在互相影响的问题。所以开放定址法简单选择线性探测实现。开发定址法的哈希表结构1234567891011121314enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V _kv;State _stateEMPTY;};templateclassK,classVclassHashTable{private:vectorHashDataK,V _tables;int_n;};要注意这里需要给每个存储值的位置加一个状态标识否则删除一些值后回影响后面冲突的值的查找。如下图删除30回导致查找20失败当我们给每个位置加一个状态标识{EXISTEMPTYDELETE}删除30就可以不用删除值而是把状态改成DELETE那么查找20是时遇到EMPTY才能停止就可以找到20.h198h308h55h363h132h209h2110h121扩容哈希表负载因子控制在0.7当负载因子到0.7以后就需要扩容按照2倍扩容但是同时要保持哈希表是一个质数第一个是质数2倍后就不是质数了。那么如何解决一种方案就是上面1.4.1除法散列中的Java HashMap的使用2的整数幂但是计算时不能直接取模的改进方法。另一种方案时sgi版本的哈希表使用的方法给了一个近似2倍的质数表每次取质数表获取扩容后的大小。12345678910111213141516inlineunsignedlong__stl_next_prime(unsignedlongn){//Note:assumes long is at least 32 bitsstaticconstint__stl_num_primes28;staticconstunsignedlong__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};constunsignedlong* first__stl_prime_list;constunsignedlong* last__stl_prime_list__stl_num_primes;constunsignedlong* poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}key不能取模的问题当key是string/Date等类型是key不能取模那么需要给HashTable增加一个仿函数这个仿函数支持把key转换成一个可以取模的整型若key可以转换为整型并且不容易冲突那么这个仿函数就用默认参数即可若这个key不能转换成整型就需要自己实现一个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每个值都参与到计算中让不同的key转换出的整型值不同。string做哈希表的key非常常见所以可以把sring特化一下。123456789101112131415161718192021222324templateclassKstructHashFunc{size_toperator()(constK key){return(size_t)key;}};templatestructHashFuncstring{size_toperator()(conststring s){//BKDRsize_thash0;for(auto ch:s){hashch;hash*131;}returnhash;}};templateclassK,classV,classHashHashFuncKclassHashTable{private:vectorHashDataK,V _tables;int_n;};完整代码示例12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485namespaceopen_address{templateclassK,classV,classHashHashFuncKclassHashTable{public:HashTable():_tables(__stl_next_prime(0)),_n(0){}boolInsert(constpairK,V kv){if(Find(kv.first)){returnfalse;}//负载因子0.7,扩容if(_n*10/_tables.size()0.7){//旧法等于说把Insert接口的逻辑又实现了一遍// vectorHashDataK,V nextables(_tables.size()*2);// for(auto data:_tables){// //旧表的数据映射到新表// if(data._stateEXIST){// size_t hash0data._kv.first%newtables.size();// //……// }// }//现代写法HashTableK,V newht;//newht._tables.resize(_tables.size()*2);newht._tables.resize(__stl_next_prime(_tables.size()1));for(auto data:_tables){//旧表映射到新表if(data._stateEXIST)newht.Insert(data._kv);}_tables.swap(newht._tables);}size_thash0kv.first%_tables.size();size_thash1hash0;inti1;intflag1;while(_tables[hash1]._stateEXIST){//线性探测hash1(hash0i)%_tables.size();i;//二次探测/*hash1(hash0(i*i*flag))%_tables.size();if(hash1_tables.size()){hash1_tables.size();}if(flag1)flag-1;else{i;flag-1;}*/}_tables[hash1]._kvkv;_tables[hash1]._stateEXIST;_n;returnfalse;}HashDataK,V* Find(constK key){size_thash0key%_tables.size();size_thash1hash0;inti1;while(_tables[hash1]._state!EMPTY){if(_tables[hash1]._kv.firstkey_tables[hash1]._stateEXIST)return_tables[hash1];hash1(hash0i)%_tables.size();i;}returnnullptr;}boolErase(constK key){HashDataK,V* retFind(key);if(ret){ret-_stateDELETE;--_n;returntrue;}elsereturnfalse;}private:vectorHashDataK,V _tables;int_n;};}6.3链地址法解决冲突的思路开放定址法中所有的元素都放在哈希表里链地址法中所有的数据不再直接存储在哈希表中哈希表中存储一个指针没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成一个链表挂在哈希表这个位置下面链地址法也叫拉链法或哈希桶。●下面演示{1930536132021122496}等这一组值映射到M11的表中。h198h308h55h363h132h209h2110h121h242h9688扩容开放定址法负载因子必须小于1链地址法的负载因子就没有限制了可以大于1。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低stl中unordered_xxx的最大负载因子基本控制在1大于1就扩容。极端场景若极端场景下某个桶特别长怎么办可以考虑使用全域散列法这样就不容易被针对。但是假设不是被针对了用来全域散列法但是偶然情况下某个桶很长查找效率很低怎么办在Java8的HashMap中当桶的长度超过一定阈值8时就把链表转换成红黑树。一般情况下不断扩容单个桶很长的场景还是比较少的。6.4链地址法代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112namespacehash_bukect{templateclassK,classVstructHashNode{pairK,V _kv;HashNodeK,V* _next;HashNode(constpairK,V kv):_kv(kv),_next(nullptr){}};templateclassK,classV,classHashHashFuncKclassHashTable{typedefHashNodeK,V Node;public:HashTable():_tables(11),_n(0){}inlineunsignedlong__stl_next_prime(unsignedlongn){//Note:assumes long is at least 32 bitsstaticconstint__stl_num_primes28;staticconstunsignedlong__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};constunsignedlong* first__stl_prime_list;constunsignedlong* last__stl_prime_list__stl_num_primes;constunsignedlong* poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}boolInsert(constpairK,V kv){//当负载因子为1时扩容if(_n_tables.size()){//直接复用Insert不好/*HashTableK,V newht;newht._tables.resize(_tables.size()*2);for(int i0;i_tables.size();i){Node* cur_tables[i];while(cur){newht.Insert(cur);curcur-_next;}}_tables.swap(newht);*/HashTableK,V newht;newht._tables.resize(_tables.size()*2);//newht._tables.resize(__stl_next_prime(_tables.size()1));for(inti0;i_tables.size();i){Node* cur_tables[i];while(cur){Node* nextcur-_next;size_thash1cur-_kv.first%newht._tables.size();//头插cur-_nextnewht[hash1];newht[hash1]cur;curnext;}_tables[i]nullptr;}_tables.swap(newht);}//头插size_thash1kv.first%_tables.size();Node* newNodenewNode(kv);newNode-next_tables[hash1];_tables[hash1]newNode;_n;returntrue;}Node* Find(constK key){size_thash0key%_tables.size();Node* cur_tables[hash0];while(cur){if(cur-_kv.firstkey)returncur;curcur-_next;}returnnullptr;}boolErase(constK key){//没有这个值if(!Find(key))returnfalse;size_thash0key%_tables.size();Node* cur_tables[hash0];Node* prevnullptr;while(cur){if(cur-_kvkey){//删除的节点是链表的头if(!prev){_tables[hash0]cur-_next;}else{prev-_nextcur-_next;}deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}private:vectorHashNodeK,V* _tables;size_t_n;};}以上就是C哈希表的实现思路剖析讲解的详细内容 C++哈希表的实现思路剖析讲解
前言哈希又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立一个哈希映射关系查找时通过这个哈希函数计算出Key存储的位置进行快速查找。1.直接定址法当关键字的范围比较集中时直接定址法就是非常简单高效的方法如一组关键字都在[0,99]之间那么我们开一个100个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母那么我们开一个26个数的数组每个关键字ascii码-a就是存储位置的下标也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。字符串中的第一个唯一字符1234567891011classSolution {public:intfirstUniqChar(string s) {//桶思想vectorint cnt(26,0);//统计次数for(auto i:s) cnt[i-a];for(size_ti0;is.size();i)if(cnt[s[i]-a]1)returni;return-1;}};2.哈希冲突直接定址法的缺点也非常明显当关键字的范围比较分散时就很浪费内存甚至内存不够用。假设只有数据范围是[0,9999]的N个值要映射到一个M个空间的数组中一般情况下MN那么就要借助哈希函数hash functionhf关键字key被放在数组的hkey位置要注意的是hkey计算出的值必须在[0,M)之间。这里存在的一个问题就是两个不同的key可能会映射到同一个位置这种问题叫哈希冲突或哈希碰撞。理想情况是找出一个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的方案。3.负载因子假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子N/M负载因子有些地方也翻译为荷载因子/装载因子英文为load factor。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低。4.将关键字转成整数将关键字映射到数组中位置一般是整数好做映射计算若不是整数要想办法转换成整数。5.哈希函数一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是要尽量往这个方向去考量设计。5.1除法散列法/除留余数法●除法散列法也叫除留余数法顾名思义假设哈希表的大小为M那么通过key除以M的余数作为映射位置的下标也就是哈希函数为hkeykey%M。●当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。若是2^x那么key%2^x本质相当于保留key的后x位那么后x位相同的值计算出的哈希值都是一样的就冲突了。如{6331}看起来没有关联的值若M是16也就是2^4那么计算出的哈希值都是15因为63的二进制后8位是0011111131的二进制后8位是00111111。若是10^x就更明显了保留的都是10进制的后x位如{112,12312}若M是100也就是10^2那么计算出的哈希值都是12。●当使用除法散列法时建议M取不太接近2的整数次幂的一个质数素数。●需要说明的是Java的HashMap采用除法散列法时就是2的整数次幂做哈希表的大小M这样的话就不用取模而可以直接位运算相对而言位运算比模更高效一些。但它不是单纯的去取模比如M是2^16次方本质是取后16位那么用keykey16然后把key和key异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内但是尽量让key所有的位都参与计算这样映射出的哈希值更均匀一些。所以建议M取不太接近2的整数次幂的一个质数的理论是大多数数据结构书籍中写的理论但实践中需灵活运用。5.2乘法散列法了解●乘法散列法对哈希表大小M没有要求它的大思路第一步用关键字K乘上常数A0A1)并抽出K*A的小数部分。第二步后再用M乘以K*A的小数部分在向下取整。●hkeyfloorMxAxkey%1.0其中floor表示对表达式进行向下取整A∈01这里最重要的是A的值应该如何设定Knuth认为A√5-1/20.6180339887……黄金分割点比较好。●乘法散列法对哈希表大小M是没有要求的假设M位1024key为1234A0.6180339887A*key762.6539420558取小数部分为0.6539420558MxAxkey%1.00.6539420558*1024669.6366651392那么h1234669。5.3全域散列法了解●若存在一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中。这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决方法就是给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。●hkeyaxkeyb%P%MP需要选一个足够大的质数a可以随机选[1,P-1]之间的任意整数b可以随机选[0,P-1]之间的任意整数这些函数构成了一个P*P-1组全域散列函数组。假设P17M6a3b4则h83x84%17%65。●需要注意每次初始化哈希表时随机选取全域散列函数组中的一个散列函数使用后续增删查改都固定使用这个散列函数否则每次哈希都是随机选一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致找不到插入的key了。5.4其它方法了解●上面的几种方法是《算法导论》书籍中讲解的方法。●《殷人昆 数据结构用面向对象方法与C语言描述第二版》和《数据结构C语言版 严蔚敏_吴伟民》等教材型书籍上面还给出平方取中法、折叠法、随机数法、数学分析法等这些方法相对更适用于一些局限的特定场景。6.处理哈希冲突实际中哈希表一般还是选择除法散列法作为哈希函数当然哈希表无论选择什么哈希函数也避免不了冲突那么插入数据时如何解决冲突主要有两种方法开放定址法和链地址法。6.1开放定址法在开放定址法中所有的元素都放在哈希表中当一个关键字key用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于1的。这里的规则有三种线性探测、二次探测、双重探测。线性探测●从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止若走到哈希表尾则绕回到哈希表头的位置。●hkeyhash0key%Mhash0位置冲突了则线性探测公式为hckeyihashihash0i%Mi{123…M-1}因为负载因子小于1则最多探测M-1次一定能找到一个存储key的位置。●线性探测的比较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。下面的二次探测可以一定程度改善这个问题。●下面演示{193053613202112}等这一组值映射到M11的表中。h198h308h55h363h132h209h2110h121二次探测●从发生冲突的位置开始依次左右二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止若往右走到哈希表尾则回绕到哈希表头的位置若往左走到哈希表头则绕回到哈希表尾的位置●h(keyhash0key%Mhash0位置冲突了则二次探测公式为hckeyihashihash0∓i^2)%Mi{123…M/2}●二次探测当hashihash0-i^2%M时当hashi0时需要hashiM●下面演示{193052631122}等这一组值映射到M11的表中。h198h308h528h638h110h220双重散列了解●第一个哈希函数计算出的值发生冲突使用第二个哈希函数计算出一个跟key相关的偏移量值不断往后探测直到寻找到下一个没有存储数据的位置为止。●h1keyhash0key%Mhash0位置冲突了则双重探测公式为hckeyihashihash0i*h2key%Mi{123…M}。●要求h2keyM且h2key和M互为质数有两种简单的取值方法1、当M为2整数幂时h2key从[0,M-1]任选一个奇数2、当M为质数时h2keykey%M-11●保证h2key与M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群若最大公约数pg c dMh1key)1那么所能寻址的位置的个数为M/PM使得对于一个关键字来说无法充分领用整个散列表。例若初始探测位置为1偏移量为3整个散列表大小为12那么所能寻址的位置为{14710}寻址个数为12/g c d1234●下面演示{19305274}等这一组值映射到M11的表中设h2keykey%1016.2开放定址法代码实现开放地址法在实践中不如下面链地址法因为开发定址法解决冲突不管使用哪种方法占用的都是哈希表中的空间始终存在互相影响的问题。所以开放定址法简单选择线性探测实现。开发定址法的哈希表结构1234567891011121314enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V _kv;State _stateEMPTY;};templateclassK,classVclassHashTable{private:vectorHashDataK,V _tables;int_n;};要注意这里需要给每个存储值的位置加一个状态标识否则删除一些值后回影响后面冲突的值的查找。如下图删除30回导致查找20失败当我们给每个位置加一个状态标识{EXISTEMPTYDELETE}删除30就可以不用删除值而是把状态改成DELETE那么查找20是时遇到EMPTY才能停止就可以找到20.h198h308h55h363h132h209h2110h121扩容哈希表负载因子控制在0.7当负载因子到0.7以后就需要扩容按照2倍扩容但是同时要保持哈希表是一个质数第一个是质数2倍后就不是质数了。那么如何解决一种方案就是上面1.4.1除法散列中的Java HashMap的使用2的整数幂但是计算时不能直接取模的改进方法。另一种方案时sgi版本的哈希表使用的方法给了一个近似2倍的质数表每次取质数表获取扩容后的大小。12345678910111213141516inlineunsignedlong__stl_next_prime(unsignedlongn){//Note:assumes long is at least 32 bitsstaticconstint__stl_num_primes28;staticconstunsignedlong__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};constunsignedlong* first__stl_prime_list;constunsignedlong* last__stl_prime_list__stl_num_primes;constunsignedlong* poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}key不能取模的问题当key是string/Date等类型是key不能取模那么需要给HashTable增加一个仿函数这个仿函数支持把key转换成一个可以取模的整型若key可以转换为整型并且不容易冲突那么这个仿函数就用默认参数即可若这个key不能转换成整型就需要自己实现一个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每个值都参与到计算中让不同的key转换出的整型值不同。string做哈希表的key非常常见所以可以把sring特化一下。123456789101112131415161718192021222324templateclassKstructHashFunc{size_toperator()(constK key){return(size_t)key;}};templatestructHashFuncstring{size_toperator()(conststring s){//BKDRsize_thash0;for(auto ch:s){hashch;hash*131;}returnhash;}};templateclassK,classV,classHashHashFuncKclassHashTable{private:vectorHashDataK,V _tables;int_n;};完整代码示例12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485namespaceopen_address{templateclassK,classV,classHashHashFuncKclassHashTable{public:HashTable():_tables(__stl_next_prime(0)),_n(0){}boolInsert(constpairK,V kv){if(Find(kv.first)){returnfalse;}//负载因子0.7,扩容if(_n*10/_tables.size()0.7){//旧法等于说把Insert接口的逻辑又实现了一遍// vectorHashDataK,V nextables(_tables.size()*2);// for(auto data:_tables){// //旧表的数据映射到新表// if(data._stateEXIST){// size_t hash0data._kv.first%newtables.size();// //……// }// }//现代写法HashTableK,V newht;//newht._tables.resize(_tables.size()*2);newht._tables.resize(__stl_next_prime(_tables.size()1));for(auto data:_tables){//旧表映射到新表if(data._stateEXIST)newht.Insert(data._kv);}_tables.swap(newht._tables);}size_thash0kv.first%_tables.size();size_thash1hash0;inti1;intflag1;while(_tables[hash1]._stateEXIST){//线性探测hash1(hash0i)%_tables.size();i;//二次探测/*hash1(hash0(i*i*flag))%_tables.size();if(hash1_tables.size()){hash1_tables.size();}if(flag1)flag-1;else{i;flag-1;}*/}_tables[hash1]._kvkv;_tables[hash1]._stateEXIST;_n;returnfalse;}HashDataK,V* Find(constK key){size_thash0key%_tables.size();size_thash1hash0;inti1;while(_tables[hash1]._state!EMPTY){if(_tables[hash1]._kv.firstkey_tables[hash1]._stateEXIST)return_tables[hash1];hash1(hash0i)%_tables.size();i;}returnnullptr;}boolErase(constK key){HashDataK,V* retFind(key);if(ret){ret-_stateDELETE;--_n;returntrue;}elsereturnfalse;}private:vectorHashDataK,V _tables;int_n;};}6.3链地址法解决冲突的思路开放定址法中所有的元素都放在哈希表里链地址法中所有的数据不再直接存储在哈希表中哈希表中存储一个指针没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成一个链表挂在哈希表这个位置下面链地址法也叫拉链法或哈希桶。●下面演示{1930536132021122496}等这一组值映射到M11的表中。h198h308h55h363h132h209h2110h121h242h9688扩容开放定址法负载因子必须小于1链地址法的负载因子就没有限制了可以大于1。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低stl中unordered_xxx的最大负载因子基本控制在1大于1就扩容。极端场景若极端场景下某个桶特别长怎么办可以考虑使用全域散列法这样就不容易被针对。但是假设不是被针对了用来全域散列法但是偶然情况下某个桶很长查找效率很低怎么办在Java8的HashMap中当桶的长度超过一定阈值8时就把链表转换成红黑树。一般情况下不断扩容单个桶很长的场景还是比较少的。6.4链地址法代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112namespacehash_bukect{templateclassK,classVstructHashNode{pairK,V _kv;HashNodeK,V* _next;HashNode(constpairK,V kv):_kv(kv),_next(nullptr){}};templateclassK,classV,classHashHashFuncKclassHashTable{typedefHashNodeK,V Node;public:HashTable():_tables(11),_n(0){}inlineunsignedlong__stl_next_prime(unsignedlongn){//Note:assumes long is at least 32 bitsstaticconstint__stl_num_primes28;staticconstunsignedlong__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};constunsignedlong* first__stl_prime_list;constunsignedlong* last__stl_prime_list__stl_num_primes;constunsignedlong* poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}boolInsert(constpairK,V kv){//当负载因子为1时扩容if(_n_tables.size()){//直接复用Insert不好/*HashTableK,V newht;newht._tables.resize(_tables.size()*2);for(int i0;i_tables.size();i){Node* cur_tables[i];while(cur){newht.Insert(cur);curcur-_next;}}_tables.swap(newht);*/HashTableK,V newht;newht._tables.resize(_tables.size()*2);//newht._tables.resize(__stl_next_prime(_tables.size()1));for(inti0;i_tables.size();i){Node* cur_tables[i];while(cur){Node* nextcur-_next;size_thash1cur-_kv.first%newht._tables.size();//头插cur-_nextnewht[hash1];newht[hash1]cur;curnext;}_tables[i]nullptr;}_tables.swap(newht);}//头插size_thash1kv.first%_tables.size();Node* newNodenewNode(kv);newNode-next_tables[hash1];_tables[hash1]newNode;_n;returntrue;}Node* Find(constK key){size_thash0key%_tables.size();Node* cur_tables[hash0];while(cur){if(cur-_kv.firstkey)returncur;curcur-_next;}returnnullptr;}boolErase(constK key){//没有这个值if(!Find(key))returnfalse;size_thash0key%_tables.size();Node* cur_tables[hash0];Node* prevnullptr;while(cur){if(cur-_kvkey){//删除的节点是链表的头if(!prev){_tables[hash0]cur-_next;}else{prev-_nextcur-_next;}deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}private:vectorHashNodeK,V* _tables;size_t_n;};}以上就是C哈希表的实现思路剖析讲解的详细内容