因此，读者在阅读本文之前，最好对 HashMap 有一个较为深入的了解和回顾，否则很可能会导致事倍功半。可以参考我之前关于hashmap的文章。...事实上，不管调用HashMap的哪个构造函数，HashMap的构造函数都会在最后调用一个init()方法进行初始化，只不过这个方法在HashMap中是一个空实现，而在LinkedHashMap中重写了它用于初始化它所维护的双向链表...我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾：get方法通过调用recordAccess方法来实现； put方法在覆盖已有...在链表长度超过8时自动转为红黑树，会按顺序插入链表中的元素，可以自定义比较器来定义节点的插入顺序。...5 linkedhashmap的removeEldestEntry方法默认返回false，要实现lru很重要的一点就是集合满时要将最久未访问的元素删除，在linkedhashmap中这个元素就是头指针指向的元素
实际上， LRU 和 LFU 在实现上也是挺相似的，都要使用到双向链表和 hashmap，只不过，我们需要思考如何很好的处理好频次这个数据 LRU 查询数据的时候，为了将时间复杂度从 O(n) 降低到...的实现时用一个双向链表，插入数据使用头插法，从尾部淘汰数据 那么 LFU 的实现实际上是使用了 2 个 hashmap 和 多个 双向链表，插入数据使用尾插法，淘汰数据从链表头淘汰 ✔举例时刻 还是同样的方法...hashmap 中 获取 3， key 为 3 的节点在 LFU 中，更新 3 节点的频次，从频次 1 更新到 频次 2 相当于在频次为 1 对应得的链表中，删除 3 这个节点，让 2 节点和 4...频次（最低的）当前频次为 1 的链表的头结点，且删除 hashmap 中的数据，同时将 5 这个节点的数据加入到 hashmap 中 从上述演示中，我们可以看到关于 LRU 的关键逻辑 实现基本的链表...LRU 的实现来说，会多维护一个 hashmap ，只不过这个 hashmap 是 key 为 频次，value 为链表 ，即上图中的 hashmap_freq 知道 LFU 的思想，以及 LFU 中数据变动的过程明白了
添加删除元素的时候需要同时维护在HashMap中的存储，也要维护在LinkedList中的存储，所以性能上来说会比HashMap稍慢。...; Node next; } 存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。...afterNodeInsertion(boolean evict)方法 在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。...）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法； （3）afterNodeRemoval()方法在LinkedHashMap...中也有实现，用来在移除元素后修改双向链表，见下文； （4）默认removeEldestEntry()方法返回false，也就是不删除元素。
什么是LinkedHashMap？ LinkedHashMap 是 HashMap 的有序实现。LinkedHashMap 用一条双向链表来维护顺序，迭代的时候也使用自己实现的迭代器。...LinkedHashMap 的底层除了继承自 HashMap 的数组，链表，红黑树，还多了链接所有节点的双向链表（图中红色和绿色箭头），用于存储各个节点的顺序。 ?...这样的继承关系其实并不是为 HashMap 设计的，在 HashMap 中确实没什么用。...LinkedHashMap 时，把 accessOrder 参数设为 true，那么我们不仅在插入的时候会维护链表，在访问节点的时候也会维护链表。...因为我们在遍历的时候又调用了 get 方法，导致链表发生变化，才会抛这个错。
介绍 Redis是一个内存数据库，当Redis使用的内存超过物理内存的限制后，内存数据会和磁盘产生频繁的交换，交换会导致Redis性能急剧下降。...：在设置了过期时间的键值对中随机进行删除 volatile-ttl：根据过期时间的先后进行删除，越早过期的越先被删除 allkeys-lru：在所有键值对中，使用lru算法进行删除 allkeys-lfu...而长时间未被访问的数据，应该被淘汰」 lru算法中数据会被放到一个链表中，链表的头节点为最近被访问的数据，链表的尾节点为长时间没有被访问的数据 「lru算法的核心实现就是哈希表加双向链表」。...链表可以用来维护访问元素的顺序，而hash表可以帮我们在O(1)时间复杂度下访问到元素。 「至于为什么是双向链表呢」？主要是要删除元素，所以要获取前继节点。...「幸亏Java有LinkedHashSet这个类，链表和集合的结合体，链表不能快速删除元素，但是能保证插入顺序。集合内部元素无序，但是能快速删除元素，完美」 下面就是具体的实现。
今天我们来深入探索一下LinkedHashMap的底层原理，并且使用linkedhashmap来实现LRU缓存。 摘要： HashMap和双向链表合二为一即是LinkedHashMap。...因此，读者在阅读本文之前，最好对 HashMap 有一个较为深入的了解和回顾，否则很可能会导致事倍功半。可以参考我之前关于hashmap的文章。...事实上，不管调用HashMap的哪个构造函数，HashMap的构造函数都会在最后调用一个init()方法进行初始化，只不过这个方法在HashMap中是一个空实现，而在LinkedHashMap中重写了它用于初始化它所维护的双向链表...我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾：get方法通过调用recordAccess方法来实现； put方法在覆盖已有...在链表长度超过8时自动转为红黑树，会按顺序插入链表中的元素，可以自定义比较器来定义节点的插入顺序。
二、Java的LRU算法 Java的LRU算法的基础是LinkedHashMap，LinkedHashMap继承了HashMap，并且在HashMap的基础上进行了一定的改动，以实现LRU算法。...在LinkedHashMap中，即保留了HashMap的数组加链表的数据保存格式，同时增加了一套header作为开始标记的双向链表（我们暂且称之为header的双向链表）。...LinkedHashMap就是通过header的双向链表来实现LRU算法的。header.after永远指向最近最不常使用的那个节点，删除的话，就是删除这个header.after对应的节点。...LinkedHashMap中的removeEldestEntry(eldest)方法永远返回false，如果我们要实现LRU算法，就需要重写这个方法，判断在什么情况下，删除最近最不常使用的节点。...这个方法在HashMap中为空，LinkedHashMap的Entry则实现了这个方法。其中remove()方法中的两行代码为双向链表中删除当前节点的标准代码，不解释。 ?
一、什么是缓存 这里说的缓存是一种广义的概念，在计算机存储层次结构中，低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存，内存是硬盘的缓存，硬盘是网络的缓存等等。...实现LRU时，我们需要关注它的读性能和写性能，理想的LRU应该可以在O(1)的时间内读取一条数据或更新一条数据，也就是说读写的时间复杂度都是O(1)。...这可以通过HashMap+双向链表实现。HashMap保证通过key访问数据的时间为O(1)，双向链表则按照访问时间的顺序依次穿过每个数据。...我们只需要在每次访问过后改变链表的连接顺序即可。 HashMap+双向链表 实现代码如下： 每个方法和成员变量前都有中文注释，不必过多解释。...值得一提的是，Java API中其实已经有数据类型提供了我们需要的功能，就是LinkedHashMap这个类。该类内部也是采用HashMap+双向链表实现的。使用这个类实现LRU就简练多了。
中的init方法为空）， //该方法在父类的构造方法和Clone、readObject中在插入元素前被调用， //初始化一个空的双向循环链表，头结点中不保存数据，头结点的下一个节点才开始保存数据...都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序；当它为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其...，从而实现双向链表中的元素按照访问顺序来排序（最近访问的Entry放到链表的最后，这样多次下来，前面就是最近没有被访问的元素，在实现、LRU算法时，当双向链表中的节点数达到最大值时，将前面的元素删去即可...我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此便把该Entry加入到了双向链表的末尾（get方法通过调用recordAccess方法来实现，put方法在覆盖已有...key的情况下，也是通过调用recordAccess方法来实现，在插入新的Entry时，则是通过createEntry中的addBefore方法来实现），这样便把最近使用了的Entry放入到了双向链表的后面
的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。...HashMap 和 双向链表实现 LRU 整体的设计思路可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的...LRU 存储是基于双向链表实现的，下面的图演示了它的原理。其中 head 代表双向链表的表头，tail 代表尾部。...下面展示了，预设大小是 3 的，LRU存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展示 HashMap部分的变化，仅仅演示了上图 LRU 双向链表的变化。...如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
一、什么是缓存 这里说的缓存是一种广义的概念，在计算机存储层次结构中，低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存，内存是硬盘的缓存，硬盘是网络的缓存等等。...实现LRU时，我们需要关注它的读性能和写性能，理想的LRU应该可以在O(1)的时间内读取一条数据或更新一条数据，也就是说读写的时间复杂度都是O(1)。...这可以通过HashMap+双向链表实现。HashMap保证通过key访问数据的时间为O(1)，双向链表则按照访问时间的顺序依次穿过每个数据。...我们只需要在每次访问过后改变链表的连接顺序即可。 ? HashMap+双向链表 实现代码如下： ? ? ? ? ? 每个方法和成员变量前都有中文注释，不必过多解释。...值得一提的是，Java API中其实已经有数据类型提供了我们需要的功能，就是LinkedHashMap这个类。该类内部也是采用HashMap+双向链表实现的。使用这个类实现LRU就简练多了。 ? ?
HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Node节点链入一个双向链表的HashMap。...MAXIMUM_CAPACITY : n + 1; } 1.2、HashMap的数据结构 我们知道，在Java中最常用的两种结构是数组和链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap...在JDK1.6和JDK1.7中，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的key-value键值对都存储在一个链表里。...最让人疑惑的有两个点： 为什么（e.hash & oldCap）== 0时就放入lo链表，否则就是hi链表; 为什么 j + oldCap就是键值对在新的table数组中的位置； 其实这里包含着一些数学技巧...虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logN)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/
添加删除元素的时候需要同时维护在HashMap中的存储，也要维护在LinkedList中的存储，所以性能上来说会比HashMap稍慢。...Node next;} 存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。...afterNodeInsertion(boolean evict)方法 在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。...）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法； （3）afterNodeRemoval()方法在LinkedHashMap...中也有实现，用来在移除元素后修改双向链表，见下文； （4）默认removeEldestEntry()方法返回false，也就是不删除元素。
基本字段 在 HashMap 的基础上他添加了三个字段，这三个字段都非常重要，首先就是关于双向链表的两个字段 以及决定是否进行 LRU 的标志位。...这个节点里是在 HashMap 的 Node 节点上添加了 before 和 after ,也就是用来构造双向链表的指针。 4....构造方法 这个类有 5 个构造方法，一开始我以为和 HashMap 一样只有四个，后来又找到一个隐藏的比较深的方法，也是实现 LRU 最重要的一个方法。 ...最后那个方法如果我们设置了 accessOrder=true 那么我们在访问一个元素的时候，这个元素会自动的排到双向链表的结尾。也就是所谓的 LRU。 ...// 如果accessOrder 为 true，也就是支持 LRU 算法，那么就把这个元素先从双向链表中删除（在数组中的位置不变），然后插到链表的头部作为最新的元素 void afterNodeAccess
LRU缓存的实现相比LFU来说要简单一点，最关键的在于LRU缓存插入，查询和删除可以做到O（1）的时间复杂度，这一点相比LFU的O（logN）来说在大数据量下LRU表现更好，此外LRU非常适合存在热点数据的场景...众所周知，双向链表的插入和删除可以达到O（1）的时间复杂度，但双向链表的缺点在于，其查询的时间复杂度为O（n）这就是它的短板，那么如何加速查询？...这里我们可以利用HashMap来当索引查询，从而使得双向链表的查询的时间复杂度也能达到O（1），没错LRU的实现原理，就是充分结合了两种数据结构的优点而衍生出来的。...我们看下面的一张图就非常直观的显示了这种关系： 上图中HashMap的key就是链表数据的key，而value就是该Node在双向链表里面的位置，也就是指针地址。...本文主要结合代码介绍了LRU缓存的原理和实现，LRU缓存的应用场景主要在于互联网项目的热点数据访问，但对偶发性的、周期性的批量操作会导致LRU算法命中率急剧下降，从而降低其性能，这一点我们应该了解。
如何使用链表实现LRU缓存淘汰算法，有什么特点，如何优化？ 好了，我们带着上面的问题来学进行下面的学习。 1、什么是缓存，缓存的作用是什么?...在缓存中，它的设计原则是：如果数据被访问多次，那么将来它的访问频率也会更高。...因为我们需要删除操作，删除一个节点不仅要得到该节点本身的指针，也需要操作其它前驱节点的指针，而双向链表能够直接找到前驱，保证了操作时间复杂度为O(1)，因此使用双向链表作为实现LRU缓存淘汰算法的结构会更高效...双向链表的节点中除了value外还需要包含key，因为在删除最久未使用的数据时，需要通过链表来定位hashmap中应当删除的键值对 一些操作：双向链表中，在后面的节点表示被最近访问 新加入的节点放在链表末尾...(node) 为了操作的方便，在双向链表头和尾分别定义一个head和tail节点。
LRU Cache的实现 那要实现一个LRU Cache其实并不难，方法和思路有很多；但是想要实现一个高效（所有操作都是O(1) ）的LRU Cache是有难度的 实现LRU Cache的方法和思路很多...，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。...使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。 那具体到底应该应该怎么做呢？...，那上面也提到了，使用双向链表和哈希表的搭配是最高效和经典的： 我们再搞一个list（list底层就是带头双向循环链表），让它里面也存储数据（相当于数据存储两份），然后我们可以默认认为尾部的那个元素就是最近最少用...那这个问题我们如何解决一下呢？ 如何做到在哈希表里面找到这个key之后，就直接能获取到他在list中的位置，而不需要去遍历查找呢？
那天我在 LeetCode 上刷到一道 LRU 缓存机制的问题，第 146 题，难度为中等，题目如下。 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。...什么，这么完美还不符合面试官要求，面试官是什么要求呢？面试官的要求是考考你 LRU 的原理，让你自己实现一个。 那咱们就由LinkedHashMap介绍一下最基础的 LRU 实现。...简单概括 LinkedHashMap的实现原理就是 HashMap+双向链表的结合。...双向链表用来维护元素访问顺序，将最近被访问（也就是调动 get 方法）的元素放到链表尾部，一旦超过缓存容量的时候，就从链表头部删除元素，用双向链表能保证元素移动速度最快，假设访问了链表中的某个元素，只要把这个元素移动链表尾部...用来存储 key 值对应的节点，为的是快速定位 key 值在链表中的位置，我们都知道，这是因为HashMap的 get 方法的时间复杂度为 O(1)。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
实时音视频
