散列表及其应用

Word文档中的单词拼写检查功能是如何实现的

想知道这个答案，需要知道散列表这个数据结构，下面就来谈谈散列表的相关知识

1. 散列思想

先搞清楚几个相关概念：Hash Table 等于 哈希表，也等于散列表，这3个概念是相同的

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

学校举办比赛，参赛编号由以下6位组成：

其中编号就是参赛队员的号码，那么我们怎么把这些数据存到数组中？我们可以截取编号的最后2位作为数组下标来读取数据，
这就是散列思想:

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性，存取元素的过程都基于下图：

2. 散列函数

散列函数设计要求：

1. 散列函数计算得到的散列值是一个非负整数；因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数

2. 如果 key1 = key2，那 hash(key1) == hash(key2)；相同的 key，经过散列函数得到的散列值也应该是相同的**。**

3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率

3. 解决散列冲突

3.1 开放寻址法

如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入

3.1.1 线性探测

线性探测：当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

举个例子，黄色表示没有数据，橙色表示有数据：

X经过hash函数得到7，但是7的位置已经有数据了，所以我们依次往后找，发现后面也满了，那么从头开始找，所以找到了2这个位置插入

插入过程如上，那么查找过程怎么样呢？其实也差不多=====>
我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。

再说一下删除，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。因为在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。所以我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。

线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。

3.1.2 二次探测

所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……

3.1.3 双重散列

我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

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

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

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

3.2 链表法

在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中

4. 一些应用

Word 文档中单词拼写检查功能是如何实现的

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10** 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB**。对于现在的计算机来说，这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。借助散列表这种数据结构，我们就可以轻松实现快速判断是否存在拼写错误。

假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序

遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。
如果 K 不是很大，可以使用桶排序，时间复杂度 O(N)。如果 K 非常大（比如大于 10 万），就使用快速排序，复杂度 O(NlogN)。

有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串

以第一个字符串数组构建散列表，key 为字符串，value 为出现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，说明存在相同字符串。时间复杂度 O(N)

5. 关于HashMap的一些扩展

5.1 JDK1.8中Hash冲突的解决

5.2 哈希函数

5.3 生成key的哈希值

那么Long和Double类型的呢：