c++: 哈希表的实现 一、哈希的概念哈希(hash)⼜称散列是⼀种组织数据的⽅式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系查找时通过这个哈希函数计算出Key存储的位置进⾏快速查找。二、哈希的实现方法2.1直接定址法就是给出的范围是一个比较集中的范围时就可以用一个确定的数组去映射对应的关系比如下面这道题: 387:字符串中第一个唯一字符这道题的思路可以是直接定址法因为26个字母很集中并且范围小开销的空间也不大classSolution{public:intfirstUniqChar(string s){intcount[26]{0};for(autoch:s){count[ch-a];}for(inti0;is.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位是0011111131的⼆进制后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 % Mhc(key,i) hashi (hash0i) % M i {1,2,3,…,M −1};最多探测M-1次,但有负载因子的存在会在存一定量数据后进行扩容,所以几乎不可能达到最坏情况三、哈希表的具体实现(存pair的实现版)哈希表的基本框架enumstatus{EXIST,DELETE,EMPTY};templateclassK,classVstructHashData{pairK,V_kv;status _statusEMPTY;};templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};templatestructHashFuncstring{size_toperator()(conststringkey){size_t keyi0;for(autoe:key){keyie;keyi*131;}returnkeyi;}};templateclassK,classV,classHashHashFuncKclassHashTable{public:HashTable(){_table.resize(53);}inlineunsignedlong__stl_next_prime(unsignedlongn){// Note: assumes long is at least 32 bits.staticconstint__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;}private:vectorHashDataK,V_table;size_t n0;};首先:__stl_next_prime是M扩容的容量选择,这是源码库里面的值这些质数能更好的降低哈希冲突vector中为什么要存HashData不用pair值因为删除操作vector只能删尾部的值你想删任意值做不到所以需要用状态来代替删除并且查找的时候 ,也是以状态来查所以就用个类来存储pair值和该值的状态仿函数的实现就是:因为哈希表的建立实现要在key能转化为整数去能进行计算才可以所以面对字符串的储存需要将字符串转为整数然后通过哈希函数和线性探测来确定位置3.1insert的实现boolinsert(constpairK,Vkey){if(find(key.first)){returnfalse;}//扩容问题if((double)n/(double)_table.size()0.7){HashTableK,V,Hash_newtable;_newtable._table.resize(__stl_next_prime(_table.size()1));for(autoe:_table){if(e._statusEXIST){_newtable.insert(e._kv);}}_table.swap(_newtable._table);}Hash ha;size_t hash0ha(key.first)%_table.size();size_t hashihash0;inti1;while(_table[hashi]._statusEXIST){hashi(hash0i)%_table.size();i;}_table[hashi]._statusEXIST;_table[hashi]._kvkey;n;returntrue;}扩容逻辑就是走了个递归先将新扩容的哈希表将原来的旧的哈希表重新映射然后再通过swap来交换底层的指针达到扩容这里的M用size()不用capacity()的原因是:如果用capacity(来当M那映射出来的位置就超过了size那你哈希底层的数据结构是vector用[]取值的话是再size以内所以不行所以我们才在构造函数时手动给值尽量使size和capacity差不多-3.2find的实现HashDataK,V*find(constKkey){Hash ha;size_t hash0ha(key)%_table.size();size_t hashihash0;inti1;while(_table[hashi]._status!EMPTY){if(_table[hashi]._kv.firstkey_table[hashi]._status!DELETE){return_table[hashi];}hashi(hash0i)%_table.size();i;}returnnullptr;}这里就体现了用状态来标记是否存在就很好能体会到了3.3erase的实现boolerase(constKkey){autokeyifind(key);if(keyi){keyi-_statusDELETE;returntrue;}returnfalse;}四、代码的全部展示#pragmaonce#includeiostream#includevector#includestringusingnamespacestd;enumstatus{EXIST,DELETE,EMPTY};templateclassK,classVstructHashData{pairK,V_kv;status _statusEMPTY;};templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};templatestructHashFuncstring{size_toperator()(conststringkey){size_t keyi0;for(autoe:key){keyie;keyi*131;}returnkeyi;}};//开放性地址法:// 1. 除数留余法: key%M//2. 负载因子存储了N个值哈希表的⼤⼩为M那么负载因⼦ N/M//3.线性探测: 如果当前位置存在哈希冲突,那就线性走下一个位置直到没有哈希冲突templateclassK,classV,classHashHashFuncKclassHashTable{public:HashTable(){_table.resize(53);}inlineunsignedlong__stl_next_prime(unsignedlongn){// Note: assumes long is at least 32 bits.staticconstint__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,Vkey){if(find(key.first)){returnfalse;}//扩容问题if((double)n/(double)_table.size()0.7){HashTableK,V,Hash_newtable;_newtable._table.resize(__stl_next_prime(_table.size()1));for(autoe:_table){if(e._statusEXIST){_newtable.insert(e._kv);}}_table.swap(_newtable._table);}Hash ha;size_t hash0ha(key.first)%_table.size();size_t hashihash0;inti1;while(_table[hashi]._statusEXIST){hashi(hash0i)%_table.size();i;}_table[hashi]._statusEXIST;_table[hashi]._kvkey;n;returntrue;}HashDataK,V*find(constKkey){Hash ha;size_t hash0ha(key)%_table.size();size_t hashihash0;inti1;while(_table[hashi]._status!EMPTY){if(_table[hashi]._kv.firstkey_table[hashi]._status!DELETE){return_table[hashi];}hashi(hash0i)%_table.size();i;}returnnullptr;}boolerase(constKkey){autokeyifind(key);if(keyi){keyi-_statusDELETE;returntrue;}returnfalse;}private:vectorHashDataK,V_table;size_t n0;};