- To construct aLRU CacheIt should have the following two methods:getandset
- Get (key): returns the value of the key if it exists in the Cache (assuming a positive number), otherwise -1.
- Set (key, value) : Sets a new value. If a key exists in the Cache, a new value is inserted. If Cache reaches capacity, the most unused item should be deleted before inserting a new one.
- For example:
// Let’s say we have a LRU cache of capacity 2.
LRUCache cache = new LRUCache(2);
cache.set(1, 10); // it will store a key (1) with value 10 in the cache.
cache.set(2, 20); // it will store a key (2) with value 20 in the cache.
cache.get(1); // returns 10
cache.set(3, 30); // evicts key 2 and store a key (3) with value 30 in the cache.
cache.get(2); // returns -1 (not found)
cache.set(4, 40); // evicts key 1 and store a key (4) with value 40 in the cache.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 30
cache.get(4); // returns 40
Copy the code– answer
- The violent method assumes that we have an array of storage nodes, each containing the following information
class Node { int key; int value; // it shows the time at which the key is stored. // We will use the timeStamp to find out the // least recently used (LRU) node. int timeStamp; public Node(int key, int value) { this.key = key; this.value = value; // currentTimeStamp from system this.timeStamp = currentTimeStamp; }}Copy the codeThe size of the array is Cache to capacity.
- Get (int key): iterates, returns value if there is one, returns -1 otherwise. Time complexity: O(n)
- Set (int key, int value) : If the array is full, we need to delete an element from the array. In order to find LRU to the Node Node, we iterate, timeStamp to find the oldest value. You can then insert the new to the Node Node. If the array is not full, we directly insert the new Node into Node. Time complexity: O(n)
- The best way to solve this problem to the point is to use a double-ended queue because it can move Nodes quickly. The LRU Cache is a key-node HashMap that allows get() to run O(1). A double-ended queue can be a Node operation: Adding/Removal to a time complexity O(1).
import java.util.HashMap; class Node { int key; int value; Node pre; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } class LRUCache { private HashMap<Integer, Node> map; private int capacity, count; private Node head, tail; public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.pre = head; head.pre = null; tail.next = null; count = 0; } public void deleteNode(Node node) { node.pre.next = node.next; node.next.pre = node.pre; } public void addToHead(Node node) { node.next = head.next; node.next.pre = node; node.pre = head; head.next = node; } // This method works in O(1) public int get(int key) { if (map.get(key) ! = null) { Node node = map.get(key); int result = node.value; deleteNode(node); addToHead(node); System.out.println("Got the value : " + result + " for the key: " + key); return result; } System.out.println("Did not get any value" + " for the key: " + key); return -1; } // This method works in O(1) public void set(int key, int value) { System.out.println("Going to set the (key, " + "value) : (" + key + ", " + value + ")"); if (map.get(key) ! = null) { Node node = map.get(key); node.value = value; deleteNode(node); addToHead(node); } else { Node node = new Node(key, value); map.put(key, node); if (count < capacity) { count++; addToHead(node); } else { map.remove(tail.pre.key); deleteNode(tail.pre); addToHead(node); } } } } public class TestLRUCache { public static void main(String[] args) { System.out.println("Going to test the LRU " + " Cache Implementation"); LRUCache cache = new LRUCache(2); // it will store a key (1) with value // 10 in the cache. cache.set(1, 10); // it will store a key (1) with value 10 in the // cache. cache.set(2, 20); System.out.println("Value for the key: 1 is " + cache.get(1)); // returns 10 // evicts key 2 and store a key (3) with // value 30 in the cache. cache.set(3, 30); System.out.println( "Value for the key: 2 is " + cache.get(2)); // returns -1 (not found) // evicts key 1 and store a key (4) with // value 40 in the cache. cache.set(4, 40); System.out.println( "Value for the key: 1 is " + cache.get(1)); // returns -1 (not found) System.out.println("Value for the key: 3 is " + cache.get(3)); // returns 30 System.out.println("Value for the key: 4 is " + cache.get(4)); // return 40 } }Copy the codeOutput:
Going to test the LRU Cache Implementation
Going to set the (key, value) : (1, 10)
Going to set the (key, value) : (2, 20)
Got the value : 10 for the key: 1
Value for the key: 1 is 10
Going to set the (key, value) : (3, 30)
Did not get any value for the key: 2
Value for the key: 2 is -1
Going to set the (key, value) : (4, 40)
Did not get any value for the key: 1
Value for the key: 1 is -1
Got the value : 30 for the key: 3
Value for the key: 3 is 30
Got the value : 40 for the key: 4
Value for the key: 4 is 40
Copy the codeAnother way to do this: use LinkedHashMap. RemoveEldestEntry () has been rewritten so that old Mapping needs to be removed when the size exceeds the capacity.
import java.util.LinkedHashMap; import java.util.Map; class LRUCache { private LinkedHashMap<Integer, Integer> map; private final int CAPACITY; public LRUCache(int capacity) { CAPACITY = capacity; Map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) { protected boolean removeEldestEntry(Map.Entry eldest) { return size() > CAPACITY; }}; } // This method works in O(1) public int get(int key) { System.out.println("Going to get the value " + "for the key : " + key); return map.getOrDefault(key, -1); } // This method works in O(1) public void set(int key, int value) { System.out.println("Going to set the (key, " + "value) : (" + key + ", " + value + ")"); map.put(key, value); } } public class TestLRUCacheWithLinkedHashMap { public static void main(String[] args) { System.out.println("Going to test the LRU "+ " Cache Implementation"); LRUCache cache = new LRUCache(2); // it will store a key (1) with value // 10 in the cache. cache.set(1, 10); // it will store a key (1) with value 10 in the cache. cache.set(2, 20); System.out.println("Value for the key: 1 is " + cache.get(1)); // returns 10 // evicts key 2 and store a key (3) with // value 30 in the cache. cache.set(3, 30); System.out.println("Value for the key: 2 is " + cache.get(2)); // returns -1 (not found) // evicts key 1 and store a key (4) with // value 40 in the cache. cache.set(4, 40); System.out.println("Value for the key: 1 is " + cache.get(1)); // returns -1 (not found) System.out.println("Value for the key: 3 is " + cache.get(3)); // returns 30 System.out.println("Value for the key: 4 is " + cache.get(4)); // return 40 } }Copy the codeOutput:
Going to test the LRU Cache Implementation
Going to set the (key, value) : (1, 10)
Going to set the (key, value) : (2, 20)
Going to get the value for the key : 1
Value for the key: 1 is 10
Going to set the (key, value) : (3, 30)
Going to get the value for the key : 2
Value for the key: 2 is -1
Going to set the (key, value) : (4, 40)
Going to get the value for the key : 1
Value for the key: 1 is -1
Going to get the value for the key : 3
Value for the key: 3 is 30
Going to get the value for the key : 4
Value for the key: 4 is 40
Copy the codeRefer to the article
Design a data structure for LRU Cache