Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
HashMap + Doubly LinkedList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 public class LRUCache { int capacity; HashMap<Integer, Node> cache; Node head; Node tail; public LRUCache (int capacity) { this .capacity = capacity; cache = new HashMap<>(); head = new Node(0 , 0 ); tail = new Node(0 , 0 ); head.prev = null ; head.next = tail; tail.next = null ; tail.prev = head; } public int get (int key) { Node node = cache.get(key); if (node != null ) { deleteNode(node); addToHead(node); return node.value; } return -1 ; } public void set (int key, int value) { Node existing = cache.get(key); if (existing != null ) { deleteNode(existing); existing.value = value; addToHead(existing); } else { if (cache.size() >= capacity) { cache.remove(tail.prev.key); deleteNode(tail.prev); } Node node = new Node(key, value); cache.put(key, node); addToHead(node); } } public void deleteNode (Node node) { node.prev.next = node.next; node.next.prev = node.prev; } public void addToHead (Node node) { node.next = head.next; node.next.prev = node; head.next = node; node.prev = head; } public class Node { int key; int value; Node prev; Node next; public Node (int key, int value) { this .key = key; this .value = value; } } }
LinkedHashMap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class LRUCache { Map<Integer, Integer> map; public LRUCache (int capacity) { map = new LinkedHashMap<Integer, Integer>(16 , 0.75f , true ){ protected boolean removeEldestEntry (Map.Entry eldest) { return size() > capacity; } }; } public int get (int key) { return map.getOrDefault(key, -1 ); } public void set (int key, int value) { map.put(key, value); } }