广东省建设厅投诉网站首页,免费追剧网站,榆中建设局网站,wordpress网站百度收录首页《算法通关村——缓存机制了解LRU实现》
介绍
LRU是Least Recently Used#xff08;最近最少使用#xff09;的缓存机制#xff0c;它是一种常用的缓存算法#xff0c;用于管理缓存中的数据项。LRU缓存机制的基本思想是#xff0c;当缓存达到其容量限制时Least Recently Used最近最少使用的缓存机制它是一种常用的缓存算法用于管理缓存中的数据项。LRU缓存机制的基本思想是当缓存达到其容量限制时会淘汰最久没有被访问的数据项以为新的数据项腾出空间。
LRU缓存机制的实现方式通常是通过维护一个数据结构例如链表或双向链表来记录数据项的访问顺序。最近访问的数据项会被移到链表的头部或双向链表的头部而最久未被访问的数据项则位于链表的尾部。当需要从缓存中淘汰数据项时就选择尾部的数据项进行淘汰以确保淘汰最久未被访问的数据。
LRU缓存机制在实际应用中表现出良好的性能因为它通常能够保留最常被访问的数据项从而提高缓存命中率。然而LRU的实现可能需要一定的额外开销因为需要维护访问顺序的数据结构而且在某些情况下可能需要频繁地移动数据项这可能会导致性能问题。因此在特定情况下可以考虑其他缓存淘汰算法如LFULeast Frequently Used或FIFOFirst-In, First-Out等。
当涉及到缓存淘汰算法时除了LRU还有其他一些常见的算法其中包括LFULeast Frequently Used和FIFOFirst-In, First-Out LFULeast Frequently Used LFU算法基于数据项被访问的频率来进行缓存淘汰决策。它认为访问频率较低的数据项应该被淘汰因为它们被认为是不太重要或不太常用的数据。LFU算法通常使用一个计数器来跟踪每个数据项被访问的次数。当需要淘汰数据项时选择具有最低访问次数的数据项进行淘汰。一些变种的LFU算法也考虑了时间因素以便更好地适应数据访问模式的变化。这些变种可能会在计数器的基础上引入时间衰减因素。 FIFOFirst-In, First-Out FIFO算法是一种非常简单的缓存淘汰策略。它按照数据项最早进入缓存的顺序来进行淘汰。也就是说首先进入缓存的数据项最先被淘汰而最后进入的数据项最后被淘汰。FIFO算法通常使用一个队列来维护数据项的顺序。当需要淘汰数据项时从队列的头部移除最早进入的数据项。FIFO算法的主要优点是其简单性但它可能不太适用于某些访问模式因为它不考虑数据项的访问频率或重要性只根据进入顺序进行淘汰。
选择何种缓存淘汰算法通常取决于具体的应用场景和需求。不同的算法有不同的优缺点因此需要根据数据访问模式、性能需求以及实际应用的特点来选择最合适的算法。在某些情况下也可以考虑结合多个算法或自定义淘汰策略以满足特定的需求。
代码实现
package AlgorithmFifth;import java.util.HashMap;
import java.util.Map;public class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key,int _value){key _key;value _value;}}private MapInteger,DLinkedNode cache new HashMap();private int size;private int capacity;private DLinkedNode head,tail;public LRUCache(int capacity){this.size 0;this.capacity capacity;// 使用伪头部和伪尾部节点head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key){DLinkedNode node cache.get(key);if(node null){return -1;}// 如果key存在先通过哈希表定位再移到头部moveToHead(node);return node.value;}public void put(int key,int value){DLinkedNode node cache.get(key);if(node null){// 如果key不存在创建一个新节点DLinkedNode newNode new DLinkedNode(key,value);// 添加进哈希表cache.put(key,newNode);// 添加至双向链表的头部addToHead(newNode);size;if(size capacity){// 如果超出容量删除双向链表的尾部节点DLinkedNode tail removeTail();// 删除哈希表中对应的项cache.remove(tail.key);size--;}}else {// 如果key存在先通过哈希表定位在修改value并移到头部node.value value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(DLinkedNode node){node.prev.next node.next;node.next.prev node.prev;}private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}private DLinkedNode removeTail(){DLinkedNode res tail.prev;removeNode(res);return res;}public static void main(String[] args) {LRUCache lruCache new LRUCache(2);lruCache.put(1,1);lruCache.put(2,2);System.out.println(lruCache.get(1));lruCache.put(3,3);System.out.println(lruCache.get(2));lruCache.put(4,4);System.out.println(lruCache.get(1));System.out.println(lruCache.get(3));System.out.println(lruCache.get(4));}
} 近期在自学 Java 做项目加入了一个编程学习圈子里面有编程学习路线和原创的项目教程感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑也希望能对大家有帮助扫 ⬇️ 二维码即可加入。 也可以点击链接我正在「编程导航」和朋友们讨论有趣的话题你⼀起来吧 也可以加我QQ2837468248咨询说明来意
