1、访问到的数据移动到链表的尾部。所以，第9行代码之后，链表中的数据是下面这样： 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 所以，最后打印出来的数据是1，2，3，5。从上面的分析，你有没有发现，按照访问时间排序的LinkedHashMap本身就是一个支持LRU缓存淘汰策略的缓存系统？ 实际上，它们两个的实现原理也是一模一样的。我也就不再啰嗦了。 我现在来总结一下，实际上，LinkedHashMap是通过双向链表和散列表这两
2、种数据结构组合实现的。LinkedHashMap中的“Linked”实际上是指的是双向链表，并 非指用链表法解决散列冲突。 解答开篇&内容小结 弄懂刚刚我讲的这三个例子，开篇的问题也就不言而喻了。我这里总结一下，为什么散列表和链表经常一块使用？ 散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照 某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。 因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据
3、的时候，都需要先排序，那效率势必会很低。为了解决 这个问题，我们将散列表和链表（或者跳表）结合在一起使用。 课后思考 1. 今天讲的几个散列表和链表结合使用的例子里，我们用的都是双向链表。如果把双向链表改成单链表，还能否正常工作呢？为什么呢？ 2. 假设猎聘网有10万名猎头，每个猎头都可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内 存中存储这10万个猎头ID和积分信息，让它能够支持这样几个操作： 根据猎头的ID快速查找、删除、更新这个猎头的积分信息； 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/gee
4、ktime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 查找积分在某个区间的猎头ID列表； 查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。 欢迎留言和我分享，我会第一时间给你反馈。 精选留言： 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 Smallfly 2018-11-05 03:56:15 通过这 20 节课学习下来，个人感觉其
5、实就两种数据结构，链表和数组。 数组占据随机访问的优势，却有需要连续内存的缺点。 链表具有可不连续存储的优势，但访问查找是线性的。 散列表和链表、跳表的混合使用，是为了结合数组和链表的优势，规避它们的不足。 我们可以得出数据结构和算法的重要性排行榜：连续空间 时间 碎片空间。 PS：跟专业的书籍相比，老师讲的真的是通俗易懂不废话，篇篇是干货。如果这个课程学不下去，学其它的会更加困难。暂时不懂的话反复阅读复习，外加 查阅，一定可以的！ 145赞 作者回复2018-11-06 01:38:23 大牛 Smallfly 2018-11-05 06:03:58 1. 在删除一个元素时，虽然能 O(1)
6、 的找到目标结点，但是要删除该结点需要拿到前一个结点的指针，遍历到前一个结点复杂度会变为 O(N），所以用双链表 实现比较合适。 （但其实硬要操作的话，单链表也是可以实现 O(1) 时间复杂度删除结点的）。 iOS 的同学可能知道，YYMemoryCache 就是结合散列表和双向链表来实现的。 2. 以积分排序构建一个跳表，再以猎头 ID 构建一个散列表。 1）ID 在散列表中所以可以 O(1) 查找到这个猎头； 2）积分以跳表存储，跳表支持区间查询； 3 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：
7、为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 ）这点根据目前学习的知识暂时无法实现，老师文中也提到了。 60赞 作者回复2018-11-06 01:37:32 其他同学可以看看这条留言 姜威 2018-11-16 13:42:35 带着问题去学习： 1.为什么散列表和链表经常放在一起使用？ 2.散列表和链表如何组合起来使用？ 一、为什么散列表和链表经常放在一起使用？ 1.散列表的优点：支持高效的数据插入、删除和查找操作 2.散列表的缺点：不支持快速顺序遍历散列表中的数据 3.如何按照顺序快速遍历散列表的数据？只能将数据转移到数组，然后排序，最后再遍历数据。
8、4.我们知道散列表是动态的数据结构，需要频繁的插入和删除数据，那么每次顺序遍历之前都需要先排序，这势必会造成效率非常低下。 5.如何解决上面的问题呢？就是将散列表和链表（或跳表）结合起来使用。 二、散列表和链表如何组合起来使用？ 1.LRU（Least Recently Used）缓存淘汰算法 1.1.LRU缓存淘汰算法主要操作有哪些？主要包含3个操作： 往缓存中添加一个数据； 从缓存中删除一个数据； 在缓存中查找一个数据； 总结：上面3个都涉及到查找。 1.2.如何用链表实现LRU缓存淘汰算法？ 需要维护一个按照访问时间从大到小的有序排列的链表结构。 缓冲空间有限，当空间不足需要淘汰一个数据
9、时直接删除链表头部的节点。 当要缓存某个数据时，先在链表中查找这个数据。若未找到，则直接将数据放到链表的尾部。若找到，就把它移动到链表尾部。 前面说了，LRU缓存的3个主要操作都涉及到查找，若单纯由链表实现，查找的时间复杂度很高为O(n)。若将链表和散列表结合使用，查找的时间复杂度 会降低到O(1)。 1.3.如何使用散列表和链表实现LRU缓存淘汰算法？ 使用双向链表存储数据，链表中每个节点存储数据（data）、前驱指针（prev）、后继指针（next）和hnext指针（解决散列冲突的链表指针）。 散列表通过链表法解决散列冲突，所以每个节点都会在两条链中。一条链是双向链表，另一条链是散列表中的
10、拉链。前驱和后继指针是为了将节点串在双 向链表中，hnext指针是为了将节点串在散列表的拉链中。 LRU缓存淘汰算法的3个主要操作如何做到时间复杂度为O(1)呢？ 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geektime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:45 首先，我们明确一点就是链表本身插入和删除一个节点的时间复杂度为O(1)，因为只需更改几个指针指向即可。 接着，来分析查找操作的时间复杂度。当要查找一个数据时，通过散列表可实现在O(1)时间复杂度找到该数据，再加上前面
11、说的插入或删除的时间复杂度是 O(1)，所以我们总操作的时间复杂度就是O(1)。 2.Redis有序集合 2.1.什么是有序集合？ 在有序集合中，每个成员对象有2个重要的属性，即key（键值）和score（分值）。 不仅会通过score来查找数据，还会通过key来查找数据。 2.2.有序集合的操作有哪些？ 举个例子，比如用户积分排行榜有这样一个功能：可以通过用户ID来查找积分信息，也可以通过积分区间来查找用户ID。这里用户ID就是key，积分就是scor e。所以，有序集合的操作如下： 添加一个对象； 根据键值删除一个对象； 根据键值查找一个成员对象； 根据分值区间查找数据，比如查找积分在10
12、0.356之间的成员对象； 按照分值从小到大排序成员变量。 这时可以按照分值将成员对象组织成跳表结构，按照键值构建一个散列表。那么上面的所有操作都非常高效。 3.Java LinkedHashMap 和LRU缓存淘汰策略实现一模一样。支持按照插入顺序遍历数据，也支持按照访问顺序遍历数据。 三、课后思考 1.上面所讲的几个散列表和链表组合的例子里，我们都是使用双向链表。如果把双向链表改成单链表，还能否正常工作？为什么呢？ 2.假设猎聘网有10万名猎头，每个猎头可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内 存中存储这10万个猎头的ID和积分
13、信息，让它能够支持这样几个操作： 1）根据猎头ID查收查找、删除、更新这个猎头的积分信息； 2）查找积分在某个区间的猎头ID列表； 3）查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。 8赞 莫问流年 2018-11-05 01:55:18 怎么判断缓存已满，是要维护一个计数变量吗 8赞 作者回复2018-11-06 01:42:32 是的 Keep-Moving 2018-11-05 01:27:00 LRU查找数据，查找到之后，不是应该把数据放到链表的头部吗？为什么这里说是尾部？ 6赞 20|散列表（下）：为什么散列表和链表经常会一起使用？ file:/F/temp/geekt
14、ime/数据结构与算法之美/20散列表（下）：为什么散列表和链表经常会一起使用？.html2019/1/15 15:35:4509|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 09|队列：队列在线程池等有限资源池中的应用 我们知道，CPU资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致CPU频繁切换，处理性能下降。所以，线程池的大 小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。 当我们向固定大小的线
15、程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又 是怎么实现的呢？ 实际上，这些问题并不复杂，其底层的数据结构就是我们今天要学的内容，队列（queue）。 如何理解“队列”？ 队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。 我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到 队列尾部；出队dequeue()，从队列头部取一个元素。
16、09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 所以，队列跟栈一样，也是一种操作受限的线性表数据结构。 队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、 阻
17、塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列Disruptor、Linux环形缓存，都用到了循环并发队 列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。 顺序队列和链式队列 我们知道了，队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素，那究竟该如何实现一个队列呢？ 跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列， 用链表实现的队列叫作链式队列。 我们先来看下基于
18、数组的实现方法。我用Java语言实现了一下，不过并不包含Java语言的高级语法，而且我做了比较详细的注释，你应该可以看懂。 / 用数组实现的队列 public class ArrayQueue / 数组：items，数组大小：n private String items; private int n = 0; / head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0; / 申请一个大小为capacity的数组 public ArrayQueue(int capacity) items = new Stringcapac
19、ity; n = capacity; / 入队 public boolean enqueue(String item) / 如果tail = n 表示队列已经满了 if (tail = n) return false; itemstail = item; +tail; return true; / 出队 public String dequeue() / 如果head = tail 表示队列为空 if (head = tail) return null; / 为了让其他语言的同学看的更加明确，把-操作放到单独一行来写了 String ret = itemshead; +head; return
20、 ret; 比起栈的数组实现，队列的数组实现稍微有点儿复杂，但是没关系。我稍微解释一下实现思路，你很容易就能明白了。 对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是head指针，指向队头；一个是tail指针，指向队尾。 abcdhead0tail4 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 你可以结合下面这幅图来理解。当 、 、 、 依次入队之后，队列中的指针指向下标为 的位置，指针指向下标为 的位置。 当我们调
21、用两次出队操作之后，队列中head指针指向下标为2的位置，tail指针仍然指向下标为4的位置。 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 你肯定已经发现了，随着不停地进行入队、出队操作，head和tail都会持续往后移动。当tail移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数 据了。这个问题该如何解决呢？ 你是否还记得，在数组那一节，我们也遇到过类似的问题，就是数组的删除操作会导致数组中的数据不连续。你还记得我们当时是怎
22、么解决的吗？对，用数据搬 移！但是，每次进行出队操作都相当于删除数组下标为0的数据，要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的O(1)变为O(n)。能不能优化 一下呢？ 实际上，我们在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数dequeue()保 持不变，我们稍加改造一下入队函数enqueue()的实现，就可以轻松解决刚才的问题了。下面是具体的代码： / 入队操作，将item放入队尾 public boolean enqueue(String item) / tail = n表示队列末尾没有空间了 if
23、 (tail = n) / tail =n / 数据搬移 for (int i = head; i next= new_node, tail = tail-next；出队时，head = head-next。我将具体的代码放到GitHub上，你可以自己试着实现一下，然后再去GitHub上跟我实现的代码对比下，看写得对不对。 循环队列 我们刚才用数组来实现队列的时候，在tail=n时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？我们来看看循环队 列的解决思路。 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与
24、算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。我画了一张图，你可以直观地感受一下。 我们可以看到，图中这个队列的大小为8，当前head=4，tail=7。当有一个新的元素a入队时，我们放入下标为7的位置。但这个时候，我们并不把tail更新为8，而是 将其在环中后移一位，到下标为0的位置。当再有一个元素b入队时，我们将b放入下标为0的位置，然后tail加1更新为1。所以，在a，b依次入队之后，循环队列中 的元素就变成了下面的样子： 09|队
25、列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有bug的循环队列 的实现代码，我个人觉得，最关键的是，确定好队空和队满的判定条件。 在用数组实现的非循环队列中，队满的判断条件是tail = n，队空的判断条件是head = tail。那针对循环队列，如何判断队空和队满呢？ 队列为空的判断条件仍然是head = tail。但队列
26、满的判断条件就稍微有点复杂了。我画了一张队列满的图，你可以看一下，试着总结一下规律。 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。 你有没有发现，当队列满时，图中的tail指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。 Talk is cheap，如果还是没怎么理解，那就show you code吧。 public class CircularQueue / 数组：items，数组大小：n private String
