Why prefer DoubleLinkedList instead of queue and hashmap to design Least recently used (LRU)?

Question

I am solving leetcode LRU design problem - Leetcode LRU:

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.

int get(int key) Return the value of the key if the key exists, otherwise return -1.

void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

I designed it with using Queue and HashMap, and I was able to pass 20 out of 22 test cases. However, the remaining test cases are timing out.

On searching, I found that a doubly linked list is the best way to implement it. I am curious as why queue and hash map is timing out and why a doubly linked list is the best way to solve this.

Below is my implementation:

class LRUCache {
    int capacity=0;
    BlockingQueue<Integer> queue;
    Map<Integer, Integer> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        queue = new ArrayBlockingQueue<Integer>(capacity);
    }
    
    public int get(int key) {
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            return map.get(key);
        }
        else
            return -1;
    }
    
    public void put(int key, int value) {
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            map.put(key, value);
        }
        else if(queue.size()<capacity){
            queue.add(key);
            map.put(key,value);
            
        }
        else{
            int oldKey = queue.remove();
            map.remove(oldKey);
            queue.add(key);
            map.put(key,value);
        }
    }
}

The result is as shown below:

enter image description here

What do you think is the asymptotic performance of queue.remove(key) and queue.contains(key)? — Louis Wasserman
– Louis Wasserman, Commented May 28, 2024 at 6:43
O(n) as per my understanding. how does this help? @Louis Wasserman — Karthik G Sarode
– Karthik G Sarode, Commented May 28, 2024 at 7:00
@KarthikGSarode, the code challenge specifically mentions that "get and put must each run in O(1) average time complexity." — trincot
– trincot, Commented May 28, 2024 at 7:23

trincot · Accepted Answer · 2024-05-28 07:12:00Z

The method calls queue.remove(key) and queue.contains(key) do not have O(1) time complexity. See the documentation on ArrayBlockingQueue which mentions that this queue is "...backed by an array", i.e. it needs to scan the array to locate a given value. This has O(𝑛) time complexity. This is enough reason not to use it for this challenge. On top of that, the operations use locking to avoid concurrency problems which make them even slower. The documentation on remove has:

remove

public boolean remove(Object o)

[...] Removal of interior elements in circular array based queues is an intrinsically slow and disruptive operation, so should be undertaken only in exceptional circumstances, ideally only when the queue is known not to be accessible by other threads.

Doubly linked list

You mention doubly linked lists: Java even has a doubly linked list implementation that is combined with a hash map: a LinkedHashMap.

The documentation mentions:

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

And that is exactly what you need here. The implementation could be:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    int capacity;  
    
    public LRUCache(int capacity) {
        // Foresee one more than desired capacity, so no extension is needed
        // when we allow a temporary overrun before deleting the eldest entry
        super(capacity + 1, 1, true); // true will enable the LRU behavior
        this.capacity = capacity;
    }

    // This method is called internally by put, getOrDefault (and similar).
    //    See documentation
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> entry) {
        return this.size() > this.capacity; // overrun detected: ask for removal
    }
    
    public int get(int key) {
        return getOrDefault(key, -1);
    }
}

thanks for the answer, and you code!! GOD I've never seen such short implementation. very brilliant!

Collectives™ on Stack Overflow

Why prefer DoubleLinkedList instead of queue and hashmap to design Least recently used (LRU)?

1 Answer 1

remove

Doubly linked list

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

remove

Doubly linked list

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related