前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课
以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。
散列表和链表经常会被放在一起使用，这是为什么呢？它们是如何组合起来使用的呢？
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()函数执行时，都会将数据添加到链表的尾部，所以，前四个操作完成之后，链表的数据是下面这样的：
image.png
在第 8 行代码中，再次将键值为 3 的数据放入到 LinkedHashMap 的时候，会先查找这个键值是否已经有了，然后，再将已经存在的 (3,11) 删除，并且将新的 (3,26) 放到链表的尾部。所以，这个时候链表中的数据就是下面这样：
image.png
当第 9 行代码访问到 key 为 5 的数据的时候，我们将被访问到的数据移动到链表的尾部。所以，第 9 行代码之后，链表中的数据是下面这样：
image.png
最后打印出来的数据就是 1 2 3 5 了，LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统，实现原理是一模一样的。
LinkedHashMap 是通过双向链表 + 散列表这两种数据结构组合实现的。Linked 指的是双向链表。
网友评论