Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: get for data and PUT for writing data.

  • To get the dataget(key)– Retrieves the value of the key if it exists in the cache (always positive), otherwise -1 is returned.
  • Write dataput(key, value)– If the keyword already exists, change its data value; If the keyword does not exist, the set of keyword/value is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.

Advanced: Can you do both in O(1) time?

Example:

LRUCache cache = new LRUCache( 2/* Cache capacity */); cache.put(1.1);
cache.put(2.2);
cache.get(1); / / return1
cache.put(3.3); // This operation will make the keyword2Invalid cache. Get (2); / / return -1Cache. Put (Not found)4.4); // This operation will make the keyword1Invalid cache. Get (1); / / return -1Cache.get (not found)3); / / return3
cache.get(4); / / return4
Copy the code

LRU can be read and written using data structures. LRU and other memory replacement strategies in the operating system have been described in the previous source code interpretation of caching and implementation principles in the operating system and Spring Boot, so I will not repeat them here. In short, the LRU selects the least recently used data to replace each time. As follows:


For example, when the page hits the first 3, the cache is full. According to the replacement idea of LRU, the least recently unused ones are selected for replacement. Then only 2 of 0, 1 and 2 in the cache are used the least times and are used the earliest.

If you need to use a data structure to implement LRU, you need to consider the following:

  • How about maintaining access records between different data in the cache?
  • How do I maintain the number and time of page visits to provide a basis for substitution?

For the first problem, since data access is sequential, we can maintain sequential relationships between data using a bidirectional linked list, with the earlier accessed elements closer to the head of the list. For the second problem, we need to arrange the data according to the time and number of accesses, and the time complexity is O(1), so the best choice is a hash table. Therefore, LRU can be implemented as a whole using a linked list + hash table structure. In addition, we need to complete data reading and writing in O(1) time complexity, so the linked list node should contain the key and value information of the data. In addition, the hash table only needs to save the key, according to the key can access the corresponding value in the linked list.

The data structure of linked list + hash table exactly corresponds to LinkedHashMap in Java. Of course, you can also customize linked list and hash table, and establish the mapping relationship between them. LinkedHashMap will be used directly as the solution, and Python will also be used to customize linked lists and hash tables to implement LRU.

Java solution code:

class LRUCache {
	// Cache capacity
    private int capacity;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    
    public LRUCache(int capacity) {
        // Initialize the size of the memory space
        this.capacity = capacity;
    }
    
    public int get(int key) {
        // First check whether the given key exists
        if(cache.containsKey(key)){
            // Change the state to recently used
            makeRecently(key);
            // Take the value directly from cache
            return cache.get(key);
        }
        return -1;
    }
    
    public void put(int key, int value) {
        // If there is a value in the given key, the value is only updated
        if(cache.containsKey(key)){
            // The incoming value overwrites the old value
            cache.put(key, value);
            // Change the status of the key to recent use
            makeRecently(key);
            return;
        }
		
        // If the cache is full at this point, it needs to be flushed
        if(cache.size() >= this.capacity){
        	The oldest data is the first element in the cache
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
		// Otherwise, save directly to the cache
        cache.put(key, value);

    }

    public void makeRecently(int key){
        int value = cache.get(key);
		// Remove first before adding to the tailcache.remove(key); cache.put(key, value); }}Copy the code

Python problem solving code[official question], using false headers and false tails to set list boundaries, and using the most recently accessed element as the head element of the list. If you change to the same logic as above, you only need to modify the operation to update the linked list insert element:

class DLinkedNode:
    def __init__(self, key=None, value=None) :
        self.key = key
        self.value = value
        self.pre = None
        self.next = None


class LRUCache:

    def __init__(self, capacity) :
        self.cache = dict()
        self.capacity = capacity
        self.size = 0
  
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        

    def get(self, key: int) - >int:
        if key not in self.cache:
            return -1
            
        If the key is present, the hash table is used to locate the key and then move it to the header
        node = self.cache[key]
        self.moveToHead(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 = DLinkedNode(key, value)
            # add to hash table
            self.cache[key] = node
            Add to the head of the bidirectional list
            self.addToHead(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:
            If the key is present, the hash table is used to locate the value, and then the value is moved to the header
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
    
    def addToHead(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 moveToHead(self, node) :
        self.removeNode(node)
        self.addToHead(node)

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