资讯详情

深入了解 · 专业解读

哈希表实现

发布时间：2026/9/3 7:02:26
哈希表实现 目录一. 哈希概念1.1 直接定址法1.1.1 概念1.1.2 题目示例387. 字符串中的第一个唯一字符 - 力扣LeetCode二. 哈希的一些概念2.1 哈希冲突2.2 负载因子2.3 将关键字转为整数2.4 哈希函数2.4.1 除法散列法 / 除留余数法2.4.2 乘法散列法2.4.3 全域散列法三. 处理哈希冲突3.1 开放定址法3.1.1 线性探测3.1.2 二次探测法3.1.3 双重散列3.2 开放定址法的实现3.2.1 key不能取模问题3.2.2 key 能否比较相等的问题3.2.3 扩容问题3.2.4 代码实现3.3 链定址法3.3.1 扩容问题3.3.1.1 极端情况3.3.2 代码实现一. 哈希概念哈希(hash)又称散列故哈希表又称散列表是一种组织数据的方式。哈希是音译名从译名来看有散乱排列散列的意思。哈希的本质就是通过哈希函数把关键字Key跟存储位置建立一个映射关系查找时通过这个哈希函数计算出Key存储的位置进行快速查找。1.1 直接定址法1.1.1 概念当关键字的范围比较集中时直接定址法是非常简单高效的方法比如一组关键字都在[099]之间那么我们开一个100个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母那么我们开一个26个数的数组每个关键字acsii码-aascii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们不仅在计数排序部分用过在string部分的OJ题目那里也用过了.1.1.2 题目示例387. 字符串中的第一个唯一字符 - 力扣LeetCodeclass Solution { public: int firstUniqChar(string s) { // 每个字⺟的ascii码-a的ascii码作为下标映射到count数组数组中存储出现的次数 int count[26] { 0 }; // 统计次数 for (auto ch : s) { count[ch - a]; } for (size_t i 0; i s.size(); i) { if (count[s[i] - a] 1) return i; } return -1; } };二. 哈希的一些概念2.1 哈希冲突直接定址法的缺点也非常明显当关键字的范围比较分散时就很浪费内存甚至内存不够用。假设我们只有数据范围是[09999]的N个值我们要映射到一个M个空间的数组中一般情况下M N那么就要借助哈希函数(hash function)hf关键字key被放到数组的h(key)位置这里要注意的是h(key)计算出的值必须在[O , M)之间。这里存在的一个问题就是两个不同的key可能会映射到同一个位置去这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以我们尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的方案。2.2 负载因子假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子 N / M负载因子有些地方也翻译为载荷因子/装载因子等他的英文为loadfactor。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低。2.3 将关键字转为整数我们将关键字映射到数组中位置一般是整数好做映射计算如果不是整数我们要想办法转换成整数这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时如果关键字不是整数那么我们讨论的Key是关键字转换成的整数。2.4 哈希函数好的哈希函数能让 key 均匀分布减少冲突常用设计方法如下2.4.1 除法散列法 / 除留余数法1、除法散列法也叫做除留余数法顾名思义假设哈希表的大小为M那么通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key) key % M。2、当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是2^Xkey % 2^X本质相当于保留key的后X位后X位相同的值计算出的哈希值都是一样的——就冲突了。比如[6331}看起来没有关联的值如果M是16也就是2^4那么计算出的哈希值都是15因为63的二进制后8位是0011111131的二进制后8位是00011111。如果是10^x就更明显了保留的都是10进值的后X位如[112,12312}如果M是100(10^2)计算出的哈希值都是12。3、当使用除法散列法时建议M取不太接近2的整数次幂的一个质数素数2.4.2 乘法散列法乘法散列法对哈希表大小M没有要求这里介绍一下大思路第一步用关键字K乘上常数A0 A 1)并抽取出k*A的小数部分第二步后再用M乘以k * A的小数部分再向下取整。h(key) floor(M * ((A * key) % 1.0))其中floor表示对表达式进行下取整A(0 , 1)%1.0是为了取小数这里最重要的是A的值应该如何设定Knuth——这又是一位大佬——他认为A (5 - 1) / 2 0.6180339887...黄金分割点)比较好。乘法散列法对哈希表大小M是没有要求的假设M为1024key为1234A 0.6180339887A * key 762.6539420558取小数部分为0.6539420558,M * ((A * key) % 1.0) 0.6539420558*1024 669.6366651392那么h(1234) 669。2.4.3 全域散列法如果存在这样一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中——这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决方法自然是见招拆招给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。hab(key) ((a * key 6) % P) % MP需要选一个足够大的质数a可以随机选[1 , P - 1]之间的任意整数b可以随机选[0 , P - 1]之间的任意整数这些函数构成了一个P * (P - 1)组全域散列函数组。假设P 17M 6a 3b 4,则h34(8) ((3 * 8 4) % 17) % 6 5。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的一个散列函数使用后续增删查改都固定使用这个散列函数否则每次哈希都是随机选一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致找不到插入的key了。三. 处理哈希冲突实践中哈希表一般还是选择除法散列法作为哈希函数当然哈希表无论选择什么哈希函数也避免不了冲突因为冲突是避免不了的我们只能减少冲突那么插入数据时如何解决冲突呢主要有两种方法开放定址法和链地址法。3.1 开放定址法在开放定址法中所有的元素都放到哈希表里当一个关键字key用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于的。这里的规则有三种线性探测、二次探测、双重探测。3.1.1 线性探测enum state { EXIST, EMPTY, DELETE }; templateclass K, class V class HashData { public: pairK, V _kv; state _state EMPTY; }; templateclass K,class V class HashTable { public: HashTable() :_tables(11) ,_n(0) {} bool insert(const pairK, V kv) { if (find(kv.first)) { return false; } //负载因子 0.7 扩容 if (_n * 1.0 / _tables.size() 0.7) { HashTableK, V newht; newht._tables.resize(_tables.size() * 2); for (auto data : _tables) { if (data._state EXIST) { newht.insert(data._kv); } } _tables.swap(newht._tables); } size_t hash0 kv.first % _tables.size(); size_t hashi hash0; size_t i 1; while (_tables[hashi]._state EXIST) { hashi (hash0 i) % _tables.size(); i; } _tables[hashi]._kv kv; _tables[hashi]._state EXIST; _n; return true; } HashDataK, V* find(const K key) { size_t hash0 key % _tables.size(); size_t hashi hash0; size_t i 1; while (_tables[hashi]._state ! EMPTY) { if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key) { return _tables[hashi]; } hashi (hash0 i) % _tables.size(); i; } return nullptr; } bool erase(const K key) { HashDataK, V* ret find(key); if (ret) { ret-_state DELETE; _n--; return true; } return false; } private: vectorHashDataK, V _tables; size_t _n; };3.1.2 二次探测法enum state { EXIST, EMPTY, DELETE }; templateclass K, class V class HashData { public: pairK, V _kv; state _state EMPTY; }; templateclass K,class V class HashTable { public: HashTable() :_tables(11) ,_n(0) {} bool insert(const pairK, V kv) { if (find(kv.first)) { return false; } //负载因子 0.7 扩容 if (_n * 1.0 / _tables.size() 0.7) { HashTableK, V newht; newht._tables.resize(_tables.size() * 2); for (auto data : _tables) { if (data._state EXIST) { newht.insert(data._kv); } } _tables.swap(newht._tables); } size_t hash0 kv.first % _tables.size(); int hashi hash0; size_t i 1; int flag 1; while (_tables[hashi]._state EXIST) { hashi (hash0 i*i*flag) % _tables.size(); if (hashi 0) { hashi _tables.size(); } if (flag 1) { flag -1; } else { flag 1; i; } } _tables[hashi]._kv kv; _tables[hashi]._state EXIST; _n; return true; } HashDataK, V* find(const K key) { size_t hash0 key % _tables.size(); int hashi hash0; size_t i 1; int flag 1; while (_tables[hashi]._state ! EMPTY) { if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key) { return _tables[hashi]; } hashi (hash0 i*i*flag) % _tables.size(); if (hashi 0) { hashi _tables.size(); } if (flag 1) { flag -1; } else { flag 1; i: } } return nullptr; } bool erase(const K key) { HashDataK, V* ret find(key); if (ret) { ret-_state DELETE; _n--; return true; } return false; } private: vectorHashDataK, V _tables; size_t _n; };3.1.3 双重散列3.2 开放定址法的实现3.2.1 key不能取模问题当key是string / Date等类型时key不能取模我们需要给HashTable增加一个仿函数这个仿函数支持把key转换成一个可以取模的整型如果key可以转换为整型并且不容易冲突那么这个仿函数就用默认参数即可如果这个Key不能转换为整型我们就需要自己实现一个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每值都参与到计算中让不同的key转换出的整型值不同。string做哈希表的key非常常见所以我们可以考虑把string特化一下——templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; // 特化 template struct HashFuncstring { // 字符串转换成整形可以把字符ascii码相加即可 // 但是直接相加的话类似abcd和bcad这样的字符串计算出是相同的 // 这里我们使⽤BKDR哈希的思路⽤上次的计算结果去乘以一个质数这个质数一般取31, 131等效果会比较好 size_t operator()(const string key) { size_t hash 0; for (auto e : key) { hash * 131; hash e; } return hash; } }; templateclass K, class V, class Hash HashFuncK class HashTable { public: private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 };3.2.2 key 能否比较相等的问题当 key 为Date等类型时我们可能面临比较相等的问题我们既可以在 Date 类中就实现相等的重载也可以像取模问题一样传入一个仿函数。class Date { public: Date(int year, int month, int day) :_year(year) , _month(month) , _day(day) {} Date() default; bool operator(const Date date)const { return _year date._year _month date._month _day date._day; } int _year; int _month; int _day; };3.2.3 扩容问题这里我们哈希表负载因子控制在0.7当负载因子到0.7以后我们就需要扩容了我们还是按照2倍的方式扩容但是同时我们要保持哈希表大小是一个质数第一个是质数2倍后就不是质数了。如何解决一种方案就是上面在【除法散列法】中我们介绍过的JavaHashMap的使用2的整数次幂但是计算时不能直接取模的改进方法另外一种方案是SGI版本的哈希表使用的方法给了一个近似2倍的质数表每次去质数表获取扩容后的大小。// 质数表(SGI STL 同款用于扩容) static const int __stl_num_primes 28; static const unsigned long __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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; }3.2.4 代码实现// 质数表(SGI STL 同款用于扩容) static const int __stl_num_primes 28; static const unsigned long __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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K class HashFunc { public: size_t operator()(const K key) { return (size_t)key; } }; template class HashFuncstring { public: size_t operator()(const string str) { size_t hash 0; for (auto ch : str) { hash (size_t)ch; hash * 131; } return hash; } }; namespace OpenAddress { // 状态标识 enum State { EMPTY, // 空位置 EXIST, // 已存储元素 DELETE // 已删除元素 }; // 哈希表结点结构 templateclass K, class V struct HashData { pairK, V _kv; // 存储key-value对 State _state EMPTY; //初始状态为空 }; // 开放定址法哈希表(线性探测) templateclass K, class V, class Hash HashFuncK class HashTable { public: // 构造函数(初始化哈希表大小为第一个质数) HashTable() :_tables(__stl_next_prime(1)) {} // 插入 key-value对(去重) bool Insert(const pairK, V kv) { // 1.先查找避免重复插入 if (Find(kv.first)) return false; // 2.负载因子 0.7扩容 if ((double)_n / (double)_tables.size() 0.7) { HashTableK, V, Hash newht; newht._tables.resize(__stl_next_prime(_tables.size() 1)); // 3.迁移旧表元素到新表 for (size_t i 0; i _tables.size(); i) { // 遍历旧表旧表数据插入到newht if (_tables[i]._state EXIST) { newht.Insert(_tables[i]._kv); } } // 4.交换新旧表 _tables.swap(newht._tables); } // 5.线性探测找空闲位置 Hash hs; size_t hash0 hs(kv.first) % _tables.size(); // 线性探测 size_t i 1; size_t hashi hash0; while (_tables[hashi]._state EXIST) { // 冲突线性探测下一个位置 hashi (hash0 i) % _tables.size(); i; } // 6.插入元素 _tables[hashi]._kv kv; _tables[hashi]._state EXIST; _n; return true; } // 查找key返回节点指针(nullptr表示未找到) HashDataK, V* Find(const K key) { Hash hs; size_t hash0 hs(key) % _tables.size(); // 线性探测 size_t i 1; size_t hashi hash0; // 遇到EMPTY才停止查找(DELETE继续探测) while (_tables[hashi]._state ! EMPTY) { if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key) { return _tables[hashi]; } // 线性探测下一个位置 hashi (hash0 i) % _tables.size(); i; } return nullptr; } // 删除key(仅修改状态为DELETE,不实际删除元素) bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret) { // 标记为 DELETE,避免影响后续查找 ret-_state DELETE; --_n; return true; } else { return false; } } private: vectorHashDataK, V _tables; // 哈希表数组 size_t _n 0;// 已存储的数据个数 };3.3 链定址法3.3.1 扩容问题开放定址法负载因子必须小于1链地址法的负载因子就没有限制了可以大于1。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低。stl中unordered_xxx的最大负载因子基本控制在1负载因子平均是1但是这是理想的情况当然没有那么平均有的哈希桶不挂有的挂2~3个大于1就扩容艾莉丝之后在代码实现中也使用这个方式进行扩容。3.3.1.1 极端情况3.3.2 代码实现namespace Hash_bucket { templateclass K,class V class HashNode { public: HashNode(const pairK,V kv) :_kv(kv) ,_next(nullptr) {} pairK, V_kv; HashNodeK, V* _next; }; templateclass K,class V,class HashHashFuncK class HashTable { private: typedef HashNodeK, V Node; public: HashTable() :_tables(__stl_next_prime(1)) {} HashTable(const HashTableK,V,Hash oldht) :_tables(oldht._tables.size()) { for (size_t i 0; i oldht._tables.size(); i) { Node* cur oldht._tables[i]; while (cur) { Insert(cur-_kv); cur cur-_next; } } } HashTableK, V, Hash operator(HashTableK, V, Hash ht) { _tables.swap(ht._tables); _n ht._n; return *this; } ~HashTable() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; Node* lat cur; while (cur) { lat lat-_next; delete cur; cur lat; } _tables[i] nullptr; } } bool Insert(const pairK, V kv) { if (Find(kv.first)) { return false; } Hash hash; //负载因子1时扩容 if (_n _tables.size()) { vectorNode* newTable(__stl_next_prime(_tables.size() 1)); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; size_t hash0 hash(cur-_kv.first) % newTable.size(); cur-_next newTable[hash0]; newTable[hash0] cur; cur next; } _tables[i] nullptr; } } size_t hash0 hash(kv.first) % _tables.size(); Node* newnode new Node(kv); newnode-_next _tables[hash0]; _tables[hash0] newnode; _n; return true; } Node* Find(const K key) { Hash hash; size_t hash0 hash(key) % _tables.size(); Node* cur _tables[hash0]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { Hash hash; size_t hash0 hash(key) % _tables.size(); Node* prev nullptr; Node* cur _tables[hash0]; while (cur) { if (cur-_kv.first key) { if (prev nullptr) { _tables[hash0] cur-_next; } else { prev-_next cur-_next; } delete cur; --_n; return true; } prev cur; cur cur-_next; } return false; } private: vectorNode* _tables; size_t _n 0;; }; }

相关新闻