那些年，散列表和链表的混合双打

数组拥有下标随机访问的特点，缺点是需要连续的内存

链表不需要连续的存储的优势，不需要事先申请空间，但是访问却是线性的。

如果把两种数据结构相结合，是不是可以做到互补，弥补他们的不足，实现更好的数据结构呢？

LRU缓存淘汰算法

我们使用链表存储元素，按照访问时间的先后顺序从链表头部到尾部方向存放数据，因为缓存空间的大小有限，当空间不够时，我们就可以从链表的头部剔除一个最长时间没有访问数据。当我们添加一个数据的时候，会先在链表中先查询这个数据是否存在，如果找到了就把这个元素移动到尾部；如果这个元素在链表中不存在，这时候直接添加到尾部即可。这里面主要涉及三种操作，查询、添加和删除，链表的添加和删除操作都比较简单，这地方最容易理解，时间复杂度为 O(1)，最消耗时间就是查询操作，链表线性查询的时间复杂度为O(n)，所以我们可以在这地方做优化。我们利用散列表的特性，把链表的结点放入散列表中，这样每次查询的时间是不是也可以做到O(n)了。添加和删除如果做成单链表不易操作的话，可以使用双向链表替换掉单链表。下图有一点没做好，箭头的起始位置是那个小方格，指向的是一个完整的结点（那四个小方格）

除此之外，这个结点还需要申请一个空间，因为散列表用链表解决冲突的时候，结点需要一个后继结点指向拥有相同哈希值的下一个结点。

通过散列表和双向列表的组合，可以完成对LRU算法的基本优化。

Redis有序集合

在redis中，我们存储一个对象，这个对象有会两个属性，一个是键（key）和值（value），能通过键来查找数据，也可以通过值去查询。有序集合可以通过跳表实现，但是跳表的查询速度是O(logn)，那么查询的阶段我们是不是可以做一下优化，使用元素的键值构建一个散列表，这样查找和删除的操作的时间复杂度都会变成O(1)。

Java中的LinkedHashMap

HashMap 的底层是通过散列表这种数据结构实现的，LinkedHashMap 比 HashMap多了一个Linked链表，那么这么链表是多在哪里的呢？

Map<Integer, Integer> hashMap = new HashMap<>();
hashMap.put(2, 2);
hashMap.put(4, 4);
hashMap.put(3, 3);
hashMap.put(1, 1);
Map<Integer, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put(2, 2);
linkedHashMap.put(4, 4);
linkedHashMap.put(3, 3);
linkedHashMap.put(1, 1);
for (Map.Entry entry : hashMap.entrySet()) {
  System.out.print(entry.getKey());// 1234
}
System.out.println();
for (Map.Entry entry : linkedHashMap.entrySet()) {
  System.out.print(entry.getKey());// 2431
}

上面的输出结果为 1234和2431，是不是发现了什么不同之处。

没错，LinkedHashMap 在存放数据的时候，保证了数据放入的先后顺序。HashMap 是随机放入的，没有先后的顺序。

为什么会出现在这种情况呢？

LinkedHashMap 存放数据的地方是一个链表，所有的新添加的数据添加在链表的一头，这样就能保证数据的先后顺序不会发生变化，这里使用的是双向链表存放数据，而且对数据的的访问和获取会改变数据的先后顺序，即LinkedHashMap本身就是一个 LRU 缓存淘汰策略的实现。