数据结构与算法之美-散列表(下)

2021-05-21 本文已影响0人沉江小鱼

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

散列表和链表经常会被放在一起使用，这是为什么呢？它们是如何组合起来使用的呢？

1. 散列表和链表为什么经常组合使用？

散列表虽然支持非常高效的插入、删除、查找操作，但是散列表中的数据都是散列函数打乱之后无规律存储的，想要顺序遍历的话肯定不行，所以我们将散列表和链表（跳表）结合在一起使用，这样就可以按顺序遍历散列表中的数据了。

2. 如何组合使用

2.1 LRU 缓存淘汰算法

单链表实现 LRU 缓存淘汰算法：
当要缓存某个数据的时候，需要现在链表中查找这个数据，如果没有找到，则将数据放到链表尾部；
如果找到了，则将其移动到链表尾部。这样查找数据需要遍历链表，所以单纯使用链表实现的 LRU 缓存淘汰算法的时间复杂度就是 O(n)。

一个缓存系统主要包含以下操作：

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

这三个操作都涉及到“查找”操作，如果只使用单链表的话，时间复杂度只能是 O(n)，所以我们可以使用散列表查询时间复杂度为O(1)的特点，将散列表和链表两种数据结构组合使用，可以将这三个操作时间复杂度都降低为 O(1)，如下图：

image.png

可以看到上图中时散列表 + 双向链表的组合，链表中的每个结点有存储数据 data、前驱指针 prev、后继指针 next、hnext指针。双向链表的 prev 和 next 指针时纵向指针，维护的是数据缓存的时间线，将结点串在双向链表中，hnext指针时为了将结点串在散列表的拉链中。

查找一个数据
散列表中查找数据的时间复杂度接近 O(1)，所以我们很快找到数据之后，还需要将它移动到双向链表的尾部，这里只是改变结点的 prev 和 next，结点在哈希表中的位置不会改变，hnext指针不会改变。

这里可能需要维护一个双向链表的尾指针，这样才能快速的将结点移动到链表的尾部。

删除一个数据
找到要删除的那个数据结点，然后通过该结点的 prev 获取前驱结点，删除指定结点，同时也需要从散列表的拉链中删除。
添加一个数据
如果数据已经在缓存中，需要将其移动到双向链表的尾部；
如果不在其中，则看缓存是否满了，如果满了，则需要先将双向链表头部的结点删除，然后再将数据放到链表尾部；如果没满，则直接将数据放到链表尾部。

YYKit中的 YYMemoryCache 就是使用这种结构实现的，有时间要去看下源码，学习一下。

2.2 Redis 有序集合

比如用户积分排行榜功能，我们可以通过用户 ID 查找积分信息，也可以通过积分区间来查找用户 ID 或者姓名信息。这里包含 ID、姓名和积分的用户信息，就是成员对象，用户 ID 就是 key，积分就是 score。

细化 Redis 有序集合的操作：

添加一个成员对象
按照键值key删除一个成员对象
按照键值key查找一个成员对象
按照分值score区间查找数据，比如查找积分在[100, 356]之间的成员对象
按照分值score从小到大排序成员变量

如果只是按照分值score将成员对象组织成跳表结构，那按照键值key 来删除、查询成员对象就会很慢，所以可以再按照键值key构建一个散列表（无序的散列表，适合按照 key 值查询，效率更高），这样按照 key 来删除，查找一个成员对象的时间复杂度就变成了 O(1)，同时借助跳表结构，其他操作也很高效。

2.3 LinkedHashMap

LinkedHashMap是通过散列表 + 双向链表实现的，不仅支持按照插入顺序遍历数据，还支持按照访问顺序遍历数据。


// 10是初始大小，0.75是装载因子，true是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);

m.put(3, 26);
m.get(5);

for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}

打印结果是 1 2 3 5。

每次 put()函数执行时，都会将数据添加到链表的尾部，所以，前四个操作完成之后，链表的数据是下面这样的：