网站评测的作用,做商城网站技术要点,wordpress获取文章图片地址,设计开发控制程序为了实现一个满足 LRU#xff08;最近最少使用#xff09;缓存约束的数据结构#xff0c;我们需要在 (O(1)) 时间复杂度内完成 get 和 put 操作。这通常可以通过结合使用哈希表和双向链表来实现#xff1a;
哈希表#xff1a;用于在 (O(1)) 时间复杂度内实现对缓存中元素…为了实现一个满足 LRU最近最少使用缓存约束的数据结构我们需要在 (O(1)) 时间复杂度内完成 get 和 put 操作。这通常可以通过结合使用哈希表和双向链表来实现
哈希表用于在 (O(1)) 时间复杂度内实现对缓存中元素的快速访问。双向链表用于维护缓存中元素的顺序以便在缓存容量超出限制时能够快速定位并移除最久未使用的元素。
以下是 LRUCache 类的实现
import java.util.HashMap;
import java.util.Map;class LRUCache {private class Node {int key;int value;Node prev;Node next;Node(int key, int value) {this.key key;this.value value;}}private final int capacity;private final MapInteger, Node cache;private final Node head;private final Node tail;public LRUCache(int capacity) {this.capacity capacity;this.cache new HashMap();this.head new Node(0, 0);this.tail new Node(0, 0);head.next tail;tail.prev head;}public int get(int key) {Node node cache.get(key);if (node null) {return -1;}// Move the accessed node to the headmoveToHead(node);return node.value;}public void put(int key, int value) {Node node cache.get(key);if (node null) {// Create a new nodeNode newNode new Node(key, value);cache.put(key, newNode);addNode(newNode);if (cache.size() capacity) {// Pop the tailNode tail popTail();cache.remove(tail.key);}} else {// Update the valuenode.value value;moveToHead(node);}}private void addNode(Node node) {node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(Node node) {Node prev node.prev;Node next node.next;prev.next next;next.prev prev;}private void moveToHead(Node node) {removeNode(node);addNode(node);}private Node popTail() {Node 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)); // 返回 1lruCache.put(3, 3); // 该操作会使得关键字 2 作废System.out.println(lruCache.get(2)); // 返回 -1 (未找到)lruCache.put(4, 4); // 该操作会使得关键字 1 作废System.out.println(lruCache.get(1)); // 返回 -1 (未找到)System.out.println(lruCache.get(3)); // 返回 3System.out.println(lruCache.get(4)); // 返回 4}
}解释
Node 类用于表示双向链表中的节点包含 key 和 value以及前驱和后继节点的引用。构造函数初始化缓存容量、哈希表、以及双向链表的头尾虚拟节点。get 方法检查缓存中是否存在指定键若存在则将该节点移动到链表头部表示最近使用并返回其值否则返回 -1。put 方法插入新键值对时若键已存在则更新值并移动到链表头部若键不存在则创建新节点并插入链表头部若超出容量则移除链表尾部节点最久未使用。辅助方法 addNode在链表头部插入节点。removeNode从链表中移除节点。moveToHead将节点移动到链表头部。popTail移除并返回链表尾部节点。
这种设计确保了所有操作的平均时间复杂度为 (O(1))。
