c++: 哈希表的实现-平芜编程栈

一、哈希的概念

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

二、哈希的实现方法

2.1直接定址法

就是给出的范围是一个比较集中的范围时，就可以用一个确定的数组去映射对应的关系，比如下面这道题: 387:字符串中第一个唯一字符
这道题的思路可以是直接定址法，因为26个字母很集中并且范围小，开销的空间也不大

classSolution{public:intfirstUniqChar(string s){intcount[26]={0};for(autoch:s){count[ch-'a']++;}for(inti=0;i<s.size();++i){if(count[s[i]]==1){returni;}}return-1;}

2.2开放定址法

我们可知当一些数据不集中时，映射到数组的对应下标的空间开销很大。就可能导致栈溢出并且很浪费内存,所以要解决这个难题需要以下的方法

2.2.1哈希函数

⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个⽅向去考量设计。

2.2.2除法散列法/除留余数法

简单来说，有N个数据，哈希表的空间为M,就是把当前数据(key)要通过Key%M的方式，把Key映射到M以内的空间中,但这也会面临一个问题，就是可能多个值是映射到同一个空间中，这就是哈希冲突

2.2.3解决哈希冲突

1.当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是，那么key%本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，也就是2^4 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是00111111，31的⼆进制后8位是00011111。如果是10^X，就更明显了，保留的都是10进值的后x位，如：{112,12312}，如果M是100，也就是，那么计算出的哈希值都12
,所以，当使⽤除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。但再怎么样哈希冲突都是不可避免的，只能通过这样的方式尽可能的减少哈希冲突

2.2.4负载因子

假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么负载因⼦=N/M，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为loadfactor。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；

2.2.5开放定址法的实现思路

有了前面的知识铺垫，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于1的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。这里主要讲的实现方法是线性探测

2.2.6 线性探测

如果通过哈希函数算出来的空间已经存在，也就是这个值会发生哈希冲突，那就从哈希冲突的位置的下一个位置进行探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。
所以公式为:
h(key) = hash0 = key % M
hc(key,i) = hashi = (hash0+i) % M， i = {1,2,3,…,M −1};最多探测M-1次,但有负载因子的存在，会在存一定量数据后进行扩容,所以几乎不可能达到最坏情况

三、哈希表的具体实现(存pair的实现版)

哈希表的基本框架

enumstatus{EXIST,DELETE,EMPTY};template<classK,classV>structHashData{pair<K,V>_kv;status _status=EMPTY;};template<classK>structHashFunc{size_toperator()(constK&key){return(size_t)key;}};template<>structHashFunc<string>{size_toperator()(conststring&key){size_t keyi=0;for(autoe:key){keyi+=e;keyi*=131;}returnkeyi;}};template<classK,classV,classHash=HashFunc<K>>classHashTable{public:HashTable(){_table.resize(53);}inlineunsignedlong__stl_next_prime(unsignedlongn){// Note: assumes long is at least 32 bits.staticconstint__stl_num_primes=28;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*pos=lower_bound(first,last,n);returnpos==last?*(last-1):*pos;}private:vector<HashData<K,V>>_table;size_t n=0;};

首先:__stl_next_prime是M扩容的容量选择,这是源码库里面的值，这些质数能更好的降低哈希冲突，vector中为什么要存HashData，不用pair值，因为删除操作vector只能删尾部的值，你想删任意值做不到，所以需要用状态来代替删除，并且查找的时候 ,也是以状态来查所以就用个类来存储pair值和该值的状态
仿函数的实现就是:因为哈希表的建立实现要在key能转化为整数去能进行计算才可以，所以面对字符串的储存需要将字符串转为整数，然后通过哈希函数和线性探测来确定位置

3.1insert的实现

boolinsert(constpair<K,V>&key){if(find(key.first)){returnfalse;}//扩容问题if((double)n/(double)_table.size()>0.7){HashTable<K,V,Hash>_newtable;_newtable._table.resize(__stl_next_prime(_table.size()+1));for(autoe:_table){if(e._status==EXIST){_newtable.insert(e._kv);}}_table.swap(_newtable._table);}Hash ha;size_t hash0=ha(key.first)%_table.size();size_t hashi=hash0;inti=1;while(_table[hashi]._status==EXIST){hashi=(hash0+i)%_table.size();++i;}_table[hashi]._status=EXIST;_table[hashi]._kv=key;++n;returntrue;}

扩容逻辑就是走了个递归先将新扩容的哈希表将原来的旧的哈希表重新映射，然后再通过swap来交换底层的指针达到扩容
这里的M用size()，不用capacity()的原因是:如果用capacity(来当M那映射出来的位置就超过了size，那你哈希底层的数据结构是vector，用[]取值的话是再size以内，所以不行，所以我们才在构造函数时手动给值，尽量使size和capacity差不多-

3.2find的实现

HashData<K,V>*find(constK&key){Hash ha;size_t hash0=ha(key)%_table.size();size_t hashi=hash0;inti=1;while(_table[hashi]._status!=EMPTY){if(_table[hashi]._kv.first==key&&_table[hashi]._status!=DELETE){return&_table[hashi];}hashi=(hash0+i)%_table.size();++i;}returnnullptr;}

这里就体现了用状态来标记是否存在就很好能体会到了

3.3erase的实现

boolerase(constK&key){autokeyi=find(key);if(keyi){keyi->_status=DELETE;returntrue;}returnfalse;}

四、代码的全部展示

#pragmaonce#include<iostream>#include<vector>#include<string>usingnamespacestd;enumstatus{EXIST,DELETE,EMPTY};template<classK,classV>structHashData{pair<K,V>_kv;status _status=EMPTY;};template<classK>structHashFunc{size_toperator()(constK&key){return(size_t)key;}};template<>structHashFunc<string>{size_toperator()(conststring&key){size_t keyi=0;for(autoe:key){keyi+=e;keyi*=131;}returnkeyi;}};//开放性地址法:// 1. 除数留余法: key%M//2. 负载因子：存储了N个值，哈希表的⼤⼩为M，那么负载因⼦= N/M//3.线性探测: 如果当前位置存在哈希冲突,那就线性走下一个位置直到没有哈希冲突template<classK,classV,classHash=HashFunc<K>>classHashTable{public:HashTable(){_table.resize(53);}inlineunsignedlong__stl_next_prime(unsignedlongn){// Note: assumes long is at least 32 bits.staticconstint__stl_num_primes=28;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*pos=lower_bound(first,last,n);returnpos==last?*(last-1):*pos;}boolinsert(constpair<K,V>&key){if(find(key.first)){returnfalse;}//扩容问题if((double)n/(double)_table.size()>0.7){HashTable<K,V,Hash>_newtable;_newtable._table.resize(__stl_next_prime(_table.size()+1));for(autoe:_table){if(e._status==EXIST){_newtable.insert(e._kv);}}_table.swap(_newtable._table);}Hash ha;size_t hash0=ha(key.first)%_table.size();size_t hashi=hash0;inti=1;while(_table[hashi]._status==EXIST){hashi=(hash0+i)%_table.size();++i;}_table[hashi]._status=EXIST;_table[hashi]._kv=key;++n;returntrue;}HashData<K,V>*find(constK&key){Hash ha;size_t hash0=ha(key)%_table.size();size_t hashi=hash0;inti=1;while(_table[hashi]._status!=EMPTY){if(_table[hashi]._kv.first==key&&_table[hashi]._status!=DELETE){return&_table[hashi];}hashi=(hash0+i)%_table.size();++i;}returnnullptr;}boolerase(constK&key){autokeyi=find(key);if(keyi){keyi->_status=DELETE;returntrue;}returnfalse;}private:vector<HashData<K,V>>_table;size_t n=0;};