哈希表 ╰半夏微凉° 2022-10-30 07:24 183阅读 0赞 **上一篇博客:[静态链表的介绍及实现][Link 1]** > 写在前面:大家好!我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正,感谢大家的不吝赐教。我的唯一博客更新地址是:[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油,冲鸭! > `用知识改变命运,用知识成就未来!加油 (ง •̀o•́)ง (ง •̀o•́)ง` ### 文章目录 ### * 简介 * 冲突及解决方式 * 链地址法 * * 简介 * 代码实现 * * 插入操作 * 查找操作 * 例题 * * 题目描述 * 输入格式 * 输出格式 * 数据范围 * 输入样例 * 输出样例 * 解题代码 * 开放寻址法 * * 简介 * 查找操作 * 完整代码 # 简介 # 哈希表(Hash Table),又叫散列表,是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说,把关键字映射到一个表中的位置来直接访问记录,以加快访问速度。 在线性表、树等结构中,记录在结构中的性对位置是随机的,和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需要进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上。例如顺序查找、折半查找、二叉排序树查找等等。查找的效率依赖于查找过程中所进行的比较次数。 理想的情况下是希望不经过任何比较,一次存取就能得到所要查询的记录,那么就必须在记录的存储位置和它的关键字之间建立一个确定的关系 f f f,使每个关键字和结构中一个唯一存储的位置相对应。因而在查找时,只要根据这个对应关系 f f f,找到给定值 **k** 的像 f ( k ) f(k) f(k)。若结构中存在关键字和 **k** 相等的记录,则必定在 f ( k ) f(k) f(k)的存储位置上,由此,不需要进行比较便可以直接取得所查的记录。这个对应关系 f f f 为 **哈希** (Hash)函数,按照这个思想建立的表称为 **哈希表**。 # 冲突及解决方式 # 对不同的关键字可能得到同一散列地址,即 **k1 ≠ k2**,而 f ( k 1 ) f(k1) f(k1) = f ( k 2 ) f(k2) f(k2),这种现象称为冲突,具有相同函数值的关键字对该哈希函数来说称作**同义词**。冲突的处理方式有很多,例如:链地址法、开放定址法、再哈希法、建立一个公共溢出区等等。平时只要用到的是前两种,这里主要写一下前两个解决方式。 # 链地址法 # ## 简介 ## 链地址法就是将所有关键字为**同义词**的记录存储在同一线性表中。假设某哈希函数产生的哈希地址在区间 **\[0, m - 1\]** 上,则设立一个指针性向量 **Hash\[m\]**;其每个分量的初始状态都是空指针。凡哈希地址为 **i** 的记录都插入到头指针为 **Hash\[i\]** 的链表中。在链表中的插入位置可以在表头或者表尾,也可以在中间,以保持在同一线性链表中按关键字有序。 例如已知一组关键字为 **(19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79)** 则按哈希函数 H ( k ) = k e y M O D 13 H(k) = key\\ MOD\\ 13 H(k)=key MOD 13 和链地址法处理冲突所得的哈希表如图: ![哈希表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70] ## 代码实现 ## 可以使用上一篇博客提到的 [静态链表的介绍及实现][Link 1] 来实现链地址法。首先开一个 **h\[\]** 数组来存储所有的哈希值,初始状态下可以使用一个特殊的值来表示空指针,即链的尾结点。然后使用一个链表来存储所有的记录。每次将每一个节点插入到对应哈希值的数组上,在上面拉一条链,每一个 **h\[\]** 数组的值相当于每一个链的**头结点**。当查询时只要求出对应的哈希值,遍历对应的单链表即可。 **注意:** 在使用 `除留余数法` 求哈希值的时候,所取模的数最好是一个质数,因为这样可以使冲突的概率尽可能的小。 ### 插入操作 ### void insert(int x) { int k = (x % N + N) % N; // k 为哈希值,用这种方法可以将 x % N 的余数从负数变成正数 // 使用头插法将当前的点插到 h[K] 上 e[idx] = x; ne[idx] = h[k]; h[k] = idx++; } ### 查找操作 ### bool find(int x) { int k = (x % N + N) % N; for (int i = h[k]; i != -1; i = ne[i]) { if (e[i] == x) return true; } return false; } ## 例题 ## 题目来源:[AcWing 840. 模拟散列表][AcWing 840.] ### 题目描述 ### 维护一个集合,支持如下几种操作: “I x”,插入一个数x; “Q x”,询问数x是否在集合中出现过; 现在要进行N次操作,对于每个询问操作输出对应的结果。 ### 输入格式 ### 第一行包含整数N,表示操作数量。 接下来N行,每行包含一个操作指令,操作指令为”I x”,”Q x”中的一种。 ### 输出格式 ### 对于每个询问指令“Q x”,输出一个询问结果,如果x在集合中出现过,则输出“Yes”,否则输出“No”。 每个结果占一行。 ### 数据范围 ### **1 ≤ N ≤ 1 0 5 10^5 105 − 1 0 9 −10^9 −109 ≤ x ≤ 1 0 9 10^9 109** ### 输入样例 ### > **5 > I 1 > I 2 > I 3 > Q 2 > Q 5** ### 输出样例 ### > **Yes > No** ### 解题代码 ### #include<iostream> #include<cstring> using namespace std; const int N = 100003; // 要取模的数最好是一个质数,因为这样冲突的概率会最小 int h[N], e[N], ne[N], idx; void insert(int x) { int k = (x % N + N) % N; // k 为哈希值,用这种方法可以将 x % N 的余数从负数变成正数 // 使用头插法将当前的点插到 h[K] 上 e[idx] = x; ne[idx] = h[k]; h[k] = idx++; } bool find(int x) { int k = (x % N + N) % N; for (int i = h[k]; i != -1; i = ne[i]) { if (e[i] == x) return true; } return false; } int main() { int n; cin >> n; memset(h, -1, sizeof h); // 将 h[] 数组初始化为 -1, -1 表示空指针 while (n--) { char op[2]; int x; scanf("%s%d", op, &x); if (op[0] == 'I') insert(x); else { if (find(x)) puts("Yes"); else puts("No"); } } return 0; } -------------------- # 开放寻址法 # ## 简介 ## 开放寻址法只需要开一个数组即可,但是要注意这个数组的长度一般是数据个数的 **2 ~ 3 倍**,保证可以存下所有的数据,初始状态下数组的赋一个数据范围之外的值表示当前位置为 **null**,也可以使用一个特殊的标志,但是要注意不能是数据范围以内的值。 开放寻址法的重点是寻找元素 **x** 的位置。首先设计哈希函数,通过哈希函数 f ( x ) = k f(x) = k f(x)=k 得到哈希值 **k**,如果当前对应的 **h\[k\] != null && h\[k\] != x**,说明当前的位置有数值,那么就应该寻找下一个位置 **h\[k + 1\]**,一直寻找下去,如果找到最后也没有找到合适的位置那么就再从头开始找。如果有 **x** 那么就返回其位置,否则就返回应该插入的位置。 ## 查找操作 ## int find(int x) { int k = (x % N + N) % N; while (h[k] != null && h[k] != x) { k++; if (k == N) k = 0; } return k; } ## 完整代码 ## #include<iostream> #include<cstring> using namespace std; const int N = 200003, null = 1e9 + 10; // 开两倍大的数组 // 要取模的数最好是一个质数,因为这样冲突的概率会最小 int h[N]; int find(int x) { int k = (x % N + N) % N; while (h[k] != null && h[k] != x) { k++; if (k == N) k = 0; } return k; } int main() { int n; cin >> n; for (int i = 0; i < N; i++) h[i] = null; while (n--) { char op[2]; int x, k; scanf("%s%d", op, &x); k = find(x); if (op[0] == 'I') h[k] = x; else { if (h[k] == x) puts("Yes"); else puts("No"); } } return 0; } -------------------- > 未完待续,持续更新中…… > ![2021021819145187.png][] [Link 1]: https://ac-fun.blog.csdn.net/article/details/113837773 [https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/ [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221024/fe5ecb56afb44c0c9bff166ea1b97ebd.png [AcWing 840.]: https://www.acwing.com/problem/content/description/842/ [2021021819145187.png]: /images/20221024/070d8bea51f94ee6846a8b7f6391a96e.png
相关 哈希表 上一篇博客:[静态链表的介绍及实现][Link 1] > 写在前面:大家好!我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的 ╰半夏微凉°/ 2022年10月30日 07:24/ 0 赞/ 184 阅读
相关 哈希表 ![Center][] [Center]: /images/20220731/1379dbdc6efb4a42a0b011f0b3aa4455.png 「爱情、让人受尽委屈。」/ 2022年08月14日 04:56/ 0 赞/ 162 阅读
相关 哈希表 什么是哈希表 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的[数据结构][Link 1]。也就是说,它通过把关键码 悠悠/ 2022年07月15日 12:14/ 0 赞/ 177 阅读
相关 哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速 系统管理员/ 2022年06月10日 01:26/ 0 赞/ 234 阅读
相关 哈希表 我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键 快来打我*/ 2022年06月05日 02:20/ 0 赞/ 331 阅读
相关 哈希表 1. 什么是哈希表 我们先来做个题(leetCode上387题) ![70][] public class Solution_387 { 朱雀/ 2022年05月16日 10:11/ 0 赞/ 274 阅读
相关 哈希表 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0 今天药忘吃喽~/ 2022年02月01日 14:36/ 0 赞/ 378 阅读
相关 【哈希表】 char FirstNotRepeatingChar(char pString) { // invalid input if(! r囧r小猫/ 2022年01月06日 11:33/ 0 赞/ 301 阅读
相关 哈希表 一、简介 如果所有的键都是小整数,那么我们可以用一个数组来实现无序的符号表,将键作为数组的索引i而数组中i(键)处储存的就是对应的值。 这样就可以快速地访问任意键的值, 旧城等待,/ 2021年12月22日 01:21/ 0 赞/ 374 阅读
相关 哈希表 【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na 傷城~/ 2021年08月11日 17:13/ 0 赞/ 528 阅读
还没有评论,来说两句吧...