1. 散列思想
散列表利用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
散列
2. 散列函数
散列函数定义为 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
该如何构造散列函数？有三点基本要求：
- 散列函数计算得到的散列值是一个非负整数；
- 如果 key1 = key2，那 hash(key1) == hash(key2)；
- 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
第一、二点很好理解，第三点实际上几乎不可能，因为它无法避免散列冲突。
3. 散列冲突
解决方法：开放寻址法和链表法。
开放寻址法
核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。探测方法有线形探测、二次探测和双重散列。
开放寻址法
线性探测
- 插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
- 查找数据：通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等。如果相等，则说明就是要找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。
- 删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为 deleted，当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
结论：最坏的时间复杂度为O(n)
二次探测
线性探测每次探测的步长为1，即在数组中一个个探测，而二次探测的步长变为原来的平方。
双重散列
使用一组散列函数，直到找到空闲位置为止。
散列表用装载因子（load factor）来表示空位的多少，计算公式是：
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
链表法
更加常用，比开放寻址法简单。
在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
链表法
- 插入数据：当插入的时候，通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以时间复杂度为 O(1)。
- 查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数 k=n/m，其中 n 表示散列表中数据的个数，m 表示散列表中槽的个数，所以时间复杂度为 O(k)。
课后思考
- Word 文档中单词拼写检查功能是如何实现的？
- 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
- 有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？
