哈希表（HashTable）

Hash Table，也叫哈希表，是数组的一种扩展

举例1：1-10号选手，使用数组，下标key：1-10，value：选手信息
举例2：051167编号，05年级，11班级，67选手号，编号不能直接作为下标，我们可以取后两位作为数组下标

1
2
3
4
5
6
7
int hash(String key) {
  // 获取后两位字符
  string lastTwoChars = key.substr(length-2, length);
  // 将后两位字符转换为整数
  int hashValue = convert lastTwoChas to int-type;
  return hashValue;
}

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

key —> hash(key) —> table下标

Hash函数计算所得的Hash值是一个索引，并不代表索引下所存储的数据

三点散列函数设计的基本要求：

  • 散列函数计算得到的散列值是一个非负整数；
  • 如果 key1 = key2，那 hash(key1) == hash(key2)；
  • 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

常用的散列冲突解决方法有两类

开放寻址法（open addressing）

链表法（chaining）

开放寻址法

线性探测

如果散列值，即存储位置已经被占用，我们就从当前位置开始，依次往后查找，直到找到位置。在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。（这里比较的是key，因为存的是key+value）

散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。对于使用线性探测法解决冲突的散列表，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。

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

对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法，二次探测（Quadratic probing）和双重散列（Double hashing）。

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

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

链表法

对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

时间复杂度 = 查找O(k)+插入O(1) = O(k)

思考题：

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

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

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

可以将10万条访问日志存入散列表，其中key为URL，value初始值为0。 当第一条URL存入散列表，再有相同的URL存入会产生散列冲突。此时，再比较key是否相同。如果key相同，则是同一个URL，将相应的value++；如果key不相同，则存入链表下一个位置。 可以在外部将最大值K给记录下来。插入完成以后，就可以取得当前URL的出现次数的范围即0-K。 根据K的大小选取相应的算法。如果K值不大，可以采用桶排序。如果K值很大，可采用快排。 为什么使用散列表进行存储： 散列表存储完成以后，已经对URL完成了去重操作，同时拿到了最大次数K，根据K选择合适的排序算法。 时间复杂度分析： 10万条URL存入散列表，时间复杂度为O(n)。 桶排序，时间复杂度为O(n)。 快排，时间复杂度为O(nlogn)。（需要注意的是，范围不一定是0-k，得看最大值和最小值的差值，差值比较小的话可以用桶排序）

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

以第一个字符串数组构建散列表，key 为字符串，value 为随便存个数据比如1。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 能取到1，说明存在相同字符串。时间复杂度 O(N)。

装载因子过大了怎么办？

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。

如何避免低效的扩容？

虽然平时很快，但是扩容那一次就很慢，这也是不能忍受的

我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

这期间的查询操作怎么来做呢？对于查询操作，为了兼容了新、老散列表中的数据，我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。

这种实现方式，任何情况下，插入一个数据的时间复杂度都是 O(1)。

如何选择冲突解决方法？

开放寻址法

优点：散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。

缺点：删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

总结一下，当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

数据量越大，浪费的空间越大

链表法

对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

如果我们存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4 个字节或者 8 个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。

我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。

总结一下，基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

回顾LRU算法

我们需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，我们就直接将链表头部的结点删除。当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表的尾部；如果找到了，我们就把它移动到链表的尾部。因为查找数据需要遍历链表，所以单纯用链表实现的 LRU 缓存淘汰算法的时间复杂很高，是 O(n)。

一个缓存（cache）系统主要包含下面这几个操作：

  • 往缓存中添加一个数据；
  • 从缓存中删除一个数据；
  • 在缓存中查找一个数据。

这三个操作都要涉及“查找”操作，如果单纯地采用链表的话，时间复杂度只能是 O(n)。

如果我们将散列表和链表两种数据结构组合使用，可以将这三个操作的时间复杂度都降低到 O(1)。

  • 往缓存中添加一个数据；
    散列表中查找数据的时间复杂度接近 O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找到数据之后，我们还需要将它移动到双向链表的尾部。这里移动到双向链表的尾部之后，节点在哈希表中的位置并不会改变，所以这里不会导致哈希算法失效，这点需要明确。 具体来说就是 hnext 指针没有改变，只改变 next 指针

  • 从缓存中删除一个数据；
    借助散列表，我们可以在 O(1) 时间复杂度里找到要删除的结点。因为我们的链表是双向链表，双向链表可以通过前驱指针 O(1) 时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要 O(1) 的时间复杂度。

  • 在缓存中查找一个数据。
    需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾部。插入尾部这个操作，需要记录双向链表的尾部结点。

这整个过程涉及的查找操作都可以通过散列表来完成。其他的操作，比如删除头结点、链表尾部插入数据等，都可以在 O(1) 的时间复杂度内完成。所以，这三个操作的时间复杂度都是 O(1)。

Java LinkedHashMap

LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。

如果把双向链表改成单链表，还能否正常工作呢？为什么呢？

效率上已经明显降低，在单链表中没有前去指针，当我们要删除某一个节点的时候，需要重新遍历一次链表，时间复杂度为O(n).

如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：

1.根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；
2.查找积分在某个区间的猎头 ID 列表；
3.查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。

1）ID 在散列表中所以可以 O(1) 查找到这个猎头；
2）积分以跳表存储，跳表支持区间查询；
3）这点根据目前学习的知识暂时无法实现（只能顺序查找了，O(n)）