专栏首页Java那些事动画:散列表 | 文本编辑器是如何检查英文单词出错的?

动画:散列表 | 文本编辑器是如何检查英文单词出错的?

作者 | 小鹿 来源 | 小鹿动画学编程

写在前边

今天小鹿就早早起床开始正准备更新今日的文章,我熟练的敲打着键盘,突然出现了下面的情况:

咦?这编辑器查错功能竟然比我手速还快,这我就不服气了,我就开始疯狂地搜着这个编辑器快速查错功能是如何实现的

后来在网上一搜,都说用哈希表实现的,我思考着,用哈希表怎么实现的,我对这次“案件”越来越感兴趣,然后我继续深入探索哈希表“案情”背后的秘密。

功夫不负有心人,我终于在维基百科找到了想要的答案:

伴随着此次“案件”的存在疑点重重,我开始深深的陷入对散列表的思考...

思维导图

1

什么是散列表?

维基百科给我们散列表的定义对于新人来说确实有点难理解,如下:

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。 —— 维基百科

那小鹿再来给解释一波吧。何为散列表,散列表就像是我们超市的存储私人物品的存储柜,我们存储物品对应的柜子都会有对应的条形码,我们可以通过扫描条形码来打开对应的柜子。其实,这就类似于一个散列表。

2

如何实现散列表?

对于数据结构中的散列表是如何实现的呢?是不是还记得我们的两位老朋友,数组和链表。我们之前再次强调,所有的数据结构基本都是由数组和链表演变而来,散列表也不例外。

我们通过自取柜的例子,可以联想到数组,数组是通过下标来访问元素的,其实散列表就是数组的一种演变,那么散列表是如何实现的呢?

我们将自取柜的二维码称之为“”,用它来作为柜子的唯一标识。然后把二维码转化为特定柜子的映射方法叫做“散列函数”(也可以称为哈希函数)。通过映射打开对应的柜子,这个映射的值叫做“哈希值

同样,数组的下标对应的就是“键”,下标所映射到的元素就是“散列值”,这就是一个散列表。

3

哈希函数

上文中,我们提到将“键”映射为“哈希值”的函数,叫做哈希函数。那么这个函数是如何实现的呢?

对于数组演变的散列表,我们可以知道哈希函数有这么几个特点:

  • 哈希函数得到的哈希值是一个非负数的值;
  • 如果“键”相同,通过哈希函数得到的哈希值一定相同。

有的小伙伴可能会问,同一个哈希值一定是同一个“键”吗?这个问题问的好,你还真别说,还真有不是一个的可能,因为存在哈希冲突。

哈希冲突是避免不了的,就算我们项目中用到的 MD5 加密也无法避免这种情况,但能做的把这种情况概率降到最低。在我们降低概率的时候同时增加了其他的开支。有种像时间换空间,空间换时间思想的意思。

4

什么是哈希冲突?

什么是哈希冲突?举个例子,比如我们往 5 个桶里放 6 个小球,每个桶中规定只能放一个,那剩下的一个不得不放入其中一个桶中,这就是所谓的哈希冲突。

难道没有更好的方法解决哈希冲突吗?有的,但是并不能完全解决,而是通过其他的开销来降低冲突的概率。

5

哈希冲突的解决办法

我们共有两种解决办法,开放寻址法拉链法(又叫链表法)。

5.1

开发寻址法

开发寻址的法的原理就是如果我们发生了哈希冲突,也就是说通过散列函数得出的散列值相同,我们就重新探测一个位置,将数据存储。那如何进行探测呢?

线性探测

所谓的线性探测,就是一个一个的进行探测如下图动画,在散列表中插入一个元素:

查找元素也是同样的道理,如果在散列表中查找的元素和我们要查找的元素相同,则直接取出,否则通过线性探测,一个一个去查找,直到没有查找到位置。

对于删除元素呢?这就比较麻烦一点,因为我们删除元素之后,再进行插入元素或者查找元素就出现位置空缺了,无法完成正常的操作了,所以我们删除元素规定不能将元素进行真正的删除,而是做一个标记,如果查找元素,遇到该标记则继续查找。

二次探测

上边我们是进行线性查找,二次探测就是每次探测都是原来的平方探测。

