关于加强内网网站建设的通知,广州小程序开发外包,2003系统做网站,登陆国外的网站要这么做今天研究一下LRU算法#xff0c;上学期学数据结构的时候就应该学一下这个算法#xff0c;不过后面操作系统也会讲到LRU算法
题目
LRU缓存leetocde146
LRU#xff08;Least Recently Used#xff0c;最近最少使用#xff09;算法是一种常见的缓存替换算法#xff0c;通…今天研究一下LRU算法上学期学数据结构的时候就应该学一下这个算法不过后面操作系统也会讲到LRU算法
题目
LRU缓存leetocde146
LRULeast Recently Used最近最少使用算法是一种常见的缓存替换算法通常用于缓存管理中。它的核心思想是当缓存空间满时会优先淘汰最近最少使用的缓存数据以便为新的数据腾出空间。LRU算法的基本原理是基于时间局部性原理即最近被访问的数据很可能在未来会被再次访问。。
如何使用数组或者链表来实现效率比较对为了实现On的效率我们可以采用双链表但是要找到一个值双链表的查询还是On,那么就可以引入hash不产生碰撞的情况下hash的效率是O1 所以来用双链表Hash来实现。 分析 需要有插入和get操作并且要求事件复杂度都是O1。
思路对于put操作如果当前的节点已经存在修改当前节点的值再讲节点移动到头节点去。 如果空间已经满了需要删除最后一个节点因为是双链表所以事件复杂度为o1并且将这个节点插入到头部去再添加进缓存中去。
对于get操作因为LRU算法遵循的是最近最少使用每一次使用都会刷新得到节点的值并且还需呀将节点的值移动到头部去。
对于moveHead操作分为两步分为别deleteHead和addHead都是数据结构双链表之间的操作插入和删除节点。
package LRU;import java.util.HashMap;
import java.util.Map;public class LRUCache {Entry head, tail;int capacity;int size;MapInteger, Entry cache;public LRUCache(int capacity) {this.capacity capacity;size 0;initLinkedList(); //初始化缓存链表cache new HashMap(capacity 2); //引入了两个哨兵}public void put(int key, int value) {Entry node cache.get(key);if (node !null) {node.value value;moveHead(node);return;}if (size capacity) {//空间满了Entry lastNode tail.pre;deleteHead(lastNode);cache.remove(lastNode.key);size--;}Entry newNode new Entry();newNode.key key;newNode.value value;addNode(newNode);cache.put(key, newNode);size;}public int get(int key) {Entry node cache.get(key);if (node null) {return -1;}moveHead(node);return node.value;}private void moveHead(Entry node) {//删除deleteHead(node);addNode(node);}private void addNode(Entry node) {//讲节点插入到头节点去head.next.pre node;node.next head.next;node.pre head;head.next node;}private void deleteHead(Entry node) {//双链表删除一个节点node.pre.next node.next;node.next.pre node.pre;}public void initLinkedList() {head new Entry();tail new Entry();head.next tail;tail.next head;}public static class Entry {public Entry pre;public Entry next;public int key;public int value;public Entry(int key,int value) {this.keykey;this.valuevalue;}public Entry() {}}public static void main(String[] args) {LRUCache cachenew LRUCache(2);cache.put(1,1);cache.put(1,2);System.out.println(cache.get(1)); //得到现在的缓存2并且当前的2已经移动到最前面去了//再加进来3的时候1就会被删除cache.put(3,3);System.out.println(cache.get(2));}
}
