一、哈希1.1 哈希的概念什么是哈希呢哈希又称散列是一种组织数据的方式。是一种通过哈希函数把关键字 key 跟存储位置建立一个映射关系查找时通过这个哈希函数计算出 key 存储的位置进行快速查找。.直接定址法当关键字的范围比较集中时就可以采用直接定址法。举个例子一组关键字都在[099]之间我们就可以开一个100个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[az]的小写字母那么我们就可以开一个26个数的数组每个关键字的 ascii码值就是存储位置的下标。直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。但是这种方式也有缺点那就是关键字的范围比较分散时就很浪费内存甚至内存不够用。所以这种方式也比较鸡肋。利用哈希函数来计算哈希值的这种方式有一个问题就是两个不同的 key 可能会映射到同一个位置去这个问题就叫做哈希冲突/哈希碰撞。理想情况下是找一个好的哈希函数来避免哈希冲突但哈希冲突是不可避免的。所以要尽可能的设计出优秀的哈希函数来减少冲突的次数。.负载因子假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子 N / M负载因子也可以叫做载荷因子/装载因子等。负载因子越大哈希冲突的概率越高空间利用率越高反之负载因子越小哈希冲突的概率越低空间利用率越低。为什么呢因为负载因子 N / M负载因子越大没说明N越大哈希表中存储的数据越多所以空间利用率越高哈希冲突概率越高。通过上述对于哈希的基础了解我们可以看到我们将关键字映射到数组中位置一般是整数好做映射计算如果不是整数就需要先将关键字转换为整数。1.2 除法散列法/除留余数法除法散列法也叫做除留余数法顾名思义假设哈希表的大小为M那么通过 key 除以M 的余数作为映射位置的下标也就是哈希函数为h(key) key % M。当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。为什么呢因为如果是这种值的话那么在利用上述哈希函数来计算的时候就相当于保留了 key 的后 X位那么后X位相同的值计算出的哈希值是一样的就容易冲突。因此我们要尽可能的让更多位参与运算这样就可以降低哈希冲突的概率。因此在使用除法散列时建议M取不太接近2的整数次幂的一个质数。1.3 乘法散列法乘法散列法对哈希表大小M没有要求第一步用关键字 k 乘上常数A0A1并抽取 k * A 的小数部分。第二步再用M乘以k * A的小数部分再向下取整。1.4 全域散列法如果存在一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中这种情况是存在的只要散列函数是公开且确定的就可以实现此攻击。所以为了解决这个问题就可以给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的一个散列函数来使用后续增删改查都固定使用这个散列函数否则每次哈希都是随机选取一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致找不到插入的 key 了。1.5 处理哈希冲突实践中哈希表一般还是选取除法散列法来作为哈希函数不管选用哪个哈希函数也避免不了哈希冲突那么我们应该如何解决哈希冲突呢有两种方法开放定址法和链地址法。.开放定址法开放定址法中所有的元素都放到哈希表里当一个关键字 key 用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置存储。这里的规则有三种线性探测二次探测双重探测。线性探测从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置。因为负载因子小于1所以最多探测M-1次一定能找到一个存储 key 的位置。线性探测比较简单如果 hash0 位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到 hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。二次探测可以一定程度改善这个问题。二次探测从发生冲突的位置开始依次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果往右走到哈希表尾则回绕到哈希表头的位置如果往左走到哈希表头则回绕到哈希表尾的位置。双重散列第一个哈希函数计算出的值发生冲突使用第二个哈希函数计算出一个跟 key 相关的偏移量的值不断往后探测直到寻找到下一个没有存储数据的位置为止。.key 不能取模的问题当 key 是 string/Date 等类型时key 不能取模那么我们需要给HashTable哈希表增加一个仿函数这个仿函数支持把 key 转换成一个可以取模的整形如果 key 可以转换成整型并且不容易冲突那么这个仿函数就用默认参数即可如果这个 key 不能转换成整型我们就需要自己实现一个仿函数传给这个参数。实现这个仿函数的要求就是尽量 key 的每个值都参与到计算中让不同的 key 转换出的整型值不同。.链地址法解决冲突的思路开放定址法中所有的元素都放到哈希表里链地址法中所有的数据不再直接存储在哈希表中哈希表中存储一个指针没有数据映射这个位置时这个指针为空有多个数据映射这个位置时我们把这些冲突的数据链接成一个链表挂在哈希表这个位置下面链地址法也叫做拉链法或者哈希桶。开放定址法负载因子必须小于1链地址法的负载因子就没有限制了可以大于1。为什么呢负载因子 N / MN代表哈希表中存储数据的个数M代表哈希表的大小在开放定址法中哈希表直接存储的就是数据所以为了避免频繁的哈希冲突我们不会将哈希表中全部填入数据所以负载因子小于1而链地址法中因为哈希冲突时会将多个数据以链表的形式存储在哈希表中所以哈希表中存储数据的个数是有可能大于哈希表的大小的所以负载因子可以大于1。如果极端场景下某个桶特别长怎么办可以考虑使用全域散列法这样就不容易被针对了。但是偶然情况下某个桶很长查找效率很低怎么办我们可以将链表转化为红黑树这样就可以提高查找时的效率了。不过在C中unordered_mapunordered_set在底层并没有采用红黑树来实现是用链地址法来实现的。二、链地址法代码实现.HashTable.h#pragmaonce#includeiostream#includevector#includeunordered_mapusingnamespacestd;staticconstint__stl_num_primes28;//数组//哈希这里用的素数表的目的是为了让数的更多比特位参与运算//从而降低哈希冲突因为素数无法被整除所有比特位都会参与运算//如果是2的整数幂较小或者是2的倍数参与运算的比特位就会很少//就会增加哈希冲突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};inlineunsignedlong__stl_next_prime(unsignedlongn){constunsignedlong*first__stl_prime_list;constunsignedlong*last__stl_prime_list__stl_num_primes;constunsignedlong*poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};//特化templatestructHashFuncstring{size_toperator()(conststringkey){size_t hashi0;for(constautoch:key){hashi*131;hashich;}returnhashi;}};enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classV,classHashHashFuncKclassHashTable{public://构造函数HashTable(size_t size__stl_next_prime(0)):_tables(size),_n(0){}boolInsert(constpairK,Vkv){//负载因子达到0.7就开始扩容if((double)_n/(double)_tables.size()0.7){//第一种方法//申请一块新空间遍历旧表重新映射//vectorHashDataK, V newtables(_tables.size() * 2);//for (size_t i 0; i _tables.size(); i)//{// if (_tables[i]._state EXIST)// {// size_t hash0 _tables[i]._kv.first % newtables.size();// //...// }//}//第二种方法//HashTableK, V newHT(_tables.size() * 2);HashTableK,VnewHT(__stl_next_prime(_tables.size()1));for(size_t i0;i_tables.size();i){if(_tables[i]._stateEXIST){newHT.Insert(_tables[i]._kv);}}//调用的是vector里面的swap函数_tables.swap(newHT._tables);//不需要//扩容是为了减少哈希冲突重新映射关系并没有增添新的数据//swap(_n, newHT._n);}Hash hs;//查找插入位置//取模操作符只能用于整数size_t hash0hs(kv.first)%_tables.size();size_t hashihash0;size_t i1;//线性探测while(_tables[hashi]._stateEXIST){hashi(hash0i)%_tables.size();i;}//说明该位置为空或者删除状态_tables[hashi]._kvkv;_tables[hashi]._stateEXIST;_n;returntrue;}HashDataK,V*Find(constKkey){Hash hs;size_t hash0hs(key)%_tables.size();size_t hashihash0;size_t i1;//线性查找//因为是线性探测所以key取模的位置有可能就是要查找key的位置//但也有可能因为该位置被其他元素所占据从而线性探测到其他位置//查找过程中如果遇到了EMPTY说明未找到对应的keywhile(_tables[hashi]._stateEXIST){if(_tables[hashi]._kv.firstkey){return_tables[hashi];}hashi(hash0i)%_tables.size();i;}returnnullptr;}boolErase(constKkey){HashDataK,V*htFind(key);if(ht){ht-_stateDELETE;returntrue;}returnfalse;}private:vectorHashDataK,V_tables;size_t _n;//表中存储数据的个数};.test.cpp#define_CRT_SECURE_NO_WARNINGS#includeHashTable.hvoidTestHT1(){inta[]{19,30,5,36,13,20,21,12};HashTableint,intht;for(autoe:a){ht.Insert({e,e});}for(size_t i0;i50;i){ht.Insert({rand(),1});}coutht.Find(-20)endl;coutht.Find(9)endl;ht.Erase(30);coutht.Find(20)endl;coutht.Find(9)endl;coutht.Find(30)endl;}structHashFuncString{size_toperator()(conststringkey){size_t hashi0;for(autoch:key){hashich;}returnhashi;}};structDate{int_year;int_month;int_day;};voidTestHT2(){//HashTablestring, string, HashFuncString dict;HashTablestring,stringdict;dict.Insert({sort,排序});dict.Insert({string,字符串});HashTabledouble,intht;ht.Insert({1.23,1});unordered_mapstring,stringstddict;stddict.insert({sort,排序});stddict.insert({string,字符串});//unordered_mapDate, string m2;}intmain(){//TestHT2();return0;}
哈希表的实现
一、哈希1.1 哈希的概念什么是哈希呢哈希又称散列是一种组织数据的方式。是一种通过哈希函数把关键字 key 跟存储位置建立一个映射关系查找时通过这个哈希函数计算出 key 存储的位置进行快速查找。.直接定址法当关键字的范围比较集中时就可以采用直接定址法。举个例子一组关键字都在[099]之间我们就可以开一个100个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[az]的小写字母那么我们就可以开一个26个数的数组每个关键字的 ascii码值就是存储位置的下标。直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。但是这种方式也有缺点那就是关键字的范围比较分散时就很浪费内存甚至内存不够用。所以这种方式也比较鸡肋。利用哈希函数来计算哈希值的这种方式有一个问题就是两个不同的 key 可能会映射到同一个位置去这个问题就叫做哈希冲突/哈希碰撞。理想情况下是找一个好的哈希函数来避免哈希冲突但哈希冲突是不可避免的。所以要尽可能的设计出优秀的哈希函数来减少冲突的次数。.负载因子假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子 N / M负载因子也可以叫做载荷因子/装载因子等。负载因子越大哈希冲突的概率越高空间利用率越高反之负载因子越小哈希冲突的概率越低空间利用率越低。为什么呢因为负载因子 N / M负载因子越大没说明N越大哈希表中存储的数据越多所以空间利用率越高哈希冲突概率越高。通过上述对于哈希的基础了解我们可以看到我们将关键字映射到数组中位置一般是整数好做映射计算如果不是整数就需要先将关键字转换为整数。1.2 除法散列法/除留余数法除法散列法也叫做除留余数法顾名思义假设哈希表的大小为M那么通过 key 除以M 的余数作为映射位置的下标也就是哈希函数为h(key) key % M。当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。为什么呢因为如果是这种值的话那么在利用上述哈希函数来计算的时候就相当于保留了 key 的后 X位那么后X位相同的值计算出的哈希值是一样的就容易冲突。因此我们要尽可能的让更多位参与运算这样就可以降低哈希冲突的概率。因此在使用除法散列时建议M取不太接近2的整数次幂的一个质数。1.3 乘法散列法乘法散列法对哈希表大小M没有要求第一步用关键字 k 乘上常数A0A1并抽取 k * A 的小数部分。第二步再用M乘以k * A的小数部分再向下取整。1.4 全域散列法如果存在一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中这种情况是存在的只要散列函数是公开且确定的就可以实现此攻击。所以为了解决这个问题就可以给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的一个散列函数来使用后续增删改查都固定使用这个散列函数否则每次哈希都是随机选取一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致找不到插入的 key 了。1.5 处理哈希冲突实践中哈希表一般还是选取除法散列法来作为哈希函数不管选用哪个哈希函数也避免不了哈希冲突那么我们应该如何解决哈希冲突呢有两种方法开放定址法和链地址法。.开放定址法开放定址法中所有的元素都放到哈希表里当一个关键字 key 用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置存储。这里的规则有三种线性探测二次探测双重探测。线性探测从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置。因为负载因子小于1所以最多探测M-1次一定能找到一个存储 key 的位置。线性探测比较简单如果 hash0 位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到 hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。二次探测可以一定程度改善这个问题。二次探测从发生冲突的位置开始依次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果往右走到哈希表尾则回绕到哈希表头的位置如果往左走到哈希表头则回绕到哈希表尾的位置。双重散列第一个哈希函数计算出的值发生冲突使用第二个哈希函数计算出一个跟 key 相关的偏移量的值不断往后探测直到寻找到下一个没有存储数据的位置为止。.key 不能取模的问题当 key 是 string/Date 等类型时key 不能取模那么我们需要给HashTable哈希表增加一个仿函数这个仿函数支持把 key 转换成一个可以取模的整形如果 key 可以转换成整型并且不容易冲突那么这个仿函数就用默认参数即可如果这个 key 不能转换成整型我们就需要自己实现一个仿函数传给这个参数。实现这个仿函数的要求就是尽量 key 的每个值都参与到计算中让不同的 key 转换出的整型值不同。.链地址法解决冲突的思路开放定址法中所有的元素都放到哈希表里链地址法中所有的数据不再直接存储在哈希表中哈希表中存储一个指针没有数据映射这个位置时这个指针为空有多个数据映射这个位置时我们把这些冲突的数据链接成一个链表挂在哈希表这个位置下面链地址法也叫做拉链法或者哈希桶。开放定址法负载因子必须小于1链地址法的负载因子就没有限制了可以大于1。为什么呢负载因子 N / MN代表哈希表中存储数据的个数M代表哈希表的大小在开放定址法中哈希表直接存储的就是数据所以为了避免频繁的哈希冲突我们不会将哈希表中全部填入数据所以负载因子小于1而链地址法中因为哈希冲突时会将多个数据以链表的形式存储在哈希表中所以哈希表中存储数据的个数是有可能大于哈希表的大小的所以负载因子可以大于1。如果极端场景下某个桶特别长怎么办可以考虑使用全域散列法这样就不容易被针对了。但是偶然情况下某个桶很长查找效率很低怎么办我们可以将链表转化为红黑树这样就可以提高查找时的效率了。不过在C中unordered_mapunordered_set在底层并没有采用红黑树来实现是用链地址法来实现的。二、链地址法代码实现.HashTable.h#pragmaonce#includeiostream#includevector#includeunordered_mapusingnamespacestd;staticconstint__stl_num_primes28;//数组//哈希这里用的素数表的目的是为了让数的更多比特位参与运算//从而降低哈希冲突因为素数无法被整除所有比特位都会参与运算//如果是2的整数幂较小或者是2的倍数参与运算的比特位就会很少//就会增加哈希冲突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};inlineunsignedlong__stl_next_prime(unsignedlongn){constunsignedlong*first__stl_prime_list;constunsignedlong*last__stl_prime_list__stl_num_primes;constunsignedlong*poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};//特化templatestructHashFuncstring{size_toperator()(conststringkey){size_t hashi0;for(constautoch:key){hashi*131;hashich;}returnhashi;}};enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classV,classHashHashFuncKclassHashTable{public://构造函数HashTable(size_t size__stl_next_prime(0)):_tables(size),_n(0){}boolInsert(constpairK,Vkv){//负载因子达到0.7就开始扩容if((double)_n/(double)_tables.size()0.7){//第一种方法//申请一块新空间遍历旧表重新映射//vectorHashDataK, V newtables(_tables.size() * 2);//for (size_t i 0; i _tables.size(); i)//{// if (_tables[i]._state EXIST)// {// size_t hash0 _tables[i]._kv.first % newtables.size();// //...// }//}//第二种方法//HashTableK, V newHT(_tables.size() * 2);HashTableK,VnewHT(__stl_next_prime(_tables.size()1));for(size_t i0;i_tables.size();i){if(_tables[i]._stateEXIST){newHT.Insert(_tables[i]._kv);}}//调用的是vector里面的swap函数_tables.swap(newHT._tables);//不需要//扩容是为了减少哈希冲突重新映射关系并没有增添新的数据//swap(_n, newHT._n);}Hash hs;//查找插入位置//取模操作符只能用于整数size_t hash0hs(kv.first)%_tables.size();size_t hashihash0;size_t i1;//线性探测while(_tables[hashi]._stateEXIST){hashi(hash0i)%_tables.size();i;}//说明该位置为空或者删除状态_tables[hashi]._kvkv;_tables[hashi]._stateEXIST;_n;returntrue;}HashDataK,V*Find(constKkey){Hash hs;size_t hash0hs(key)%_tables.size();size_t hashihash0;size_t i1;//线性查找//因为是线性探测所以key取模的位置有可能就是要查找key的位置//但也有可能因为该位置被其他元素所占据从而线性探测到其他位置//查找过程中如果遇到了EMPTY说明未找到对应的keywhile(_tables[hashi]._stateEXIST){if(_tables[hashi]._kv.firstkey){return_tables[hashi];}hashi(hash0i)%_tables.size();i;}returnnullptr;}boolErase(constKkey){HashDataK,V*htFind(key);if(ht){ht-_stateDELETE;returntrue;}returnfalse;}private:vectorHashDataK,V_tables;size_t _n;//表中存储数据的个数};.test.cpp#define_CRT_SECURE_NO_WARNINGS#includeHashTable.hvoidTestHT1(){inta[]{19,30,5,36,13,20,21,12};HashTableint,intht;for(autoe:a){ht.Insert({e,e});}for(size_t i0;i50;i){ht.Insert({rand(),1});}coutht.Find(-20)endl;coutht.Find(9)endl;ht.Erase(30);coutht.Find(20)endl;coutht.Find(9)endl;coutht.Find(30)endl;}structHashFuncString{size_toperator()(conststringkey){size_t hashi0;for(autoch:key){hashich;}returnhashi;}};structDate{int_year;int_month;int_day;};voidTestHT2(){//HashTablestring, string, HashFuncString dict;HashTablestring,stringdict;dict.Insert({sort,排序});dict.Insert({string,字符串});HashTabledouble,intht;ht.Insert({1.23,1});unordered_mapstring,stringstddict;stddict.insert({sort,排序});stddict.insert({string,字符串});//unordered_mapDate, string m2;}intmain(){//TestHT2();return0;}
