目录介绍

  • 01.前沿介绍
  • 02.LRU缓存淘汰算法
  • 03.Redis有序集合
  • 04.LinkedHashMap
  • 05.内容小结

好消息

  • 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.前沿介绍

  • 散列表和链表，经常会被放在一起使用，在链表那一节，我们讲到，LRU淘汰算法的时间复杂度是O(n)，当时我也提到，通过散列表可以将这个时间复杂度降低到O(1)。
  • 跳表那一节，我提到Redis的有序集合是使用跳表来实现了，跳表可以卸任一种改进版的链表。Redis的有序集合不仅使用了跳表，还用到了散列表。
  • 除此之外，Java中LinkedHashmap也用到了散列表和链表两种结构。今天，我们来看看，在这几个问题中，散列表和链表都是如何组合起来使用的，以及为什么散列表和链表经常会放到一块使用。

02.LRU缓存淘汰算法

  • 首先，回顾下当时我们是如何通过链表实现LRU缓存淘汰算法的。我们需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，我们就直接将链表头部结点删除。
  • 当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表的尾部；如果找到了，就把它移动到链表的尾部。因为查找数据需要遍历链表，所以单纯用链表实现LRU缓存淘汰自满的时间复杂度很高，是O(n)。
  • 实际上，一个缓存（cache）系统主要包含下面这几个操作：
    • 往缓存中添加一个数据；
    • 从缓存中删除一个数据；
    • 在缓存中查找一个数据。
  • 这三个操作都涉及“查找”操作，如果单纯地采用链表的话，时间复杂度只能是O(n)。如果我们将散列表和链表两种数据结构组合使用，可以将这三个操作的时间复杂度都降低到O(1)。具体的结构就是下面这个样子：
    • image
      image
  • 我们使用双向链表存储的数据，链表中的每个结点处理存储数据（data）、前驱指针（prev）、后继指针（next）之外，还增加了一个特殊的字段hnext。这个hnext有什么用呢？
  • 因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中，hnext指针是为了将结点串在散列表的拉链中。
  • 了解这个散列表和双向链表的组合存储结构之后，我们再来看，前面讲到的缓存的三个操作，是如何做到时间复杂度是O(1)的？
  • 首先，我们来看如何查找一个数据。在前面讲过，散列表中查找数据的时间复杂度接近O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找到数据之后，我们还需要将它移动到双向链表的尾部。
  • 其次，我们看如何删除一个数据。我们需要找到数据所在结点，然后将结点删除。借助散列表，我们可以在O(1)时间复杂度里找到要删除的结点。因为我们的链表是双向的，双向链表可以指针O(1)时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要O(1)的时间复杂度。
  • 最后，我们来看如何添加一个数据。添加数据到缓存稍微有点麻烦，我们需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果没有满，直接将数据放到链表的尾部，否则先将链表头部的结点删除，然后再将数据放到链表的尾部。
  • 这整个过程涉及的查找操作都可以散列表来完成。其他的操作，比如删除头部结点、链表尾部斤数据等，都可以在O(1)的时间复杂度内完成。所以，这三个操作的时间复杂度都是O(1)到此，我们就通过散列表和双向链表的组合使用，实现一个高效的、支持LRU缓存淘汰算法的缓存系统原型。

