问题:获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
例子:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4
解析1:HashMap+双向链表。根据要求,可以实现put时,若不存在key相同的,将newNode插入双向链表head的后继,即头节点,若此时size大于capacity则将尾节点和其kv删除。否则,将原先节点提到头节点处,将value更新。实现get时,直接输出value值并且将该key对应的节点提到头节点处。
代码:
import java.util.Hashtable; public class LRUCache { class DLinkedNode {//定义节点 int key; int value; DLinkedNode prev; DLinkedNode next; } private void addNode(DLinkedNode node) {//增加node至头节点处操作 /** *新的节点总在head节点后 */ node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node){ /** * 删除节点的操作 */ DLinkedNode prev = node.prev; DLinkedNode next = node.next; prev.next = next; next.prev = prev; } private void moveToHead(DLinkedNode node){ /** * 更新当前节点位置至头节点处 */ removeNode(node); addNode(node); } private DLinkedNode popTail() { /** * 将尾节点tail的前驱节点输出(同时删除该节点) */ DLinkedNode res = tail.prev; removeNode(res); return res; } private Hashtable<Integer, DLinkedNode> cache = new Hashtable<Integer, DLinkedNode>();//定义一个Hashtable(key,双向链表) private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) {//构造函数,造出head,tail相互指向 this.size = 0; this.capacity = capacity; head = new DLinkedNode(); // head.prev = null; tail = new DLinkedNode(); // tail.next = null; head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) return -1; // 更新节点的位置 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key);//查看当前链表中key对应的节点 if(node == null) {//如果链表中无此节点 DLinkedNode newNode = new DLinkedNode(); newNode.key = key; newNode.value = value; cache.put(key, newNode); addNode(newNode);//加入链表 ++size;//长度加一 if(size > capacity) {//超出了容量 // pop the tail DLinkedNode tail = popTail();//将尾部节点删除 cache.remove(tail.key);//在hashtable中将其对应的kv删除 --size; } } else { //链表中有此节点则更新value. node.value = value; moveToHead(node);//移至头节点 } } } /** * LRUCache 对象会以如下语句构造和调用: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */
解析2:LinkedHashMap的使用。需要对LinkedHashMap有深刻的了解。有序的hashMap,get过一次,就变到首端(直接达到了上述的效果,实际上上面就是对LinkedHashMap的实现)。只要在put的时候是否需要将最老节点去掉的条件改成size和capacity的大小关系就可以了。
代码:
class LRUCache extends LinkedHashMap<Integer, 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);//Map中的方法,找到了返回value,没有就返回-1 } public void put(int key, int value) { super.put(key,value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } }