19. Implementation, application and solution of LRU Cache

Cache Cache

Let’s take a look at caches and how they are used in real life. Caches are called caches. For example, the Fibonacci sequence and stair climbing problems mentioned in previous articles require a memorized search. Python can be written directly with the @lru Cache. So what exactly is a cache? In reality, there are many applications.

  1. memory
  2. Wallet. – Locker
  3. Code modules

Such as our human memory, in fact, most of the time is a cache, a lot of things we will written down on a piece of paper, write in the books, because we are afraid we can’t remember, benefit is the book that will exist forever, but the problem is that you want to load it to your brain, need to spend a lot of time, often with Ken, we in mind, It’s incredibly fast, but the problem is that it’s often wrong or it’s forgotten, and that’s the problem with memory being a cache.

Cache itself, from the WORDS of THE CPU to say a lot, for example, we just contact with computing when the hardware is more interested in, especially famous at that time is Intel processor.


It was a L1 cache, a L2 cache, a L3 cache, so it had what’s called a level 3 cache.


Understanding the Meltdown exploit — in my own simple words

Here it is a CPU with four cores, each core has L1 D-cache, L1 L-cache, L2 Cache, L3 Cache, refers to the most commonly used data, immediately to the CPU computing module for calculation processing, put in L1, other words more out of the system. The second most commonly used Cache is L1 L-cache, the second is L2 Cache, and the third is L3 Cache. Of course, the external Cache is the memory, which is faster than the previous one, but the volume of the data can be stored in L3 Cache is definitely the largest. L1 D-cache is the smallest. This is what it calls a caching mechanism.

LRU Cache

When it comes to caching, there are two basic features:

Two elements: size, replacement strategy

  • The first one is what is the total size of the cache? If the cache is very large like the CPU cache against one ram, if you have one gigabyte of cache, then a lot of stuff just goes into it. For people, this person has a very good memory.
  • The second one is its replacement strategy, that is, I have the fastest L1, but I don’t have enough capacity, so what are we going to put the infrequently used ones behind, and how do we identify the infrequently used ones, and that’s what we’re going to get the so-called replacement algorithm.

Hash Table + Double LinkedList Hash Table + Double LinkedList Hash Table + Double LinkedList Refers to the least recently used wants it to go out at the end of it in general, it is the realization of the last word in the hash table to add a two-way linked list to achieve, such a structure can query time complexity is O (1), that is to say whether this element exists, can be directly in the hash table inside the time of O (1) can be detected, In the meantime, if you want to make changes and updates, the specific elements are stored in the Double LinkedList, or you can use O(1) time to make changes and updates.

  • The O (1) the query
  • O(1) Modify and update

Example of LRU Cache working


This is the LRU Cache, which is just a chunk of memory in this place, and of course its underlying data structure, which is a bidirectional linked list, and of course a hash table in this place. The least recently used element of the LRU Cache will be removed from the Cache.

Replacement strategy

  • LFU – Least frequently used
  • Lru-least recently used

Replacement algorithm overview: https://en.wikipedia.org/wiki/Cache_replacement_policies

Practical subject

146.LRU caching mechanism

The two operations in this case require a hash table and a bidirectional linked list. In interviews, readers are expected to implement a simple two-way linked list on their own, rather than using the language’s built-in, encapsulated data structures. In Python, OrderedDict, a data structure that combines hash tables and bidirectionally linked lists, can do this in just a few lines of code. In the Java language, there is a similar data structure called LinkedHashMap.

Method 1: The Java language built-in LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer>{

    private int capacity;



    public LRUCache(int capacity) {

Super (capacity and 0.75 F,true);

        this.capacity = capacity;

    }

    

    public int get(int key) {

        return super.getOrDefault(key, -1);

    }

    

    public void put(int key, int value) {

        super.put(key, value);

    }

    

    @Override

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {

        return size() > capacity;

    }

}

Copy the code

Method two: hash table + bidirectional linked list

The algorithm LRU caching mechanism can be implemented through a hash table with a bidirectional linked list. We maintain all key value pairs in the cache with a hash table and a bidirectional linked list.

  • The bidirectional list stores the key-value pairs in the order in which they are used, with the key-value pairs near the head being the most recent and the key-value pairs near the tail being the oldest.
  • A hash table is a common HashMap that maps the location of the cached data in a bidirectional linked list through its keys.

In this way, we first use the hash table to locate the cache item in the bidirectional list, and then move it to the head of the bidirectional list to complete the GET or PUT operation in O(1) time. Specific methods are as follows:

  • forgetOperation, first judgekeyDoes it exist:
    • If key does not exist, -1 is returned;
    • If a key exists, the node corresponding to the key is the most recently used node. Hash table is used to locate the node in the bidirectional linked list, move it to the head of the bidirectional linked list, and finally return the value of the node.
  • forputFirst judgekeyDoes it exist:
    • If the key does not exist, create a new node using key and value, add the node to the head of the bidirectional list, and add the key and the node to the hash table. Then determine whether the nodes of the bidirectional linked list exceed the capacity, if so, delete the tail nodes of the bidirectional linked list and delete the corresponding items in the hash table;
    • If the key exists, it is located through the hash table, then updates the value of the corresponding node to value, and moves the node to the head of the bidirectional list.

In the above operations, the time complexity of accessing the hash table is O(1), and the complexity of adding nodes at the head of the bidirectional list and deleting nodes at the tail of the bidirectional list is also O(1). Moving a node to the head of the bidirectional linked list can be divided into two steps: “delete the node” and “add node to the head of the bidirectional linked list”, both of which can be completed in O(1) time.

class LRUCache {

    class DLinkedNode {

        int key;

        int value;

        DLinkedNode prev;

        DLinkedNode next;

        public DLinkedNode() {}

        public DLinkedNode(int key, int value) {

            this.key = key;

            this.value = value;

        }

    }



    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();

    private int size;

    private int capacity;

    private DLinkedNode head, tail;



    public LRUCache(int capacity) {

        this.size = 0;

        this.capacity = capacity;

// Use false headers and false tails

        head = new DLinkedNode();

        tail = new DLinkedNode();

        head.next = tail;

        tail.prev = head;

    }

    

    public int get(int key) {

        DLinkedNode node = cache.get(key);

        if (node == null) {

            return- 1;

        }

// If the key exists, the hash table is used to locate the key, and then move to the header

        moveToHead(node);

        return node.value;

    }

    

    public void put(int key, int value) {

        DLinkedNode node = cache.get(key);

        if (node == null) {

// If the key does not exist, create a new node

            DLinkedNode newNode = new DLinkedNode(key, value);

// Add to the hash table

            cache.put(key, newNode);

// Add to the head of the bidirectional list

            addToHead(newNode);

            ++size;

            if (size > capacity) {

// If the capacity exceeds, delete the tail node of the bidirectional list

                DLinkedNode tail = removeTail();

// Delete the corresponding entry in the hash table

                cache.remove(tail.key);

                --size;

            }

        } else {

// If the key exists, locate it through the hash table first, then modify the value and move it to the header

            node.value = value;

            moveToHead(node);

        }

    }



    private void addToHead(DLinkedNode node) {

        node.prev = head;

        node.next = head.next;

        head.next.prev = node;

        head.next = node;

    }



    private void removeNode(DLinkedNode node) {

        node.prev.next = node.next;

        node.next.prev = node.prev;

    }



    private void moveToHead(DLinkedNode node) {

        removeNode(node);

        addToHead(node);

    }

    

    private DLinkedNode removeTail() {

        DLinkedNode res = tail.prev;

        removeNode(res);

        return res;

    }

}

Copy the code
LRUCache cache = new LRUCache(2 /* Cache capacity */);



cache.put(1, 1);

cache.put(2, 2);

cache.get(1); / / returns 1

cache.put(3, 3); // This operation invalidates keyword 2

cache.get(2); // return -1 (not found)

cache.put(4, 4); // This operation invalidates keyword 1

cache.get(1); // return -1 (not found)

cache.get(3); / / return 3

cache.get(4); / / return 4

Copy the code

Complexity analysis

  • Time complexity: For both PUT and GET.
  • Spatial complexity: because hash tables and bidirectional linked lists store at most one element.

Some pictures from the network, copyright to the original author, delete.Copy the code