手撕哈希表（Hash Table）：从原理到C++完整实现

手撕哈希表Hash Table从原理到C完整实现哈希表作为O(1)级别查找的数据结构是面试与工程开发中的高频考点。本文从哈希核心概念讲起深入哈希函数、哈希冲突、两种冲突解决方案并提供可直接运行的C完整代码带你彻底吃透哈希表。文章目录手撕哈希表Hash Table从原理到C完整实现一、哈希表核心概念1.1 什么是哈希1.2 直接定址法1.3 哈希冲突1.4 负载因子1.5 关键字转整数二、哈希函数设计2.1 除法散列法最常用2.2 乘法散列法2.3 全域散列法三、哈希冲突解决方案3.1 开放定址法3.1.1 线性探测3.1.2 二次探测3.1.3 双重散列3.2 链地址法哈希桶工程首选四、C完整实现4.1 通用哈希仿函数4.2 开放定址法线性探测完整代码4.3 链地址法哈希桶完整代码五、测试代码六、总结一、哈希表核心概念1.1 什么是哈希哈希Hash又称散列通过哈希函数建立关键字Key与存储位置的映射关系实现数据的快速插入、查找、删除理想时间复杂度为O(1)。1.2 直接定址法关键字范围集中时的极简哈希方式关键字为[0,99]整数直接用关键字作为数组下标关键字为小写字母下标 字符ASCII码 - a的ASCII码示例LeetCode 387. 字符串中的第一个唯一字符classSolution{public:intfirstUniqChar(string s){// 用字母相对ASCII码作为下标统计字符出现次数intcount[26]{0};for(autoch:s){count[ch-a];}// 遍历找第一个出现一次的字符for(size_t i0;is.size();i){if(count[s[i]-a]1){returni;}}return-1;}};1.3 哈希冲突不同关键字通过哈希函数计算出相同存储位置称为哈希冲突哈希碰撞。冲突无法完全避免只能通过优秀哈希函数减少冲突并设计冲突解决方案。1.4 负载因子负载因子 哈希表中元素个数 / 哈希表大小负载因子越大冲突概率越高空间利用率越高负载因子越小冲突概率越低空间利用率越低1.5 关键字转整数非整数类型如string、自定义类型需先转为整数再进行哈希计算。二、哈希函数设计哈希函数核心目标让关键字均匀散列到哈希表中减少冲突。2.1 除法散列法最常用公式h(key) key % MM为哈希表大小建议M取不接近2的整数次幂的质数避免后几位固定导致大量冲突Java HashMap优化M取2的整数次幂用位运算替代取模同时让key所有位参与计算2.2 乘法散列法公式h(key) floor(M × ((A × key) % 1.0))A取黄金分割比(√5-1)/2 ≈ 0.618对表大小M无要求2.3 全域散列法随机选择哈希函数防止恶意构造数据导致极端冲突公式h_ab(key) ((a × key b) % P) % MP为大质数a∈[1,P-1]b∈[0,P-1]三、哈希冲突解决方案3.1 开放定址法所有元素存储在哈希表数组中冲突时按规则寻找空位置负载因子必须1。3.1.1 线性探测冲突后依次向后探测公式hashi (hash0 i) % Mi1,2,3…优点实现简单缺点易产生数据堆积查找效率下降3.1.2 二次探测冲突后按平方数跳跃探测公式hashi (hash0 ± i²) % M优点缓解线性探测的堆积问题3.1.3 双重散列用第二个哈希函数计算偏移量公式hashi (hash0 i × h2(key)) % M要求h2(key)与M互质保证遍历全表3.2 链地址法哈希桶工程首选哈希表存储链表指针冲突元素挂在对应位置的链表上负载因子可1。优点无堆积问题实现简单效率稳定Java8 HashMap优化链表长度8转为红黑树进一步提升效率四、C完整实现4.1 通用哈希仿函数支持int、string等类型转整数string采用BKDR哈希减少冲突// 通用哈希仿函数templateclassKstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};// string特化BKDR哈希templatestructHashFuncstring{size_toperator()(conststringkey){size_t hash0;for(autoch:key){hashhash*131ch;// 131为优质质数}returnhash;}};// SGI STL质数表扩容用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;}4.2 开放定址法线性探测完整代码namespaceopen_address{// 节点状态存在/空/已删除enumState{EXIST,EMPTY,DELETE};// 哈希节点templateclassK,classVstructHashData{pairK,V_kv;State _stateEMPTY;};// 开放定址哈希表templateclassK,classV,classHashHashFuncKclassHashTable{public:HashTable(){_tables.resize(__stl_next_prime(0));}// 插入boolInsert(constpairK,Vkv){if(Find(kv.first)){returnfalse;}// 负载因子0.7扩容if(_n*10/_tables.size()7){HashTableK,V,HashnewHT;newHT._tables.resize(__stl_next_prime(_tables.size()1));// 旧数据重新映射到新表for(size_t i0;i_tables.size();i){if(_tables[i]._stateEXIST){newHT.Insert(_tables[i]._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;// 遇到EMPTY停止查找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(retnullptr){returnfalse;}ret-_stateDELETE;--_n;returntrue;}private:vectorHashDataK,V_tables;size_t _n0;// 有效元素个数};}4.3 链地址法哈希桶完整代码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.resize(__stl_next_prime(0),nullptr);}// 析构释放所有节点~HashTable(){for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;deletecur;curnext;}_tables[i]nullptr;}}// 插入头插boolInsert(constpairK,Vkv){if(Find(kv.first)){returnfalse;}Hash hs;size_t hashihs(kv.first)%_tables.size();// 负载因子1扩容if(_n_tables.size()){vectorNode*newTables(__stl_next_prime(_tables.size()1),nullptr);// 旧节点直接移动到新表高效for(size_t i0;i_tables.size();i){Node*cur_tables[i];while(cur){Node*nextcur-_next;// 重新计算哈希位置size_t newHashhs(cur-_kv.first)%newTables.size();// 头插新表cur-_nextnewTables[newHash];newTables[newHash]cur;curnext;}_tables[i]nullptr;}_tables.swap(newTables);// 重新计算插入位置hashihs(kv.first)%_tables.size();}// 头插法插入新节点Node*newNodenewNode(kv);newNode-_next_tables[hashi];_tables[hashi]newNode;_n;returntrue;}// 查找Node*Find(constKkey){Hash hs;size_t hashihs(key)%_tables.size();Node*cur_tables[hashi];// 遍历对应链表while(cur){if(cur-_kv.firstkey){returncur;}curcur-_next;}returnnullptr;}// 删除boolErase(constKkey){Hash hs;size_t hashihs(key)%_tables.size();Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(cur-_kv.firstkey){// 头节点删除if(prevnullptr){_tables[hashi]cur-_next;}else{// 中间/尾节点删除prev-_nextcur-_next;}deletecur;--_n;returntrue;}prevcur;curcur-_next;}returnfalse;}private:vectorNode*_tables;// 指针数组哈希桶size_t _n0;// 有效元素个数};}五、测试代码intmain(){// 测试链地址法哈希表hash_bucket::HashTableint,stringht;ht.Insert(make_pair(1,one));ht.Insert(make_pair(2,two));ht.Insert(make_pair(3,three));// 查找测试autonodeht.Find(2);if(node){coutkey:2 value:node-_kv.secondendl;}// 删除测试ht.Erase(2);nodeht.Find(2);if(!node){coutkey:2 删除成功endl;}// 测试string类型hash_bucket::HashTablestring,intstrHT;strHT.Insert(make_pair(hash,100));strHT.Insert(make_pair(table,200));autostrNodestrHT.Find(hash);if(strNode){coutkey:hash value:strNode-_kv.secondendl;}return0;}六、总结哈希表核心哈希函数冲突解决目标O(1)查找哈希函数除法散列法最常用string推荐BKDR哈希冲突解决开放定址法实现简单易堆积负载因子1链地址法工程首选无堆积支持负载因子1扩容哈希表大小取质数负载因子达到阈值自动扩容本文实现的哈希表可直接用于学习与面试理解原理后可轻松掌握unordered_map/unordered_set底层逻辑。