这两种方式只是方式上的不同,如果散列表的空间不足时,产生的哈希冲突还是很大概率的。我们通常用一个阀值来表示散列表中剩余空间的大小,我们称这个阀值为装载因子。(装载因子 = 元素个数 / 散列表的大小)。

5.2

拉链法

我们除了开放寻址法外,我们还可以使用拉链法来解决哈希冲突,所谓的拉链法就是链表这个数据结构。

如果我们通过“键”得到的哈希值相同的时候,也就是冲突的时候,我们会在该散列表中对应的位置加一条链表,如果再冲突,我们继续往对应的链表中添加元素。

如果我们查找、删除元素的时候,得到的哈希值没有,则在对应的单链表中进行查找。

6

小结

我们上边分享了散列表的基本常识,回到我们开篇的问题上去,文本编辑器是如何检查英文单词出错的呢?

牛津词典的单词一共 75 万左右,如果不归类、不分义,常用的英语单词一共 25 万左右。假设一个单词平均占 10 个字节,25 万单词四舍五入凑个整数大约 3 M。就算是 75 万单词,也就是 8 M。我们用散列表进行存储,放到内存中。

当我们飞速的打着字时,计算机就会拿着你输入的单词去散列表中的查找,因为散列表就是数组的演变,查询一个元素的时间复杂度为O(1)。如果可以查找到,则存在该单词,就不会有报错信息。否则,提示错误,出现下滑波浪线,提示用户修改错误的单词。

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 目标检测算法之NMS后处理相关

    昨天盘点了一下目标检测算法的常见数据集还有评判标准,但目标检测过程还有一个后处理算法的重要性确常被忽略,今天我们就来盘点一下目标检测算法中的NMS相关知识吧。

    BBuf
  • 2019年,不想再当人肉跑数机了,求解放!

    有同学问:老师,我现在负责部门的数据分析,可实际就是个跑数的,每天跑来跑去也就是那些东西,感觉不到技能提升,求解放!

    接地气的陈老师
  • 目标检测算法之SSD

    昨天介绍了特征金字塔网络用于目标检测,提升了多尺度目标检测的鲁棒性,今天开始讲讲One-Stage目标检测算法中SSD算法。这个算法是我平时做工程中最常用到的,...

    BBuf
  • 人脸识别系列三 | MTCNN算法详解下篇

    上篇讲解了MTCNN算法的算法原理以及训练细节,这篇文章主要从源码实现的角度来解析一下MTCNN算法。我要解析的代码来自github的https://githu...

    BBuf
  • 目标检测算法之YOLOv1

    今天开始分享一下YOLO系列的目标检测算法,前面介绍了SSD算法和Faster-RCNN,现在公司用Faster-RCNN的似乎不是很多,主要集中在YOLO,S...

    BBuf
  • OpenCV图像处理专栏一 | 盘点常见颜色空间互转

    今天是OpenCV传统图像处理算法的第一篇,我们来盘点一下常见的6种颜色空间互转算法,并给出了一些简单的加速方案,希望可以帮助到学习OpenCV图像处理的同学。...

    BBuf
  • 《ENet》论文阅读及实现

    昨天介绍了目标检测算法之YOLOv2,但还留下一个比较大的坑没填,就是YOLOv2的损失函数解析,今天没来得及做这个工作,来解析一篇高速度的针对嵌入式端的语义分...

    BBuf
  • 人脸识别系列一 | 特征脸法

    从这里开始,我会不定期的更新一些人脸识别的有趣算法和小demo算法,源码也会开放出来,自己在学习的过程中希望也能帮助到公众号中对这方面感兴趣的小伙伴,无论是从源...

    BBuf
  • 传统企业的数字化转型项目怎么做?

    传统企业推动数字化核心难点,在于经营模式的不同。不像那些烧钱的互联网公司,花大价钱砸数据不心疼。那些还在靠买东西挣毛利的传统企业,是经不起大把烧钱的。“一个项目...

    接地气的陈老师
  • 人脸识别系列二 | FisherFace,LBPH算法及Dlib人脸检测

    前面介绍了使用特征脸法进行人脸识别,这里介绍一下OpenCV人脸识别的另外两种算法,一种是FisherFace算法,一种是LBPH算法。

    BBuf

扫码关注云+社区

领取腾讯云代金券