C++:哈希表

文章目录1. 哈希的概念1.1 直接定址法1.2 哈希冲突1.3 负载因子1.4 将关键字转为整数1.5 哈希函数1.5.1 除法散列法/除留余数法1.6 处理哈希冲突1.6.1 开放地址法1.6.2 开放地址法实现1.6.3 扩容1.6.4 实现字符串储存1.6.5 链地址法1.6.6 两种方法代码实现1. 哈希的概念哈希 (hash) 又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系查找时通过这个哈希函数计算出 Key 存储的位置进行快速查找。1.1 直接定址法直接定址法是最基础的哈希函数实现方式核心逻辑是用关键字本身或对关键字做简单的线性运算比如加减一个固定偏移量直接算出数组下标建立关键字和存储位置的一一映射。它的特点是完全没有哈希冲突、访问效率极高但仅适用于关键字取值范围连续且集中的场景不适合范围大、分布零散的数据。例比如一组关键字都在 [0,99] 之间那么我们开一个 100 个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母那么我们开一个 26 个数的数组每个关键字 ASCII 码 - a 的 ASCII 码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。#includestdio.hintmain(){// 关键字范围0~99数组长度设为100intcount[100]{0};intnums[]{5,12,5,37,12,5,99};intnsizeof(nums)/sizeof(nums[0]);// 直接定址法Key直接作为下标for(inti0;in;i){intkeynums[i];count[key];}// 输出结果printf(数字出现次数\n);for(inti0;i100;i){if(count[i]0){printf(%d: %d次\n,i,count[i]);}}return0;}1.2 哈希冲突直接定址法的缺点也非常明显当关键字的范围比较分散时就很浪费内存甚至内存不够用。假设我们只有数据范围是[0,9999]的N个值我们要映射到一个M个空间的数组中(一般情况下M N)那么就要借助哈希函数(hash function)hf关键字key被放到数组的h(key)位置这里要注意的是h(key)计算出的值必须在[0, M)之间。这里存在的一个问题就是两个不同的key可能会映射到同一个位置去这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以我们尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的方案。1.3 负载因子假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子 N / M负载因子有些地方也翻译为载荷因子/装载因子等它的英文为load factor。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低1.4 将关键字转为整数我们将关键字映射到数组中位置一般是整数好做映射计算如果不是整数我们要想办法转换成整数这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时如果关键字不是整数那么我们讨论的Key是关键字转换成的整数。1.5 哈希函数一个好的哈希函数应该让N个关键字被等概率地均匀地散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个方向去考量设计。1.5.1 除法散列法/除留余数法除法散列法又称除留余数法是最经典、最常用的哈希函数构造方法。其核心公式为h ( k e y ) k e y % M h(key) key \% Mh(key)key%M其中k e y keykey待映射的关键字需为整数M MM哈希表的长度h ( k e y ) h(key)h(key)关键字在哈希表中的映射下标范围[ 0 , M − 1 ] [0, M-1][0,M−1]M MM的取值禁忌应避免将M MM设为2 x 2^x2x2的幂或10 x 10^x10x10的幂若M 2 x M2^xM2x取模运算等价于只保留k e y keykey的低x xx位高位信息丢失容易因低x xx位相同导致冲突。例如M 16 ( 2 4 ) M16(2^4)M16(24)时63 ( 00111111 ) 63(00111111)63(00111111)和31 ( 00011111 ) 31(00011111)31(00011111)的低4位均为1111哈希值均为15。若M 10 x M10^xM10x则仅保留k e y keykey的低x xx位十进制数字同样容易因低位重复引发冲突。例如M 100 ( 10 2 ) M100(10^2)M100(102)时112 112112和12312 1231212312的低2位均为12哈希值均为12。推荐取值多数数据结构教材建议将M MM取为不太接近2的整数次幂的质数能显著降低冲突概率。#includestdio.h// 除留余数法哈希函数inthash(intkey,inttable_size){returnkey%table_size;}intmain(){inttable_size13;// 选用质数降低冲突概率intkeys[]{10,23,36,49,62};intnsizeof(keys)/sizeof(keys[0]);for(inti0;in;i){intidxhash(keys[i],table_size);printf(key %d → 下标 %d\n,keys[i],idx);}return0;}1.6 处理哈希冲突这里我们说两种方法开放定址法链地址法1.6.1 开放地址法这里给张图展示这里的探测主要有三种线性探测二次探测双重探测1.6.2 开放地址法实现先给个哈希表结构enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassK,classVclassHashTable{private:vectorHashDataK,V_tables;size_t _n0;// 表中存储数据个数};这里给_tables加了个State状态。便于增删查改。1.6.3 扩容扩容先给个函数inlineunsignedlong__stl_next_prime(unsignedlongn){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;}这是 SGI STL 哈希表配套的获取下一个质数函数。哈希表扩容要求容量为质数减少哈希冲突此函数专门用来获取大于等于当前容量的最小质数替代简单的 2 倍扩容。哈希表负载因子达到 0.7 触发扩容时调用该函数拿到新质数容量再将旧表数据重新哈希映射到新表保证哈希表容量始终为质数降低冲突概率。为什么取质数哈希表容量选择质数是因为除留余数法中合数容量容易与关键字产生公因数导致哈希结果扎堆、冲突增多、分布不均而质数仅有1和自身两个因数能最大程度避免关键字集中映射让哈希下标均匀分布从而大幅减少哈希冲突。1.6.4 实现字符串储存#includestring#includevectorusingnamespacestd;templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};// 字符串哈希函数特化BKDR哈希templatestructHashFuncstring{size_toperator()(conststringkey){size_t hash0;for(autoe:key){hash*131;//BKDR哈希感兴趣可以去看看hashe;}returnhash;}};templateclassK,classV,classHashHashFuncKclassHashTable{private:vectorHashDataK,V_tables;size_t _n0;// 表中存储数据个数};字符串、日期等非整型类型无法直接取模因此引入哈希仿函数统一将关键字转为整型默认仿函数直接转换整型关键字针对字符串做模板特化采用 BKDR 哈希算法让每个字符都参与运算降低哈希冲突。核心要点简释普通整型key使用默认仿函数直接强转为size_t参与取模。字符串key不能简单累加ASCII码易冲突改用BKDR哈希通过乘以质数131叠加字符值让不同字符串尽量生成不同整型哈希值。哈希表模板增加哈希仿函数模板参数支持不同类型key自定义哈希规则。1.6.5 链地址法先看图扩容开放定址法负载因子必须小于 1链地址法的负载因子就没有限制了可以大于 1。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低STL 中unordered_xxx的最大负载因子基本控制在 1大于 1 就扩容我们下面实现也使用这个方式。1.6.6 两种方法代码实现#pragmaonce#includeHashTable.h#includevector#includestring#includealgorithmusingnamespacestd;enumState{EXIST,EMPTY,DELETE};templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};templatestructHashFuncstring{size_toperator()(conststrings){size_t hash0;for(autoch:s){hashch;hash*131;}returnhash;}};inlineunsignedlong__stl_next_prime(unsignedlongn){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;}//开放地址法namespaceopen_address{templateclassK,classV,classHashHashFuncKclassHashTable{private:vectorHashDataK,V_tables;size_t _n;public:HashTable():_tables(__stl_next_prime(0)),_n(0){}boolInsert(constpairK,Vkv){if(Find(kv.first))returnfalse;if(_n*10/_tables.size()7){HashTableK,V,Hashnewht;newht._tables.resize(__stl_next_prime(_tables.size()1));for(autodata:_tables){if(data._stateEXIST)newht.Insert(data._kv);}_tables.swap(newht._tables);}Hash hash;size_t hash0hash(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 hash;size_t hash0hash(key)%_tables.size();size_t hashihash0;size_t i1;while(_tables[hashi]._state!EMPTY){if(_tables[hashi]._stateEXIST_tables[hashi]._kv.firstkey){return_tables[hashi];}hashi(hash0i)%_tables.size();i;}returnnullptr;}boolErase(constKkey){HashDataK,V*retFind(key);if(ret){ret-_stateDELETE;returntrue;}returnfalse;}};}//链地址法namespacehash_bucket{templateclassK,classVstructHashNode{pairK,V_kv;HashNodeK,V*_next;HashNode(constpairK,Vkv):_kv(kv),_next(nullptr){}};templateclassK,classV,classHashHashFuncKclassHashTable{typedefHashNodeK,VNode;public:HashTable():_tables(11),_n(0){}boolInsert(constpairK,Vkv){if(_n_tables.size()){vectorNode*newTable(_tables.size()*2);for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;size_t hashicur-_kv.first%newTable.size();cur-_nextnewTable[hashi];newTable[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newTable);}size_t hashikv.first%_tables.size();Node*newnodenewNode(kv);newnode-_next_tables[hashi];_tables[hashi]newnode;_n;returntrue;}private:vectorNode*_tables;size_t _n;};}