C++数据结构 — 哈希表 (Hash Table)、散列函数 课程设计与应用

​ 🎁个人主页：工藤新一¹

​ 🔍系列专栏：C++面向对象（类和对象篇）

​ 🌟心中的天空之城，终会照亮我前方的路

​ 🎉欢迎大家点赞👍评论📝收藏⭐文章

文章目录

• 哈希表( Hash Table ) —— 算法数据结构
  • （一）、哈希表的概念
    • 1.1哈希表的定义
    • 1.2哈希函数
    • 1.3哈希冲突
      • 1.3.1对于哈希冲突的认知
  • （二）、常见的哈希函数
    • 2.1直接定址法
    • 2.2除留余数法
  • （三）、处理哈希冲突
    • 3.1线性探测法
    • 3.2链地址法
  • （四）、哈希表的模拟实现
    • 4.1线性探测法
      • 4.1.1创建
      • 4.1.2哈希函数以及处理哈希函数
      • 4.1.3添加元素
      • 4.1.4查找元素
      • 4.1.5测试代码
    • 4.2连地址法
      • 4.2.1创建
      • 4.2.2知识穿插 —**树的存储 - 链式前向星**
      • 4.2.3哈希函数
      • 4.2.4插入元素
      • 4.2.5查找元素
      • 4.2.6代码实现
  • （五）、简介STL - unordered_set / unordered_map
    • 1. [unordered_set](https://so.ZEEKLOG.net/so/search?q=unordered_set&spm=1001.2101.3001.7020)的介绍
    • 2.STL容器差异

哈希表( Hash Table ) —— 算法数据结构

（一）、哈希表的概念

1.1哈希表的定义

• 哈希表（hash table），又称散列表，是根据关键字进行访问的数据结构。
• 哈希表建立了一种关键字和存储地址之间的映射关系，使每个关键字与结构中的唯一存储位置相对应。

• 理想情况下，在散列表中进行查找的时间复杂度为O(1)，即与表中的元素数量无关。因此哈希表是一种存储和查找非常快的结构。
• 核心思想：给出关键字，通过映射关系找出存储位置。
• 关键字 ----> 映射关系 ----> 存储位置

int cnt[26];//创建一个大小为26的数组voidsolve(string& s){for(auto ch : s)//遍历语法糖{ cnt[ch -'a']++;/* 因为'a' - 'a' = 0,'b' - 'a' = 1;将对应的数组索引位置 +1，从而通过下标映射出字符出现的次数。 */}}

• 流程演示

"a b c a b c c"//idex ^ 扫描到 a 时，其元素的映射关系的（下标）0 位置进行 ++ 

"a b c a b c c"//idex ^ 扫描到 b 时，其元素的映射关系（下标）1 位置进行++ 

"a b c a b c c"//idex ^ 扫描到 c 时，其元素对应位置（下标）2 位置进行++ 

"a b c a b c c"//idex ^ 同理。 

"a b c a b c c"//idex ^ 

int cnt[26];voidsolve(string& s){for(auto ch : s){ cnt[ch -'a']++;/* 'b' - 'a' == 1，因此当我们要统计字符 b 出现的次数时，可以通过下标为 1 的位置，来找到字符 b 出现的次数，cnt[1]。 */}}

• 因此在我们这段编程代码中:
• 关键字(字符a, b, c) ----> 映射关系(ch - 'a') ----> 存储位置(idex)

1.2哈希函数

• 定义：将关键字映射成对应地址的函数就是哈希函数。
  说白了，哈希函数就是这个映射关系。
交给哈希函数一个关键字，哈希函数给我们计算出一个存储位置。
• 哈希函数，也叫做散列函数，记作：Hash( key ) = Adder。
F ( x ) = K;
• 比如上个案例中 ch - ‘a’ 就是一个哈希函数，记作：Hash( key ) = key - ‘a’，代入公式：Hash( ch ) = ch - ‘a’。
• 算法核心：Hash( key ) = Adder。告诉哈希函数( Hash )一个关键字 key ( x ) ，( Hash )会返回关键字 key 所对应的存储位置( Adder )。

1.3哈希冲突

• 设计哈希函数：Hash( key ) = key % 7;( 为什么 % 7 )
  • 由数组大小可知，sizeof(a) == 7;因此我们 %7 后绝对是可以将数组中的每一个元素映射到大小为 7 的数组中的每一个存储位置上( 数组中的每个元素都会被映射到 idex == 0~6 的位置上)。
  • 因此，我们可以开辟一个大小为7的数组即可。

但此时的问题就会显现：

哈希函数可能会把两个或两个以上不同的关键字，映射到同一个存储位置上，这种情况被称为哈希冲突，也叫做散列冲突。起冲突的两个不同关键词被称为同义词。

hash(3)=3;hash(17)=3;/* 当我们统计元素 3 出现的次数时,对应 3 存储位置上的数++; 当我们统计元素 17 出现的次数时,对应 3 存储位置上的数也会进行了++操作 */

如上所见，两个不同的元素却出现在同一个存储位置上!
综上：不同的关键字映射到同一个存储位置上，这种情况我们就成为哈希冲突。

1.3.1对于哈希冲突的认知

• 哈希冲突不可避免。
• 我们需要的不是消除哈希冲突，而是设法设计出优秀的哈希函数，并且处理哈希冲突。
• 由此可见，设计一个优秀的哈希表，不仅需要设计一个优秀的哈希函数，也需要能够处理哈希冲突。那么，学习哈希表的重点就是设计哈希函数和处理哈希冲突。

（二）、常见的哈希函数

2.1直接定址法

• 在哈希表概念篇章中，统计字符串中某字符出现次数的案例所使用的方法，就是直接定址法。
• 直接定址法：直接取关键字的某个线性函数值为散列地址。比如，直接映射"Hash( key ) = key "，直接拿关键字的值当作存储地址(Adder)或者拿一个线性的值当作存储地址(Adder)"Hash( key ) = a * key + b "(a，b 是常数) 。这种方式计算较为简单，适合关键字分布基本连续的情况，但关键字分布不连续，会导致空位较多，导致存储空间的大量浪费。
• 如下情况使用思路一会导致存储空间的浪费：

2.2除留余数法

• 如上图哈希冲突例子中的思路二即是典型的除留余数法：拿关键字的值 % 某一个数，映射到下标的某一个位置( 存储位置上 )。
• **除留余数法：**顾名思义，假设哈希表的大小为 M，那么通过key / M的余数作为映射位置的下标，也就是哈希函数：hash( key ) = key % M。因此这种方法的重点就是选好模数M。
  • 建议 M 取不太接近 2 的整数次幂的一个质数（素数）。（ 具体原理可以参考《算法导论》中的证明，选素数可以使分布更均匀从而减少冲突）

（三）、处理哈希冲突

• 有时候哈希表无论选择什么哈希函数都无法避免哈希冲突的产生，那么插入数据时，如何解决解决哈希冲突呢？主要有两种方法：线性探测法和链地址法。

3.1线性探测法

• 线性探测：从发生冲突的位置开始，依次线性向后探测，直到找到下一个没有存储数据的位置为止，若走到哈希表表尾，则回绕到哈希表表头位置。
• 线性探测法的弊端：当数组对元素的存储过于拥挤时，会导致查找与存储的时间复杂度退化为O(N)。
• 案例说明：哈希表的作用 — 存储数据
• INF：无穷大是数组中绝对不会出现的值，将数组初始化为INF可以明确表示某个位置尚未被有效赋值。如果数组未初始化，其值是不确定的（可能包含随机垃圾值），将数组初始化为INF可以避免因未定义行为导致的错误。

h(19)=8(哈希值 || Adder); 因此我们将关键字 19 存放到下标为 8 的存储位置上 

h(30)=8; 因此我们将关键字 30 存放到下标为 8 的存储位置上 但发现下标为 8 的存储位置上已经存放了其他元素，此时就发生哈希冲突 使用线性探测法，依次线性向后寻找一个没有存储元素的位置 最终我们发现下标为 9 的位置上可以存放关键字 30

h(5)=5;h(26)=3;h(13)=2; 将关键字 5 放到下标为 5 的存储位置上 将关键字 26 放到下标为 3 的存储位置上 将关键字 13 放到下标为 2 的存储位置上 h(20)=9; 发现下标为 9 的存储位置上存放着其他元素，此时发生了哈希冲突 使用线性探测法，依次线性向后寻找一个没有存储元素的位置 

h(21)=10; 发生哈希冲突，且存储位置在表尾上 接下来再回到表头，进行线性探测 h(12)=1; 发生哈希冲突，存储至下标为 2 的存储位置上 此时数组中的所有的元素，都以线性探测的方式存入哈希标中 

3.2链地址法

• 链地址法：链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们将这些冲突的数据链接成一个链表，挂在哈希表存储位置的下方。

• 结果如下：

• 注意：我们这里的链表执行的插入操作是头插操作。
• 弊端：当数组中所有的元素都存放在同一个存储位置时，时间复杂度就退化成了O(N)。
• 解决弊端的措施： 不再继续使用链表的方式来穿插哈希表存储位置的下方元素，而是改用红黑树！时间复杂度就变为了O( logN )。

（四）、哈希表的模拟实现

4.1线性探测法

4.1.1创建

#include<iostream>usingnamespace std;#include<cstring>constint N =23;//(随意选取一个质数)//创建哈希表 h，无穷大：0x3f3f3f3f，通常用一个特殊值表示某个位置是空的或未被使用。int h[N], INF =0x3f3f3f3f;//为 h 数组初始化voidinit(){//使用 memset 函数将整个数组 h 初始化为 0x3f3f3f3fmemset(h,0x3f,sizeof h);}intmain(){init();return0;}

4.1.2哈希函数以及处理哈希函数

除留余数法：hash(key) = key % N;

但要注意，key有可能是负数，负数取模后仍是负数。

核心重点：

​ eg：hash(-5) = -5(key) % 23(质数) (映射)----> 负数(下标) 大家仔细思考，其所得到这个负数结果，是会被映射到存储位置（下标）上的，但数组中是不会存在负数下标的。因此，如果我们需要映射一个负数存储空间时，那就需要进行补正操作。**负数补正操作：**取模后再加上模数即可。eg：（-5 % 23）+ 23（模数）但正数取模后再加上模数整体就会变大，所以需要统一再次进行取模操作。eg：（5 % 23） + 23 == 28，因此需要统一补正操作。

最终就是：（5 % 23 + 23 ） % 23;

公式：（key % N + N）% N ，简称： 模加模 。

#include<iostream>usingnamespace std;#include<cstring>constint N =23;int h[N], INF =0x3f3f3f3f;voidinit(){memset(h,0x3f,sizeof h);}//实现哈希函数的功能 - 计算出 x 的存储位置inthash(int x){int id =(x % N + N)% N;//处理哈希冲突 - 线性探测法while(h[id]!= INF && h[id]!= x)//当 id 位置存在其他元素，且h[id] != x;{ id++;if(id == N) id =0;//如果走到尾部，就从头再来}return id;}intmain(){init();return0;}

4.1.3添加元素

通过哈希函数找到合适的位置，将其放入即可。

voidinsert(int x){int idex =hash(x);//找到 x 适合存放的位置 h[idex]= x;}

4.1.4查找元素

通过哈希函数找到映射位置，判断数组中的值是否是 x

boolfind(int x){int idex =hash(x);return h[idex]== x;}

4.1.5测试代码

#include<iostream>usingnamespace std;#include<cstring>constint N =23;int h[N], INF =0x3f3f3f3f;voidinit(){memset(h,0x3f,sizeof h);}inthash(int x){int id =(x % N + N)% N;while(h[id]!= INF && h[id]!= x){ id++;if(id == N) id =0;}return id;}voidinsert(int x){int idex =hash(x); h[idex]= x;}boolfind(int x){int idex =hash(x);return h[idex]== x;}intmain(){init();int n;cin >> n;while(n--){int op, x;cin >> op >> x;if(op ==1){insert(x);}elseif(op ==2){if(find(x)) cout <<"Yes"<< endl;else cout <<"No"<< endl;}}return0;}

4.2连地址法

4.2.1创建

连地址法的实现与 树的存储 - 链式前向星 一模一样

本质也是使用数组模拟链表

#include<iostream>usingnamespace std;constint N =23;int h[N];//使用数组创建哈希表int e[N], ne[N], id;//e[N] - 数据域，ne[N] - 指针域intmain(){return0;}

4.2.2知识穿插 —树的存储 - 链式前向星

链式前向星是在静态链表（链表概念）的基础上完成的。

链式前向星的本质是用数组来模拟链表，名字听起来很花哨，但是不要被唬到。链式前向星其实就是用链表存储所有的孩子节点（树中的概念），其中链表是用数组来模拟实现的。

4.2.3哈希函数

除留余数法

//哈希函数 - 计算哈希值inthash(int x){return(x % N + N)% N;//确保哈希值非负}

4.2.4插入元素

实质就是把当前这个节点( x )放到当前的哈希值( 存储位置 )所对应的链表上

插入方式：头插 - 涉及链表的存储

//插入元素，并且处理哈希冲突voidinsert(int x){int idex =hash(x);//计算哈希值(存储位置)//把 x 头插到 idex 所在的链表在 中 id++;//为元素 x 分配一个存储位置  e[id]= x;//链地址法 ne[id]= h[idex];//新节点的指针指向当前头节点 h[idex]= id;//更新头节点}

4.2.5查找元素

找出哈希值

遍历链表 - 涉及链表的遍历

boolfind(int x){int idex =hash(x);//计算哈希值(存储位置)//遍历链表中是否存在元素 xfor(int i = h[idex]; i; i = ne[i])if(e[i]== x)returntrue;returnfalse;}

4.2.6代码实现

#include<iostream>usingnamespace std;constint N =23;int h[N];int e[N], ne[N], id;inthash(int x){return(x % N + N)% N;}voidinsert(int x){int idex =hash(x); id++; e[id]= x; ne[id]= h[idex]; h[idex]= id;}boolfind(int x){int idex =hash(x);for(int i = h[idex]; i; i = ne[i])if(e[i]== x)returntrue;returnfalse;}intmain(){int n;cin >> n;while(n--){int op, x;cin >> op >> x;if(op ==1){insert(x);}elseif(op ==2){if(find(x)) cout <<"Yes"<< endl;else cout <<"No"<< endl;}}return0;}

（五）、简介STL - unordered_set / unordered_map

1. unordered_set的介绍

unordered_set是一种关联式容器，它具有以下几个特点：

1.基本概念unordered_set是一种关联式容器，不按特定顺序存储键值。元素的值同时也是唯一标识它的key

2.内部存储方式内部元素没有按照特定顺序排序。为快速找到指定key，将相同哈希值的键值放在相同的桶中(开散列)。

3.性能特点通过key访问单个元素比set快。在遍历元素子集的范围迭代方面效率较低，因为数据并不在某个范围，而是无序的。

4.迭代器类型迭代器至少是前向迭代器。

具体可参考官方文档——unordered_set

2.STL容器差异

1.set与unordered_set 的区别前者的实现方式是红黑树，后者是哈希表。使用方式完全一样。无非是存储和查找的效率不同。以及前者(set)是有序，后者(unordered_set)是无序的。

2.unordered_set与unordered_map的区别前者只存储键，且键是唯一的，没有值，后者存储键值对（key-value），键是唯一的，但值可以重复。

3.unordered_set 与 unordered_multiset区别前者存储唯一的元素，不允许重复，后者允许存储重复的元素。

🌟各位看官好，我是工藤新一¹呀~

🌈愿各位心中所想，终有所致！