「算法与数据结构」带你看哈希算法之美

[daydaylee1227]

前言

最近在某面经上，看到关于哈希表相关的问题，对这个数据结构感兴趣，于是就有了这篇文章。

如果你经常听到哈希算法，哈希表，哈希冲突,但又是有点模棱两可的概念，说不定读完本文，对你些许有点帮助。

公众号前端UpUp，回复哈希，即可获取脑图。

联系👉TianTianUp，遇到问题的话，可以联系作者噢，愿意陪你一起学习一起探讨问题。

脑图👇

主要围绕这几个方面介绍👇

• 哈希概念介绍
• 哈希函数
• 哈希表
• 如何解决哈希冲突
• 哈希应用
• leetcode哈希表实践

---

基本介绍

可能你听过散列表，散列函数，它们跟哈希表，哈希函数是一个概念，接下来我就以哈希这两个关键字来梳理。

哈希概念

借用一段话来描述哈希的概念👇

散列（hashing）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。也译为散列。旧译哈希（误以为是人名而采用了音译）。它也常用作一种资讯安全的实作方法，由一串资料中经过散列算法（Hashing algorithms）计算出来的资料指纹（data fingerprint），经常用来识别档案与资料是否有被窜改，以保证档案与资料确实是由原创者所提供。 ----Wikipedia

总结的话，我的理解就是将任意数量的数据通过哈希算法得到一个固定的结果，这样子我们查找某个键的话，速度也大大提升，当然了，输入数据发生改变的话，则哈希也会发现改变。

哈希函数

根据设定的哈希函数H（key）和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。

常见的hash算法👇

1. MD4

MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（消息摘要） 的缩写。它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。

2. MD5

　MD5（RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

3. SHA-1及其他

SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。

哈希表

什么是哈希表，大概说的意思就是(Hash table，也叫散列表)，它是通过hash算法得来的，通常而言，是一个固定长度的数组。

假设关键字为value,那么其值存在与hash(value)的存储位置上，不需要比较就可以直接拿到所查记录，称这个对应关系f为散列函数，按这个思想建立的表为散列表。

总的来说，哈希表就是一种映射关系的表，你可以根据这个映射关系由键（关键字）找到值。

---

如何解决哈希冲突

首先我们的清楚啥是哈希冲突👇

由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。

解决方法有哪些呢👇

• 链地址法
• 开放地址法

链地址法

每个数组单元中储存的不再是单个数据，而是一个链条，用的更多，java的
HashMap，它解决hash冲突使用就是链地址法。

从这张图上来看的话，就很好理解它的这种思路了，一般而言，链表的长度也是规定最长为8，具体为什么，有兴趣的小伙伴可以去深入了解。

---

开放地址法

这种思路解决冲突的思路👉寻找空白的单元格来添加重复的数据

那么这种方法有具体的探测三种方法👇

• 线性试探法
• 二次探测
• 再哈希法

线性探测法

线性探测法的地址增量di = 1, 2, ... , m-1，其中，i为探测次数。该方法一次探测下一个地址，知道有空的地址后插入，若整个空间都找不到空余的地址，则产生溢出。

二次探测

二次探测法的地址增量序列为 di = 2， -4， 8， -16，… ， q^2, -q^2 (q <= m/2)。二次探测能有效避免“聚集”现象，但是不能够探测到哈希表上所有的存储单元，但是至少能够探测到一半。

再哈希法

把关键字用另外一个哈希函数，再做一次哈希化，用这次哈希化的结果作为步长。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(注意：在这个方法里面是把元素分开两个表来存储)。

---

哈希应用

哈希算法有哪些应用场景呢，这里梳理几个👇

安全加密

日常用户密码加密通常使用的都是 md5、sha等哈希函数，因为不可逆，而且微小的区别加密之后的结果差距很大，所以安全性更好。

唯一标识

比如 URL 字段或者图片字段要求不能重复，这个时候就可以通过对相应字段值做 md5 处理，将数据统一为 32 位长度从数据库索引构建和查询角度效果更好，此外，还可以对文件之类的二进制数据做 md5 处理，作为唯一标识，这样判定重复文件的时候更快捷。

数据校验

比如从网上下载的很多文件（尤其是P2P站点资源），都会包含一个 MD5 值，用于校验下载数据的完整性，避免数据在中途被劫持篡改。

---

3个例子

对哈希表数据结构有了一定的认识后，接下来，通过一定的题量来练习，下午准备了5道leetcode题目关于哈希表的，难度从简单到困难👇

• 两数之和⭐
• 有效的字母异位词⭐
• 无重复字符的最长子串⭐⭐
• 前K个高频单词⭐⭐
• 原子的数量⭐⭐⭐

---

接下来，我们就以三题为例子，来看看哈希表在题目中该这么应用👇

两数之和⭐

链接： 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

这题最简单做法就是O(n*n)复杂度，在这里，我们有考虑使用Map来降低时间复杂度，题目要求答案返回的是下标，所以我们Map可以做一个映射，将当前的值，与下标index做映射。

代码点这里☑️

---

无重复字符的最长子串⭐⭐

链接：无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

暴力解法时间复杂度较高，会达到 O(n^2)，那么如何来降低时间复杂度呢👇

• 滑动窗口来降低时间复杂度
• 定义一个map数据结构，维护这么一个结构（key,index），key值就是字符，index表示的就是第几个字符。
• 滑动窗口的话，我们需要维护的就是一个start开始位置，end结束位置。
• end指针不断向后走，当遇到区间[start,end]相同的字符时，我们就需要重新跟新start指针，并且把此时的答案ans更新即可。

代码👇

代码点这里☑️

---

前K个高频单词⭐⭐

链接：前K个高频单词

---

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

注意：

假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。

扩展练习：

尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 需要求的前k个出现次数最多的，那么我们只需要统计次数
• map数据结构维护（str,count），str表示的是对于的字符串，count表示的是出现次数
• 每次只需要判断是否出现，出现的话，在count+1,没有出现，将它置为1
• 最后通过排序，即可拿到前k个数。

代码点这里☑️

---

希望这篇文章介绍哈希表这个数据结构而言，对你算是抛砖引玉吧。

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话：

1. 点赞支持下吧，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
2. 关注公众号前端UpUp，联系作者，我们一起学习一起进步。
3. 觉得不错的话，也可以阅读TianTian近期梳理的文章（感谢掘友的鼓励与支持🌹🌹🌹）：
   • 「算法与数据结构」一张脑图带你看动态规划算法之美（370+👍）
   • 「算法与数据结构」DFS和BFS算法之美(240+👍)
   • 「算法与数据结构」梳理6大排序算法(220+👍)