Design LRU cache
20 January, 2014 - 7 min read
You have to design a LRU cache such that all operations can be done in O(1) – read, write and insert.
- In case, cache is full, you have to remove an element which was read/written last.
- Each read should update the timestamp of these elements.
- Read request of the element contains a key which is not the location of the element.
Strategy:
Assuming hashmap has retrieval complexity of O(1), we can do this using a doubly link list and a Hashmap
- Doubly link list will be used to store indexes sorted by date/timestamp information.
- Keep track of first and last node.
- No sorting effort is needed as each new node will have latest timestamp.
- The Hashmap will retrieve the node searched by key. It will also contain pointer to its respective doubly link list node.
READ -
- Search the node by key. Retrieve the node value and index for doubly linklist.
- Delete the node from doubly linked list and add it with the updated date value at the starting of the list.
- Complexity of deleting a node in doubly link list is O(1) as we can reach to it without traversing the list.
INSERT -
- Add the new node in the hashmap and the doubly linked list.
- If the cache is full, use the pointer to the last node in the doubly linked list and delete that node. Set the delete pointer appropriately.
- Inserting at the start of linked list is operation with time O(1).
UPDATE -
- Update operation will need similar operation as READ in terms of accessing the data structure. Hence, similar time complexities apply.
DELETE -
- Deleting the node from the doubly-linked list and hashmap can be done in O(1).
Implementation:
Queue with DLL + HashMap
1: struct LRUCacheNode {
2: int key;
3: int value;
4: LRUCacheNode* prev;
5: LRUCacheNode* next;
6: LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;
7: } ;
8:
9: class LRUCache{
10: private:
11: hash_map< int, LRUCacheNode* > Map;
12: LRUCacheNode * Head;
13: LRUCacheNode * Tail;
14: int Capacity ;
15: int Count ;
16:
17: public:
18: LRUCache(int capacity) {
19: Capacity = capacity ;
20: Count = 0 ;
21: Head = new LRUCacheNode;
22: Tail = new LRUCacheNode;
23: Head->prev = NULL;
24: Head->next = Tail;
25: Tail->next = NULL;
26: Tail->prev = Head;
27: }
28:
29: ~LRUCache ( ) {
30: delete Head;
31: delete Tail;
32: }
33:
34: int get(int key) {
35: LRUCacheNode* node = Map[key];
36: if(node)
37: {
38: DetachNode(node);
39: AttachNodeToFront(node);
40: return node->value;
41: }
42: else
43: return -1 ;
44:
45: }
46:
47: void set(int key, int value) {
48: LRUCacheNode* node = Map[key];
49: if(node)
50: {
51: DetachNode(node);
52: node->value = value;
53: AttachNodeToFront(node);
54: }
55: else{
56: LRUCacheNode* node = new LRUCacheNode ;
57: if ( Capacity == Count ) { // If Cache is Full
58: RemoveLRUNode ( key ) ;
59: }
60:
61: node->key = key;
62: node->value = value;
63: Map[key] = node;
64: AttachNodeToFront(node);
65: Count++ ;
66: }
67: }
68: private:
69: void RemoveLRUNode ( int key ) {
70: LRUCacheNode* node = Tail->prev;
71: DetachNode(node);
72: Map.erase(node->key);
73: Count-- ;
74: }
75:
76: void DetachNode(LRUCacheNode* node) {
77: node->prev->next = node->next;
78: node->next->prev = node->prev;
79: }
80:
81: void AttachNodeToFront(LRUCacheNode* node) {
82: node->next = Head->next;
83: node->prev = Head;
84: Head->next = node;
85: node->next->prev = node;
86: }
87: };