03.Redis有序集合

  • 在跳表那一节，讲到有序集合的操作时，我稍稍做了简化。实际上，在有序集合中，每个成员有两个重要的属性，key(键值)和score(分值)。我们不仅会通过score来查找数据，还会通过key来查找数据。
  • 举下例子，比如用户积分排行榜有这样一个功能：我们可以通过用户的ID来查找积分信息，也可能通过积分区间来查找用户ID或者姓名信息。这里包含ID、姓名和积分的用户信息，就是成员对象，用户ID就是key，积分就是score。
  • 所以，如果我们细化一下Redis有序集合的操作，那就是下面这样：
    • 添加一具成员对象；
    • 按照键值来删除一个成员对象；
    • 按照键值来查找一个成员对象；
    • 按照分值区间查找数据，比如查找积分在[100,356]之间的对象；
    • 按照分值从小到大排序成员变量；
  • 如果我们仅仅按照分值将成员组织成跳表结构，那按照键值来删除、查询成员对象就会很慢，解决方法与LRU缓存淘汰算法的解决方法类似。我们可以再按照键值构建一个散列表，这样按照key来删除、查找一个成员对象的时间复杂度就变成O(1)。现时借助跳表结构，其他操作也非常高效。
  • 实际上，Redis有序集合的操作还有另外一类，也就是查找成员对象的排名（Rank）或者根据排名区间查找成员。这个功能单纯用刚刚讲的这种组合结构就无法高效实现了。

04.LinkedHashMap

  • 实际上，LinkedHashMap中“Linked"并不仅仅代表它是通过链表法解决散列冲突的。关于这一点，在我是初学者的时候，也误解了很久。
  • 我们先来看一段代码。你觉得这段代码会以什么样的顺序打印3，1，5，2这几个key呢？原因又是什么呢？
    Map<Integer,Integer> testMap = new LinkedHashMap<Integer, Integer>();
testMap.put(3, 11);
testMap.put(1, 12);
testMap.put(5, 23);
testMap.put(2, 22);
for(Map.Entry<Integer,Integer> e : testMap.entrySet()) {
	System.out.println(e.getKey());
}
  • 这时直接告诉你答案，找钱的顺序是3，1，5，2，也就是会按插入的顺序来打印。你有没有感觉到奇怪？散列表中数据是经过散列函数打乱之后无规律的，这里是如何实现按照数据的插入顺序来遍历打印的呢？
  • LinkedHashMap是通过散列表和链表组合在一起实现的。实际上，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。
     //  10 初始大小，0.75是装载因子， true 是表示按照访问时间顺序
Map<Integer,Integer> testMap = new LinkedHashMap<Integer, Integer>(10,0.75f,true);
testMap.put(3, 11);
testMap.put(1, 12);
testMap.put(5, 23);
testMap.put(2, 22);

testMap.put(3, 26);
testMap.get(5);
for(Map.Entry<Integer,Integer> e : testMap.entrySet()) {
	System.out.println(e.getKey());
}
  • 这段代码打印的结果是1，2，3，5。来分析下为什么会是这样。
  • 每次调用put()函数，往LinkeHashMap中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样：
    • image
      image
  • 在第8代码中，再次将键值为3的数据放入LinkedhashMap的时候，会先找这个键值是否已经有了，然后，再将已经存在的（3，11）删除，并且将新的（3，26）放到链表的尾部。所以，这个时候链表中的数据就是下面这样：
    • image
      image
  • 当第9行代码访问到key为5的数据时，我们将被访问的数据移动到链表的尾部。所以，第9行代码之后，链表中的数据是下面这样：
    • image
      image
  • 所以，最后打印出来的数据是1，2，3，5。从上面的分析，你有没有发现，按照访问时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统？实际上，它们两个的实现的原理也是一模一样的。
  • 总结下，LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap中的“linked”实际上是指双向链表，并非指用链表法解决散列冲突。

05.内容小结

  • 散列表这各数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就是说，它无法支持按照顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。
  • 因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按照顺序遍历散列表中的数据时，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表（或是跳表）结合在一起使用。

参考文献

  • 极客时间，王争大神，数据结构和算法之美

01.关于博客汇总链接

02.关于我的博客

  • github：https://github.com/yangchong211
  • 知乎：https://www.zhihu.com/people/yczbj/activities
  • 简书：http://www.jianshu.com/u/b7b2c6ed9284
  • csdn：http://my.csdn.net/m0_37700275
  • 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
  • 开源中国：https://my.oschina.net/zbj1618/blog
  • 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
  • 邮箱：yangchong211@163.com
  • 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
  • segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
  • 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e
贡献者: yangchong211