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

迈不过友情╰ 2023-06-23 07:52 5阅读 0赞

点击蓝色 “五分钟学算法” 关注我哦!

加个 “星标” ，算法动画喂饱你！

![format_png][]

作者 | 小鹿

来源 | 小鹿动画学编程

写在前边

![format_png 1][]

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

![format_png 2][]

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

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

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

![format_png 4][]

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

思维导图

![format_png 1][]

![format_png 5][]

什么是散列表？

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

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

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

如何实现散列表？

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

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

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

![format_png 6][]

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

哈希函数

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

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

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

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

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

什么是哈希冲突？

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

![format_png 7][]

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

哈希冲突的解决办法

我们共有两种解决办法，**开放寻址法**和**拉链法**（又叫链表法）。

***5.1***

开发寻址法

![format_png 8][]

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

**线性探测**

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

![format_png 9][]

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

![format_png 10][]

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

![format_png 11][]

**二次探测**

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

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

***5.2***

拉链法

![format_png 8][]

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

![format_png 12][]

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

![format_png 13][]

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

小结

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

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

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

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 14][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9NVVZVSEZpYmliZ0Q4Q2JqaWM0ZEduVGljNTJKR0NOTkVSbzdib2FtRzYyaWNHU2lidnNxSmtQNEZaUUQ5Nmw5RXlMcFhlcU5neWNVNUdpYlBHaWIwVXkwbW1PczdBLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEVk9VZ1Roa2g3QXR3aWE2eE1ZMkNuWWdQaWMxWUtpYkVieWlhbTFUclI0a29pYVhmUXJYMmU1eXphT0EvNjQwP3d4X2ZtdD1wbmc?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yZXMud3gucXEuY29tL21wcmVzL2h0bWxlZGl0aW9uL2ltYWdlcy9pY29uL2NvbW1vbi9lbW90aW9uX3BhbmVsL3NtaWxleS9zbWlsZXlfMzIucG5n?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEbDlraWJYR3V0UndGaWJza2RuTWxwZzBSZGgzWHJ0d1AzYjltZ3ZLT2dqZGljclI5bjdVb1ppYkYxUS82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEa0taOGdBTXZRMmRDR3Y3cVdSVzRpY2p6b0FOZTkwd3FDUVFUVmtZRktIck0zYUx2RkpaY1VGUS82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEbFZZcmVVR09Sc3dwaGJmWFA4aWFCcnAzY20zMmdDWGsxT1UxWGpITGdXdDIwWUp0R0hqam5Wdy82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VESFRDM2lidHJSdmlibEtZV043V3hZalJGOXJPb29Ma3FCc0hramljRUsxMlJFMk52aWFUTzVnSGQ1US82NDA_d3hfZm10PWdpZg?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi95bjNZVHZPS0tpYmhxbHFEd1dvejlQUVA1RWdxVlNBUGljSGZ1MGNBTVRVcmFYRW9CTWNtZlVpYWhaMW1pYXByVVN3RU9BQ0tORFRJdE1ON2dpYXNzWlJaOEVBLzY0MD93eF9mbXQ9Z2lm?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEeW1zNXRVTWFpYjcyak8zaWE3c2YwRFFDTzV0aWNaZUZXaWFESm9naWIwUjRCYThWTnZXUzFTeXNKbncvNjQwP3d4X2ZtdD1naWY?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VESndPU0dVeElPdDBTODRpYjBLZ3dSTUdmdDRWTURGVWlhRGlhSGtNM3JnMWQ1aWFZMGljSFd4RGljU3RRLzY0MD93eF9mbXQ9Z2lm?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEYVZhN3ZhUU5ET25zZmx3VGtiVkJORlBpY2NtbDZyQ0FWZ3lLMUh1blB1djhRc1BLUExDcTJhUS82NDA_d3hfZm10PWdpZg?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEVkt3YW1EUWlibVFkVFFkUUc2NzR1NFlSbHJiNWJGWmVFdzVKT093NmtJT2VYNUJ1aGlhY2NZWUEvNjQwP3d4X2ZtdD1wbmc?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXQwdXpwS1ZoOVdvMWJ4OEVkZG1pY1VEcmxLMzhWNXh0V3dYZGh5U0NleFVtYnhkdXU4c2ZpY2dxTkdXa0VvNUJOaWJoN2IwNFFpYVppYmtrUS82NDA_d3hfZm10PWdpZg?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png