阅读 7950

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

前言

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

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

公众号前端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位操作数的位操作来实现的。

  1. MD5

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

  1. 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题目关于哈希表的,难度从简单到困难👇


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

两数之和⭐

链接: 两数之和

给定一个整数数组 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。


请注意,你的答案必须是 子串 的长度,"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近期梳理的文章(感谢掘友的鼓励与支持🌹🌹🌹):