我想做网站怎么做昆山,网站开发项目私活,向国旗敬礼做美德少年网站,wordpress zhong思路#xff1a; 首先要了解LRU缓存的原理#xff0c;首先定下容量#xff0c;每次get请求和put请求都会把当前元素放最前/后面#xff0c;如果超过容量那么头部/尾部元素就被移除#xff0c;所以最近最少使用的元素会被优先移除#xff0c;保证热点数据持续存在。 不管放…
思路 首先要了解LRU缓存的原理首先定下容量每次get请求和put请求都会把当前元素放最前/后面如果超过容量那么头部/尾部元素就被移除所以最近最少使用的元素会被优先移除保证热点数据持续存在。 不管放在头部还是尾部都可以。看你怎么定义 那么如何实现呢有两种方式第一种直接继承LinkedHashMap 这个是已经帮我们实现的代码如下
class LRUCache extends LinkedHashMapInteger, Integer{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity capacity;}public int get(int key) {return super.getOrDefault(key, -1);}// 这个可不写public void put(int key, int value) {super.put(key, value);}Overrideprotected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) {return size() capacity; }
}
第二种就是手动去实现了代码如下
class LRUCache extends AbstractLRUCacheInteger, Integer {public LRUCache(int capacity) {super(capacity);}public int get(int key) {Integer ans super.get(key);return ans null ? -1 : ans;}public void put(int key, int value) {super.set(key, value);}
}abstract class AbstractLRUCacheK, V {private MapK, NodeK, V keyNodeMap;private NodeDoubleLinkedListK, V nodeList;private final int capacity;public AbstractLRUCache(int cap) {if (cap 1) {throw new RuntimeException(should be more than 0);}keyNodeMap new HashMap();nodeList new NodeDoubleLinkedList();capacity cap;}public V get(K key) {if (keyNodeMap.containsKey(key)) {NodeK, V res keyNodeMap.get(key);nodeList.moveNodeToTail(res);return res.value;}return null;}public void set(K key, V value) {if (keyNodeMap.containsKey(key)) {NodeK, V node keyNodeMap.get(key);node.value value;nodeList.moveNodeToTail(node);} else {NodeK, V newNode new Node(key, value);keyNodeMap.put(key, newNode);nodeList.addNode(newNode);if (keyNodeMap.size() capacity 1) {removeMostUnusedCache();}}}private void removeMostUnusedCache() {NodeK, V node nodeList.removeHead();keyNodeMap.remove(node.key);}class NodeK, V {public K key;public V value;public NodeK, V last;public NodeK, V next;public Node(K key, V value) {this.key key;this.value value;}}class NodeDoubleLinkedListK, V {private NodeK, V head;private NodeK, V tail;public NodeDoubleLinkedList() {head null;tail null;}public void addNode(NodeK, V newNode) {if (newNode null) {return;}if (head null) {head newNode;tail newNode;} else {tail.next newNode;newNode.last tail;tail newNode;}}public void moveNodeToTail(NodeK, V node) {if (this.tail node) {return;}if (this.head node) {this.head node.next;this.head.last null;} else {node.last.next node.next;node.next.last node.last;}node.last this.tail;node.next null;this.tail.next node;this.tail node;}public NodeK, V removeHead() {if (this.head null) {return null;}NodeK, V res this.head;if (this.head this.tail) {this.head null;this.tail null;} else {this.head res.next;res.next null;this.head.last null;}return res;}}
}
以下是代码实现的功能要点 AbstractLRUCache 是一个抽象类它包含了 LRU 缓存的核心逻辑如添加节点、移动节点到链表尾部、移除最少使用的节点等。 LRUCache 是 AbstractLRUCache 的具体实现它提供了 get 和 put 方法来与缓存进行交互。这些方法调用了抽象类中的方法来实现 LRU 逻辑。 Node 类代表缓存中的一个条目包含键、值以及指向前一个和后一个节点的指针。 NodeDoubleLinkedList 是一个双向链表用于按照访问顺序维护缓存中的节点。最近访问的节点被移动到链表的尾部而最少使用的节点位于链表的头部。 当缓存达到其容量限制时最少使用的节点链表头部的节点将被移除以确保缓存大小不超过设定的容量。
