preface

Recently, I saw an interview question about Redis, which mentioned that Redis will use LRU and other elimination mechanism when the memory reaches the maximum limit. Then I found some information about this aspect to share with you.

If a new number comes and the memory is full, the old number needs to be eliminated. In order to move the data easily, we must use a data structure like a linked list. In addition, key-value data structures such as hashMap should also be used to determine whether the data is the latest or the oldest.

The first implementation (using LinkedHashMap)

public class LRUCache { int capacity; Map<Integer,Integer> map; public LRUCache(int capacity){ this.capacity = capacity; map = new LinkedHashMap<>(); } public int get(int key){// If (! map.containsKey(key)){ return -1; } // Refresh data when found Integer value = map.remove(key); map.put(key,value); return value; } public void put(int key,int value){ if (map.containsKey(key)){ map.remove(key); map.put(key,value); return; } map.put(key,value); // Out of capacity, If (map.size() > capacity){map.remove(map.entryset ().iterator().next().getKey());  } } public static void main(String[] args) { LRUCache lruCache = new LRUCache(10); for (int i = 0; i < 10; i++) { lruCache.map.put(i,i); System.out.println(lruCache.map.size()); } System.out.println(lruCache.map); LruCache. Put (10200); System.out.println(lruCache.map); }Copy the code

Second implementation (double linked list + HashMap)

public class LRUCache { private int capacity; private Map<Integer,ListNode>map; private ListNode head; private ListNode tail; public LRUCache2(int capacity){ this.capacity = capacity; map = new HashMap<>(); head = new ListNode(-1,-1); tail = new ListNode(-1,-1); head.next = tail; tail.pre = head; } public int get(int key){ if (! map.containsKey(key)){ return -1; } ListNode node = map.get(key); node.pre.next = node.next; node.next.pre = node.pre; return node.val; } public void put(int key,int value){ if (get(key)! =-1){ map.get(key).val = value; return; } ListNode node = new ListNode(key,value); map.put(key,node); moveToTail(node); if (map.size() > capacity){ map.remove(head.next.key); head.next = head.next.next; head.next.pre = head; }} private void moveToTail(ListNode node) {node.pre = tail.pre; tail.pre = node; node.pre.next = node; node.next = tail; } private class ListNode{int key; int val; ListNode pre; ListNode next; Public ListNode(int key,int val){this.key = key; this.val = val; pre = null; next = null; }}}Copy the code

Like the first way, it would be easier to copy removeEldestEntry, so here’s a quick example

public class LRUCache extends LinkedHashMap<Integer,Integer> { private int capacity; @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; }}Copy the code