散列表（上）：Word 文档中的单词拼写检查功能是如何实现的？

一旦我们在 Word 里输入一个错误的英文单词，它就会用标红的方式提示 拼写错误。Word 的这个单词拼写检查功能，虽然很小但却非常实用，它是如何实现的呢？

使用 散列表 可以轻松实现这个功能。

极客时间原文链接

学了散列表，才知道 hashcode 什么时候用，如果要存储的数据，在某种自定义的业务逻辑下，通过其 key 得到重复性比较低的 整数，那么就可以通过复写 hashcode()方法，来优化 HashMap 取散列值的过程。

一、散列思想

散列表的英文叫 Hash Table（终于要知道 HashTable 和 HashMap 是什么东西了）。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来，可以说，如果没有数组，就没有散列表。

首先要了解一下什么是散列函数和散列值。

例1： 假设有 89 名选手参加运动会，为了方便记录成绩，每个选手都会有自己的参赛号码。这 89 名选手的编号就是 1 到 89。我们希望通过编程实现这样一个功能，通过编号快速找到对应的选手信息。

我们可以把这 89 名选手的信息放在数组里。选手的编号是多少，该选手的信息在数组中存储的下标就是多少。

因为参赛编号跟数组下标一一对应，当我们需要查询参赛编号为 x 的选手的时候，我们只需要将下标为 x 的数组元素取出来就可以了，时间复杂度为 ○(1)。

在上述例子中，就使用到了散列的思想。因为参赛编号是自然数，并且与数组下标形成一一映射关系，所以就可以利用数组随机访问时时间复杂度为 ○(1) 的特性。

加深理解散列思想的例子2 如果编号要加上更多的信息，比如使用六位数来表示，051167，表示 5 年级，11 班，67号，这时候如何存储选手信息才能支持通过编号来快速查找选手信息呢？

我们可以截取编号的后两位作为数组下标来存储选手信息。

这就是典型的散列思想。其中，选手的编号我们叫做 键(key) 或者 关键字。用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法叫作 散列函数(或 ‘Hash函数'、‘哈希函数’)，而散列函数计算得到的值就叫做 散列值(或 ‘Hash值’、‘哈希值’)。

哈哈哈 Java 中的 hashcode 就是散列函数，用来配合基于散列的集合。像 HashSet、HashMap、HashTable 就是散列集合。

散列思想

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度为 ○(1) 的特性。

二、散列函数

顾名思义，它是一个函数，这个函数用来将 key 通过我们自定义的逻辑过程，转换成散列值。再使用散列值到数组中查找数据。

在上面学生编号的例子2中，散列函数可以如下编写：

int hash(String key){
    //获取后两位字符
    //将后两位字符转换为整数
    //返回这个整数
}

这个散列函数是比较简单的，但是如果参赛选手的编号是随机生成的 6 位数字，又或者用的是 a 到 z 之间的字符串，该如何构造散列函数呢？
散列函数设计的三点基本要求

• 散列函数计算得到的散列值一定是一个非负整数（因为要与数组的下标一一映射）
• 如果 key1 == key2，那么 hash(key1) == hash(key2)
• 如果 key1 != key2，那么 hash(key1) != hash(key2)

主要是第三点可能会出现一些问题，这个要求我们都能理解，因为如果 key != key2，但是 hash(key1) == hash(key2) 的话，那么不同的 key 值会得到相同的散列值，这明显不是我们想要的。但是，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。

著名的 MD5、SHA、CRC等哈希算法，也无法完全避免这种 散列冲突，因为数组的存储空间有限，也会加大散列冲突的概率。

所以针对散列冲突问题，需要通过其他途径来解决。

三、散列冲突

常用的散列冲突解决方法有两类，开放寻址法(open addressing) 和 链表法(chaining)。

1. 开放寻址法

核心思想，如果出现了散列冲突，就重新探测一个空闲位置，将数据插入。如何重新探测新的位置呢？

线性探测(Linear Probing)

如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，知道找到位置。

散列冲突解决方式：线性探测 线性探测过程

上述是向散列表中插入数据的过程，那么查找数据的过程是什么样的呢？
实际上，散列表的查找与插入的过程很相似。
我们通过散列函数求出要查找元素的 key 对应的散列值。然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明找到了。如果不相等，就顺序向后查找，如果遍历到数组的空闲位置，还没有找到，就说明要查找的元素不在散列表内。

第一次看到这段话的时候我是没怎么看懂的，但是在写笔记的过程中，明白了。因为在执行插入过程的时候，如果出现散列冲突（此时两个key是不同的，但是得到的散列值是相同的），那么该数据会被通过线性探测的方式，向后插入。那么当查找的时候，不同的 key 值，可能会得到相同的散列值，所以在取出元素过程中，要判断该元素是否是我们要查找的元素。如果不是的话，因为线性探测是向后插入的，所以我们也要向后去查，看有没有与目标数据匹配的元素。
那为什么遇到空闲位置，就认为散列表中无此数据呢？因为在插入的时候，我们是顺序插入的，所以数组中的数据一定是[元素1，元素2，元素3,空,空,空,空,空]，而不会是[元素1，元素2，空，空，元素3，元素4，空]这样的。

查找过程

散列表和数组一样，支持插入、查找、删除等操作。但是对于使用线性探测发解决散列冲突的散列表，删除操作稍微有些区别。我们不能单纯的把要删除的元素设置为空。为什么？

在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就认为散列表中不存在这个数据。但是如果这个数据是我们后来删除的呢？我们删除的时候把此下标的元素设置为空，那么就会导致原来的查找算法失效，本来存在的数据，会被认定为不存在。

我们可能将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，不会停下来，而是继续往后探测。

删除过程：标记deleted

所以插入的线性探测过程中，遇到 deleted，也可以直接插入。

线性探测法存在的问题

1. 当散列表中插入的数据越来越多，散列冲突发生的可能性会越来越大。
2. 当散列表中插入的数据越来越多，空闲位置会越来越少，线性探测时间会越来越久。
3. 极端情况下，我们可能要探测整个散列表，所以最坏情况下的时间复杂度为 ○(n)。

二次探测

跟线性探测很像，线性探测每次探测的步长为 1，那它探测的下标序列就是 hash(key)+0
hash(key)+1 hash(key)+2 ……。而二次探测的步长就变成了原来的 二次方，也就是 hash(key)+0 hash(key)+1² hash(key)+2²（讲道理小白的我名没觉得有什么卵用）

双重散列

意思就是不仅仅使用一个散列函数，而是一组散列函数，先用第一个散列函数计算，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

装载因子

不管哪种探测方法，当散列表空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，会尽可能保证散列表有一定比例的空闲槽位。空位的多少，用 装载因子 来表示。

散列表装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

2. 链表法

链表法是一种更加常用的散列冲突解决方法，相比开放寻址法，要简单很多。
在散列表中，每个 桶 或者 槽 会对于一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。（哈哈哈这是不是就是 HashMap）

链表法解决散列冲突

当插入的时候，只需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可。所以插入的时间复杂度是 ○(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对于的槽，然后遍历链表查找或者删除。

使用链表法解决冲突，查找或删除的时间复杂度是多少？
这两个操作偶读时间复杂度跟链表的长度 k 成正比，也就是 ○(k)。
对于散列比较均匀的散列函数，理论上讲，k = n/m。
n：散列中数据的个数
m：散列中槽的个数

四、解答开篇

image

五、课后思考

1. 假设有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
2. 有两个字符串数组，每个数组大约 10 万条字符串，如何快速找出两个数组中相同的字符串？