Design and implement an LRU (least recently used) caching mechanism

Ideas:

  1. It should support the following operations: get for data and PUT for writing data.
  2. Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned.
  3. Write data PUT (key, value) – Writes the data value of the key if it does not exist. When the cache reaches its maximum capacity, it should remove the least-recently used data values before writing new data to make room for new data values.

Scheme 1 directly inherits LinkHashMap

public class LRUCache extends LinkedHashMap<Integer,Integer> {

private int capacity; Public LRUCache (int) capacity {super (capacity, 0.75 f, 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); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; }Copy the code

}

Scheme 2: double linked list +hashMap

public class LRUCacheNormal { private int capacity; private HashMap<Integer,Integer> map; private DoubleLink cache; Public LRUCacheNormal(int capacity) {this.capacity = capacity; this.map = new HashMap<>(); this.cache = new DoubleLink(); } public int get(int key) { if (! map.containsKey(key)) return -1; int val = map.get(key).intValue(); put(key, val); return val; } public void put(int key, int val) {Node x = new Node(key, val); Remove (new Node(key, map.get(key))); if (map.containsKey(key)) {// Delete the old one and insert the new one into the header cache.remove(new Node(key, map.get(key))); cache.addFirst(x); Put (key, x.val); // Update the corresponding data in the map. } else {if (capacity == cache.size()) {last = cache.removelast (); map.remove(last.key); } cache.addFirst(x); map.put(key, x.val); } } class DoubleLink { private Node head,tail; private int size; public DoubleLink(){ head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; size = 0; } public void addFirst(Node x) { x.next = head.next; x.prev = head; head.next.prev = x; head.next = x; size++; } public void remove(Node x) { x.prev.next = x.next; x.next.prev = x.prev; size--; } public Node removeLast() { if (tail.prev == head) return null; Node last = tail.prev; remove(last); return last; } public int size() { return size; } } class Node { public int key, val; public Node next, prev; public Node(int k, int v) { this.key = k; this.val = v; }}}Copy the code