第十八节-散列表（上）

散列思想

散列表利用的是数组支持下标随机访问，时间复杂度是 O(1) 的特性，所以散列表其实是数组的一种扩展，由数组演化而来。可以说如果没有数组，就没有散列表。

散列思想就是，通过散列函数，把元素的键值 (key) 映射为数组的下标 (hash(key))，然后将元素存储在数组中对应下标的位置。当我们按照键值 (key) 查找元素时，再利用同样的散列函数，将键值映射为数组下标，从对应下标的位置取数据。

散列函数

散列函数，顾名思义，它是一个函数，符合 y = f(x) 的特征。我们可以把散列函数定义为 hash(key) , 其中 key 表示元素的键值，hash(key) 表示经过散列函数计算得到的散列值。

散列函数要符合三个基本设计要求：

1. 散列函数集散得到的散列值是一个非负整数;

因为数组下标是从 0 开始的。

2. 如果 key1 = key2，那 hash(key1) == hash(key2);

相同的 key，经过散列函数映射得到的散列值也应该是相同的，这样我们才能取回存放的元素。

3. 如果 key1 != key2，那 hash(key1) != hash(key2)。

这一点是理想情况，但现实要想找到一个不同 key 对应的散列值都不一样的散列函数，几乎是不可能的。因为数组存储的空间有限，而 key 可以无限，所以总有重复的时候，即总会存在散列冲突。

散列冲突

解决散列冲突的方法很多，常用的有两类：开放寻址法和链表法。

开放寻址法

开放寻址法的核心思想就是，如果出现了散列冲突，我们就再重新探测一个空闲位置，将其插入。当删除元素时，将该位置的元素标记为 deleted 而不是直接删除。

开放寻址法比较适合小数据量，当存在冲突时，速度比链表法快一些，毕竟可以直接利用 CPU 的缓存把整个数组缓存下来， IO 时间快了很多。Java 中的 ThreadLocalMap 就用了开放寻址法。

重新探测新的位置的方法有很多，比如：

• 线性探测
• 二次探测 （二次方探测）
• 双重散列（使用一组散列函数，一个不行换另一个）

链表法

链表法比开放寻址法更加常用，散列冲突时，将冲突的元素组织成一条链表、或者变种成一棵树。删除元素时可以直接删除。

散列表应用

实现一个 Word 文档中档次的拼写检查功能

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

当用户输入某个英文单词时，我们就拿这个单词取散列表中查找，如果查到，就说明是拼写检查正确的；否者，就提示可能存在拼写错误。

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

遍历 10 万条数据，URL 作为 key，value 是访问次数，存入散列表，同时记录下最大的访问次数 K，时间复杂度是 O(n)。

如果 K 不是很大，那么进行桶排序，否则进行快排。

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

1. 以第一个数组为基础构建一个散列表，字符串作为 key，value 是一个标记。遍历第二个数组，每个字符串作为 key 往散列表中做查询，查不到的字符串存到一个 set 中，遍历结束，这个 set 中就存放着两个数组中相同的字符串。

2. 直接使用 hashset ，若是 add 失败，就是重复的。