手写lru算法 java android里面lrucache算法为什么用双向链表实现？
android里面lrucache算法为什么用双向链表实现？
LRU是通过双向链表和映射实现的，在Java中也是通过双向链表实现的。通过JDK中的LinkedHashMap很容易实现lrucache。
将最近访问的元素放在链表的一端，如果容量达到限制，则从另一端删除该元素
LRU算法的设计原则是：如果最近一段时间内没有访问过某个数据，则将来不太可能访问该数据。换言之，当有限的空间充满数据时，应该消除最长时间未被访问的数据。
执行LRU
1。使用数组存储数据，用访问时间戳标记每个数据项。插入新数据项时，首先增加数组中现有数据项的时间戳，将新数据项的时间戳设置为0，然后将其插入数组中。每次访问数组中的数据项时，所访问数据项的时间戳都设置为0。当数组空间已满时，时间戳最大的数据项将被删除。
2. 使用链表实现，每次插入新数据时，将新数据插入链表的头部；每次缓存命中时，将数据移动到链表的头部（即访问数据）；然后在链表已满时丢弃链表末尾的数据。
3. 使用链表和HashMap。当需要插入新数据项时，如果新数据项存在于链表中（通常称为hit），请将节点移动到链表的头部。如果不存在，则创建一个新节点并将其放在链表的头部。如果缓存已满，请删除链表的最后一个节点。在访问数据时，如果链表中存在该数据项，则节点会移到链表的头，否则返回-1。这样，链表末尾的节点就是最近不可访问的数据项。
对于第一种方法，需要连续维护数据项的访问时间戳。另外，在插入数据、删除数据和访问数据时，时间复杂度为O（n）。对于第二种方法，链表的时间复杂度为O（n）。所以一般来说，第三种方法是实现LRU算法。
lru算法？
1. Linkedhashset继承自hahsset。构造方法使用三个参数调用方法。构造方法的底层初始化LinkedHashMap。因为LinkedHashMap是有序的，所以linkedhashset也是有序的。为什么我们不能调用这个构造函数？它是包访问级别，不能在外部调用。接下来，分析LinkedHashMap是如何实现的，以理解为什么它是有序的。
2. 先看下面的图片。（对于写在手机上的问题，你不能把图片放在文字里，它们都在下面。）。
LinkedHashMap的数据结构与HashMap不同。HashMap中的条目有四个属性：key、value、hash和next，而LinkedHashMap中的条目添加了before和after属性。因此，LinkedHashMap在HashMap的基础上使用双向链表来连接所有节点。当然，它也有一个头部节点，所以遍历可以有序进行。具体结构如图所示。
3. LinkedHashMap主要重写addentry和createentry方法，在创建节点时创建双向链表。
此外，LinkedHashMap还可以实现LRU算法的缓存。
源代码基于JDK7查看ha。如果你不懂HashMap，你可以看到我分享的另一篇文章。
希望对您有所帮助，您可以关注我，以后会分享更多的架构和java知识文章。
手写lru算法 java spring事务原理 java和c++哪个好
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
