Interviewer: Here we go, buddy. LRU cache implementation?

Me: Just LinkedHashMap.

Interviewer: Don’t use an existing implementation, implement one yourself.

I:…

Interviewer: Go back and wait for the news….

Hello everyone, I am a senior programmer, today we are going to talk about LRU cache.

LRU is ubiquitous in computer software. I hope you must understand it thoroughly.

Problem description

LRU(least recently used) cache structure is designed. The structure determines the size when it is constructed, assuming the size is K, and has the following two functions: 1. Set (key, value) : inserts records (key, value) into the structure; 2Copy the code

To analyze problems

From the problem description, we know that the LRU cache contains two types of operations, namely Set and Get operations.

For Set operations, there are two cases.

  1. If it already exists in the cache. Moves the corresponding element in the cache to the cache header.
  2. If it doesn’t exist in cache. Add the element to the cache header. If the cache size exceeds the limit, delete the last element in the cache.

There are also two cases for Get operations.

  1. If it exists in the cache. Moves the element in the cache to the cache header and returns the corresponding value.
  2. If it doesn’t exist in cache. Return -1.

To sum up: There are three main operations for an LRU cache.

  1. Find an element.
  2. Deletes an element at the end of the cache.
  3. Add an element to the cache header.

So, the easiest thing to think of is to use a linked list to implement LRU caching. We can maintain an ordered single linked list, and nodes closer to the end of the list are accessed earlier. When we perform a Set operation, we iterate sequentially from the list head. There are two cases of traversal.

  1. If the data is already in the list, we iterate to get the node that corresponds to the data and move it from that position to the head of the list.
  2. If this data is not in the linked list, there are two cases. If the list is not full, we insert the node directly into the head of the list. If the list is full at this point, we delete a node from the end of the list and insert the new data node into the head of the list.

When we do Get, we iterate sequentially from the list head. There are two cases of traversal.

  1. If this data is in a linked list. We iterate to get the node that this data corresponds to, then move it from that position to the head of the list, and return the value of that node.
  2. If this data is not in the linked list. Let’s go straight back to negative 1.

Let’s take a look at how the code works.

class LinkedNode:
    def __init__(self, key=0, value=0) :
        self.key = key
        self.value = value
        self.next = None

class LRUCache() :
    def __init__(self, capacity: int) :
        # use dummy header nodes
        self.capacity=capacity
        self.head = LinkedNode()
        self.head.next=None
        self.size = 0

    def get(self, key: int) - >int:

        cur=self.head.next
        pre=self.head

        whilecur! =None:
            if cur.key==key:
                pre.next = cur.next
                cur.next = self.head.next
                self.head.next = cur
                break
            pre=pre.next
            cur=cur.next

        ifcur! =None:
            return cur.value
        else:
            return -1

    def put(self, key: int, value: int) - >None:

        cur = self.head.next
        pre = self.head
        
        # Cache has no elements, add them directly
        if cur==None:
            node = LinkedNode()
            node.key = key
            node.value = value
            self.head.next = node
            self.size = self.size + 1
            return

        There are elements in the cache
        whilecur! =None:
            # indicates that it already exists
            if cur.key == key:
                # put the element in the head of the list anyway
                cur.value=value
                pre.next = cur.next
                cur.next = self.head.next
                self.head.next = cur
                break

            # represents the last element of the current element
            if cur.next= =None:
                If the cache is full at this point, eliminate the last element
                if self.size==self.capacity:
                    pre.next=None
                    self.size=self.size-1
                node=LinkedNode()
                node.key=key
                node.value=value
                node.next=self.head.next
                self.head.next=node
                self.size=self.size+1
                break
                
            pre = pre.next
            cur=cur.next
Copy the code

We have thus implemented an LRU cache using a singly linked list. Let’s examine the time complexity of cache access. For a Set, we need to go through the list whether the cache is full or not, so the time is order n. For Get, the list is also iterated, so the time complexity is also O(n).

To optimize the

From the above analysis, we can see that. If we use a single linked list to implement LRU, no matter the Set or Get operation, we need to traverse the list to find whether the current element exists in the cache. The time complexity is O (n), so can we optimize it? We know that with a hash table, we can reduce the time of finding elements to O (1). If we could use a hash table instead of doing that, wouldn’t that reduce the time of finding elements? Based on this logic, we use a combination of hash and linked lists to achieve an efficient LRU cache.

class LinkedNode:
    def __init__(self, key=0, value=0) :
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int) :
        self.cache = dict()
        self.head = LinkedNode()
        self.tail = LinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) :
        # If key does not exist, return -1
        if key not in self.cache:
            return -1
        Hash the position and delete it without traversing the search process
        node = self.cache[key]
        self.moveHead(node)
        return node.value

    def put(self, key: int, value: int) - >None:
        if key not in self.cache:
            If the key does not exist, create a new node
            node = LinkedNode(key, value)
            # add to hash table
            self.cache[key] = node
            self.addHead(node)
            self.size += 1
            if self.size > self.capacity:
                Delete the end node of the bidirectional list if it exceeds capacity
                removed = self.removeTail()
                Delete the corresponding entry in the hash table
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveHead(node)

    def addHead(self, node) :
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node) :
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveHead(self, node) :
        self.removeNode(node)
        self.addHead(node)

    def removeTail(self) :
        node = self.tail.prev
        self.removeNode(node)
        return node
Copy the code

conclusion

LRU caching is something we come across all the time, both at work and in interviews. I hope this article has been helpful to you. \

When a hash table meets a linked list

That’s all for today. More interesting knowledge, please pay attention to the public number [senior programmer].

The more you know, the more your mind opens up. See you next time.