本篇文章主要讲解进阶数据结构之哈希表。1 什么是哈希表在了解什么是哈希表之前我们先来了解一下什么是哈希。哈希哈希是英文单词 hash 的音译hash 是把...弄遭、弄乱的意思其实就代表着一个物体的状态是混乱的哈希也是由此而来所以哈希又称为散列。哈希是一种组织数据的方式。哈希就是通过一个哈希函数将一个键值 key 转换为对应的索引建立键值与索引之间的映射关系这样就可以通过该映射关系给你一个键值 key采用 O(1) 时间复杂度快速找到索引从而快速查找到对应的 value。比如之前做过的一道算法题就用到了哈希的思想387. 字符串中的第一个唯一字符 - 力扣LeetCode给定一个字符串s找到它的第一个不重复的字符并返回它的索引。如果不存在则返回-1。示例 1输入:s leetcode输出:0示例 2:输入:s loveleetcode输出:2示例 3:输入:s aabb输出:-1提示:1 s.length 105s只包含小写字母class Solution { public: int firstUniqChar(string s) { //创建一个数组来记录 s 中字符出现的次数 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; } };在上面这道题中我们就采用了哈希的思想其中的哈希函数就是 hash(ch) ch - a将一个字符 ch 映射为数组 count 的下标完成对 ch 对应 value 的快速查找。所以哈希更像是一种以空间换时间的思想用额外的一些空间来达到 O(1) 时间复杂度的查找效率。哈希表哈希表正是利用了哈希的基本思想用一个哈希函数 hash(key) 来计算 key 经过映射后的索引值这样我们就可以快速完成插入和查找了。比如我们使用一个哈希函数 hash(key) key % M其中 M 是底层容器的大小这里我们使用 vector 作为底层容器。假设 M 是 11利用 hash(key) 计算索引插入 vector 的过程就是其中对应的容器例如 vector加上对应的查找规则哈希函数就构成了哈希表。当然在上面那种情况中我们发现 31、20、9 都插入到了 9 这个位置这种由于哈希函数计算出相同的索引导致多个值放到同一个位置的情况称之为冲突这种冲突的产生是由于一个哈希函数将多个 key 值映射到了同一个索引所以我们应该设计一个好的哈希函数来尽量避免冲突另外不管多好的哈希函数都是不可能完全避免冲突的产生的所以后面我们还需要一定的解决冲突的办法。综合上面两点一个设计好的哈希表应该包含两个方面一个就是好的哈希函数来尽量避免冲突另一个就是有一个好的解决冲突的办法。这里再提一嘴之前我们在排序时接触过的技计数排序其实也是哈希思想的体现。在计数排序中哈希函数为 hash(key) key - minnum但是计数排序只适合于数据比较集中的情况否则会特别浪费空间。2 哈希函数上面我们说一个好的哈希表应该包含一个好的哈希函数用来尽量避免冲突的产生。常用的哈希函数主要包括除余散列法、乘法散列法、全域散列法、平方取中法、数学分析法等等。但是在日常使用中我们主要还是使用除余散列法其他的用的比较少。所以这里我们主要介绍前三种剩下的大家感兴趣可以自主学习。除余散列法除余散列法又叫做除留余数法。这种方法就是我们上面采用的哈希函数其核心数学公式为其中M 为哈希表的大小。通过上面的例子我们可以看到如果哈希表采用除留余数法作为哈希函数那么其性能大部分是取决于 M 的大小的如果 M 太小那么冲突的概率会很高如果 M 很大又会浪费空间所以 M 的选择很重要。在实际应用中我们一般将 M 设为远离 2^k 的质数。因为如果我们选取 2^k 作为 M 的大小那么其实在取余数时其余数就是二进制中的后 k 位。比如 M 8那么 9 % 8 1001 % 1000 001 1再比如 10 % 8 1010 % 1000 010 2。所以如果取 2^k其实得到的索引就是二进制的后 k 位也就是说只有 key 的后 k 位参与了运算key 的所有位数并不会参与运算这其实就是增加了冲突的概率。所以我们一般选择远离 2^k 的质数比如 11,53 等等。但是在实际应用中M 也不一定会完全取成远离 2^k 的质数。比如 Java 中的 HashMap 就使用了 2^k 作为 M但是其会先对 key 进行扰动计算高位与低位异或使更多比特参与哈希值生成再对 key 进行 2^k 取模这样就充分利用了 key 的每一位也会降低冲突的概率。但是使用除余散列法时会有一个缺点那就是被除数 key 必须为 size_t 类型因为如果不为整形那就无法进行模运算而且如果是负数的话那么取模出来依然是一个负数放入底层结构 vector 时就会越界下标从 0 开始所以如果 key 为 string我们就需要将其转换为 size_t 类型。乘法散列法乘法散列法是一种通过小数部分的均匀分布特性实现关键字均匀映射的哈希函数设计方法其核心优势在于对哈希表的长度 M 没有特殊要求且能有效避免除法散列法中因模数选择不当导致的冲突概率增加问题。乘法散列法的核心数学公式为其中 A 为 (0, 1) 之间的一个小数常数常取黄金分割点floor 是向下取整的符号。(A * key) % 1.0 会得到一个小于 1 的小数然后再乘以 M再向取整就得到了索引。比如 key 10M 8A 取黄金分割点那么 hash(10) floor(8 * (6.1803) % 1.0) floor(8 * 0.1803) floor(1.4424) 1。乘法散列法的好处就是冲突概率跟哈希表的大小 M 没有关系比除余散列法的冲突概率小很多。但是缺点也很明显计算效率与实现复杂度会比除余散列法高很多而且除余散列法在实际应用中的冲突概率还是可以接受的所以一般都会选择除余散列法。全域散列法全域散列法主要是为了预防恶意攻击者攻击而存在的一种哈希函数。在传统的哈希方法中哈希函数是固定的。如果攻击者提前知道了这个函数就可以故意构造出一大批映射到同一个地址的关键字也就是哈希碰撞攻击。然后哈希表中的冲突概率就会急剧增加导致哈希表的性能大幅下降。所以全域散列法就会构造一大批散列函数称为散列函数族。其核心数学公式为其中 P 是一个很大的质数a 在 [1, P - 1] 中随机选择一个数字b 在 [0, P - 1] 中随机选择一个数字这样 a,b 不同哈希函数就不同a,b 一共能构成 P* (P-1) 个函数所以上面那个哈希函数就构成了一个哈希函数族。总之全域散列法是一种通过随机化策略来防御哈希冲突的哈希函数设计思想。与前几种固定的哈希算法不同它的核心在于随机选择。在程序运行时从一个精心设计的哈希函数族中随机挑选一个函数来映射数据。这种方法能有效对抗恶意攻击者精心构造的冲突数据保护了哈希函数的性能。3 解决哈希冲突不管是用上面的哪种哈希函数当数据量很大时难免会发生冲突。所以我们还需要一个处理冲突的方法来解决哈希表中的冲突。解决冲突的方法一共有两种开放定址法以及链地址法。开放定址法开放定址法也叫闭散列法顾名思义就是所有的元素都要呆在哈希表内部。当发生冲突时会寻找下一个哈希表为空的位置然后将数据放进去。其核心数学公式为其中 M 就是哈希表的大小d_i 为发生冲突时的增量序列也就是发生冲突时将当前数据放在相对于冲突位置的下一个位置的增量。比如 M 11key 20经过 hash(20) 20 % 11 9得到了索引 9 之后但是 9 位置已经有数据了但是 10 位置没有数据就可以将 20 放在 10 位置此时的 d_i 1。开放定址法主要有三种接下来我们一一进行讲解。不过在讲解三种方法之前我们先了解一个负载因子的概念。负载因子负载因子也叫做载荷因子、装载因子英文名称为 load facto。负载因子是指数据量 N 和哈希表容量 M 之间的比值即 N/M其描述了一个哈希表内部的空间利用率也描述了哈希表内部发生冲突的概率大小。比如哈希表容量为 10但是里面已经有 7 个元素了负载因子就为 0.7。当负载因子很小时哈希表内部比较空旷此时发生冲突的概率比较低但同时空间利用率就会很小当负载因子很大是哈希表内部比较拥挤虽然空间利用率大了但是发生冲突的概率也会响应的变得很高。所以负载因子是平衡哈希表空间利用率与性能效率的杠杆在设计时我们应该给一个合适的负载因子既要考虑性能又要考虑空间利用率。线性探测法线性探测法就是从冲突的位置开始一直向后线性探测直到找到下一个没有存储的位置为止如果走到了哈希表的结尾那么就返回哈希表的头部再线性寻找。所以其核心数学公式为上面那个哈希表如果采用线性探测法解决冲突的过程如下可以看到线性探测法其实就是占据了本来属于别人的位置使得本来属于那个位置的元素又不得不去占据别的元素的位置当一个哈希表中 hash0、hash1、hash2 都有元素时后续映射到 hash0、hash1、hash2 的元素都会去争夺 hash3 这个位置就会导致一个位置发生冲突其周围的位置都会很快被占满这样的现象称为群集或者堆积会大大降低哈希表的效率。产生这种现象的原因就是哈希表的负载因子太高了整个哈希表很拥挤所以线性探测法的负载因子不应该太高一般设为 2/3 或者 0.7、0.8 左右。二次探测法二次探测法为了解决线性探测法聚集的问题将探测方式变为了跳跃式探测即 di 01^2-1^22^2-2^2......(M/2)^2-(M/2)^2。其核心数学公式为如果 hashi 0 了那么 hashi 需要加上 M。上面那个哈希表根据二次探测解决冲突的过程如下虽然二次探测解决了聚集的问题但是容易产生二次聚集的问题也就是相同冲突位置的元素还是采用相同的路径进行探测。双重散列法双重散列法为了彻底解决上面的冲突问题当发生冲突时其偏移量是使用另一个哈希函数 hash2(key) 计算出来也就是 di i * hash2(key)。其核心数学公式为其中hash2(key) 与 M 一般互为质数有两种取法1M 取 2^khash2(key) 在 [0, M-1] 之间随机选择一个奇数2M 取一个质数h2(key) key % (M - 1) 1。如果按照第二种方法M 11hash2(key) key % 10 1那么上面那个哈希表按照双重散列法解决冲突的过程为其中蓝色代表进行了一次探测紫色代表进行了两次探测。虽然双重探测可以有效减免聚集现象的产生但是还是会占用其他元素的空间使得本来不冲突的元素也发生冲突。所以不管是上面哪种开放定址法都会产生相互影响。所以我们主要采用后面的链地址法来解决冲突。使用线性探测法实现哈希表在使用线性探测法实现哈希表之前我们需要注意几个点。哈希表大小的选择以及扩容注意事项哈希表的底层结构我们选择的是 vector也就是之前在继承章节了解过的组合形式。我们说哈希表的大小最好选成一个质数所以这里我们可以参考一下库中的实现方法。库中用了一个全是质数的数组而且后一个差不多是前一个的两倍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; const unsigned long* pos std::lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; }其中核心函数就是unsigned long __stl_next_prime(unsigned long n)函数这个函数用到了库中的 lower_bound 函数这个函数与我们在 map 和 set 中用到了 lower_bound 函数相同只要你给他一个迭代器区间和一个值 n他就会帮你返回容器中第一个 n 位置的迭代器。所以 __stl_next_prime 函数的核心作用就是返回 __stl_prime_list 数组中 n 的第一个值。我们在扩容时就可以利用这个函数每次扩容只要将大小设置为 __stl_next_prime(ht.size() 1) 即可。另外在扩容之后需要注意一点要对哈希表内的数据重新计算映射关系因为哈希表的大小变了索引也会改变。所以对于哈希表来说扩容的代价是比较大的不仅要遍历哈希表还要重新计算映射索引。哈希表中如何删除元素删除哈希表中的元素时我们不能将一个元素直接删除因为会出现后面的元素找不到的情况比如图中直接删除了 9 这个元素导致哈希表中索引 9 的位置为空了那么我们查找 20 这个元素时由于 20 的索引也为 9但是 9 索引位置为空了此时就会判断 20 找不到但实际上 20 是存在的。为了防止上述情况的发生我们可以为每一个哈希表位置设置一个标记{EMPTY, EXIST, DELETE}此时 9 就不是空了而是 DELETE 标记但是还是存在的只有找到 EMPTY 标记才代表真的为空。将键值转为整数我们在哈希表中采用的除留余数法哈希函数但是除留余数法只能对整数进行取模而且必须是 0 或者正整数取模才可以那么当键值是负数或者不能转换为整数类型怎么办呢其实我们只需要在 HashTable 中添加一个 Hash 模板参数传递将 key 值转换为整数的仿函数就可以了。templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //由于在日常生活中 string 作为键值非常常用所以这里将模板进行特化 template struct HashFuncstd::string { size_t operator()(const std::string key) { //这里对 string 进行了 BKDR_Hash 算法避免不同字符串之间产生相同的整形值 size_t hash 0; for (auto ch : key) { hash * 131; hash ch; } return hash; } };代码实现//HashTable.hpp #pragma once #include iostream #include string #include vector //库中的计算 hashtable 容量大小的数组及函数 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; const unsigned long* pos std::lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //由于在日常生活中 string 非常常用所以这里将模板进行特化 template struct HashFuncstd::string { size_t operator()(const std::string key) { //这里对 string 进行了 BKDR_Hash 算法避免不同字符串之间产生相同的整形值 size_t hash 0; for (auto ch : key) { hash * 131; hash ch; } return hash; } }; namespace open_address { enum State { EXIST, EMPTY, DELETE }; templateclass K, class V struct HTData { std::pairK, V _data; State _state EMPTY; // 需要一个字段来标记当前位置的状态 }; templateclass K, class V, class Hash HashFuncK class HashTable { public: HashTable(size_t size __stl_next_prime(0)) :_ht(size) ,_n(0) {} bool Insert(const std::pairK, V kv) { //不能插入相同值 if (Find(kv.first) 0) return false; //0.如果负载因子超过了 0.7那么就对当前的 hash 表进行扩容 if ((double)_n / (double)_ht.size() 0.7) { //扩容到下一个质数 HashTableK, V newht(__stl_next_prime(_ht.size() 1)); //复用当前 Insert for (size_t i 0; i _ht.size(); i) { //只插入当前状态为存在的值 if (_ht[i]._state EXIST) { newht.Insert(_ht[i]._data); } } //将当前表与新表交换 _ht.swap(newht._ht); } Hash hs; //1. 根据哈希函数计算出当前 key 所存放的索引 size_t hashi hs(kv.first) % _ht.size(); //2. 如果索引位置已经存在数据那就进行线性探测 if (_ht[hashi]._state EXIST) { while (_ht[hashi]._state EXIST) { hashi; hashi % _ht.size(); } } _ht[hashi]._data kv; _ht[hashi]._state EXIST; _n; return true; } bool Erase(const K key) { int hashi Find(key); if (hashi -1) return false; _ht[hashi]._state DELETE; --_n; return true; } int Find(const K key) { Hash hs; //1. 根据哈希函数计算出当前 key 所存放的索引 size_t hashi hs(key) % _ht.size(); //2. 如果索引位置已经存在数据那就进行线性探测 while (_ht[hashi]._state ! EMPTY) { if (_ht[hashi]._state EXIST _ht[hashi]._data.first key) return hashi; hashi; hashi % _ht.size(); } return -1; } private: std::vectorHTDataK, V _ht; size_t _n; }; void Test_Hashtable01() { HashTableint, int ht(11); ht.Insert({ 1, 1 }); ht.Insert({ 3, 1 }); ht.Insert({ 9, 1 }); ht.Insert({ 13, 1 }); ht.Insert({ 20, 1 }); ht.Insert({ 31, 1 }); ht.Insert({ 5, 1 }); ht.Insert({ 70, 1 }); ht.Insert({ 28, 1 }); ht.Insert({ 50, 1 }); ht.Insert({ 51, 1 }); ht.Insert({ 59, 1 }); int ret ht.Find(31); std::cout ret std::endl; ret ht.Find(50); std::cout ret std::endl; ht.Erase(20); std::cout ht.Find(20) std::endl; ret ht.Find(31); std::cout ret std::endl; } void Test_Hashtable02() { HashTablestd::string, std::string ht; ht.Insert({left, 左边}); ht.Insert({right, 右边}); ht.Insert({sort, 排序}); ht.Insert({algorithm, 算法}); int ret ht.Find(left); std::cout ret std::endl; ret ht.Find(right); std::cout ret std::endl; ht.Erase(left); std::cout ht.Find(left) std::endl; } }链地址法链地址法主要是利用了链表这一数据结构来解决了冲突的问题。此时哈希表内部不再存储真正的元素而是存储单链表的头节点指针每个哈希表节点连接的单链表才是真正存储数据的数据结构。所以如果采用链地址法上面的哈希表就会变成然后查找也很简单所以链地址法就解决了元素之间相互影响。根据上面的逻辑结构链地址法也有两个比较形象的别名 — 拉链法和哈希桶。但是哈希桶有一个缺点就是极端情况下一个桶下面的单链表可能会很长会影响哈希表的查找效率所以此时我们就可以将一个桶下面的单链表变为红黑树这样查找效率就会大大提高Java 的 HashMap 就是这样做的。链地址法实现哈希表#pragma once #include iostream #include string #include vector //库中的计算 hashtable 容量大小的数组及函数 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; const unsigned long* pos std::lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //由于在日常生活中 string 非常常用所以这里将模板进行特化 template struct HashFuncstd::string { size_t operator()(const std::string key) { //这里对 string 进行了 BKDR_Hash 算法避免不同字符串之间产生相同的整形值 size_t hash 0; for (auto ch : key) { hash * 131; hash ch; } return hash; } }; namespace Bucket { templateclass K, class V struct HTNode { std::pairK, V _kv; HTNodeK, V* _next;//需要有指向下一个节点的指针 HTNode(const std::pairK, V kv) :_kv(kv) ,_next(nullptr) {} }; templateclass K, class V, class Hash HashFuncK class HashTable { //using 的另一用法类似于 typedef using Node HTNodeK, V; public: HashTable(size_t size __stl_next_prime(0)) :_tables(size) , _n(0) {} bool Insert(const std::pairK, V kv) { //不能插入相同值 if (Find(kv.first)) return false; Hash hs; //0.如果负载因子为1那么就对当前的 hash 表进行扩容 if (_n _tables.size()) { //将原哈希表中的所有节点移到新的哈希表中 HashTable newht(__stl_next_prime(_tables.size() 1)); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; Node* next nullptr; while (cur) { next cur-_next; int hashi hs(cur-_kv.first) % newht._tables.size(); cur-_next newht._tables[hashi]; newht._tables[hashi] cur; cur next; } _tables[i] nullptr; } //交换新表与旧表 _tables.swap(newht._tables); } //1. 根据哈希函数计算出当前 key 所存放的索引 size_t hashi hs(kv.first) % _tables.size(); //2. 新添加一个节点将该节点头插到对应的单链表中 Node* newnode new Node(kv); Node* cur _tables[hashi]; newnode-_next cur; _tables[hashi] newnode; _n; return true; } bool Erase(const K key) { if (!Find(key)) return false; //删掉该节点 Hash hs; //1. 根据哈希函数计算出当前 key 所存放的索引 size_t hashi hs(key) % _tables.size(); //2. 遍历当前单链表 Node* prev nullptr; Node* cur _tables[hashi]; while (cur) { if (cur-_kv.first key) break; prev cur; cur cur-_next; } if (prev nullptr) { //cur 是头节点 _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; --_n; return true; } Node* Find(const K key) { Hash hs; //1. 根据哈希函数计算出当前 key 所存放的索引 size_t hashi hs(key) % _tables.size(); //2. 遍历当前单链表 Node* cur _tables[hashi]; while (cur) { if (cur-_kv.first key) return cur; cur cur-_next; } return nullptr; } //不要忘记写析构函数 ~HashTable() { for (auto ptr : _tables) { Node* cur ptr; Node* next nullptr; while (cur) { next cur-_next; //释放当前节点 delete cur; cur next; } ptr nullptr; } } private: std::vectorNode* _tables; size_t _n; }; void Test_Hashtable01() { HashTablestd::string, std::string ht; ht.Insert({ left, 左边 }); ht.Insert({ right, 右边 }); ht.Insert({ sort, 排序 }); ht.Insert({ algorithm, 算法 }); auto ret ht.Find(left); if (ret) std::cout ret-_kv.first : ret-_kv.second std::endl; else std::cout Not Find std::endl; ret ht.Find(right); if (ret) std::cout ret-_kv.first : ret-_kv.second std::endl; else std::cout Not Find std::endl; ht.Erase(left); ret ht.Find(left); if (ret) std::cout ret-_kv.first : ret-_kv.second std::endl; else std::cout Not Find std::endl; } //测试扩容 void Test_Hashtable02() { HashTableint, int ht(11); const size_t N 20; srand(time(nullptr)); for (int i 0; i N; i) { int x rand(); //打个条件断点看一下扩容执行情况 if (i 11) { ht.Insert({ x, x }); continue; } ht.Insert({ x, x }); } } }总结哈希表是一个具有 O(1) 查找时间复杂度的数据结构也是 unordered_map 与 unordered_set 的底层实现结构。一个好的哈希表要具有好的哈希函数以及解决冲突的方法在日常使用中最常使用的哈希函数就是除余散列法最常使用的解决冲突的方法就是哈希桶stl 中的 unordered_map 与 unordered_set 也是使用哈希桶实现的。
