Cache is a technology to improve the performance of data reading. It is widely used in hardware design and software development, such as CPU cache, database cache, browser cache and so on.

The size of the cache is limited. When the cache is full, what data should be purged and what data should be retained? This requires a cache elimination strategy. There are three common FIFO policies: First In, First Out (FIFO), Least Frequently Used LFU (Least Recently Used LRU). LFU (Least Frequently Used)

What is the LRU algorithm?

It’s a cache flushing strategy.

A computer’s cache capacity is limited, and if it fills up, some content has to be deleted to make room for new content. But the question is, what to delete? We want to delete useless caches and keep useful data in the cache for later use. So what kind of data do we define as “useful”?

LRU cache elimination algorithm is a common strategy. The full name of LRU is Least Recently Used, that is, we think that the Recently Used data should be “useful”, and the data that has not been Used for a long time should be useless. When the memory is full, the data that has not been Used for a long time should be deleted first.

Realization idea: bidirectional linked list + hash table

The idea is that when we maintain an ordered single linked list, nodes closer to the end of the list are accessed earlier. When a new data is accessed, we traverse the list sequentially, starting with the list header.

  1. If the data has already been cached in the list, we iterate to get the node corresponding to the data, remove it from its original position, and insert it into the head of the list.
  2. If this data is not in the cache linked list, it can be divided into two cases:
  • If the cache is not full at this point, the node is inserted directly into the head of the list;
  • If the cache is full at this point, the end of the list is deleted and the new data node is inserted into the head of the list.

So we implement an LRU cache using linked lists. Isn’t that easy?

We need to maintain a linked list structure in order of access time from largest to smallest. Because the cache size is limited, when the cache space is insufficient and a data needs to be eliminated, we will directly delete the node in the head of the linked list.

When you want to cache some data, you first look it up in the linked list. If not, the data is placed directly at the end of the list; If we find it, we move it to the end of the list. Because searching for data requires traversing the linked list, the time of LRU cache elimination algorithm realized by simply using the linked list is very complex, which is O(n).

In fact, to summarize, a cache system consists of the following operations:

  • Add data to the cache;
  • Delete a data from the cache
  • Find a piece of data in the cache.

All three operations involve “lookup” operations, and the time complexity is O(n) if you simply use linked lists. If we combine hash and linked list data structures, we can reduce the time complexity of all three operations to O(1). The specific structure is as follows:

Now that we know about the hash table and the bidirectional linked list, how do we get O(1) time for the three operations we talked about in the cache?

First, let’s look at how to find a piece of data. As we mentioned earlier, the time complexity of finding data in a hash table is close to O(1), so we can quickly find a data in the cache with a hash table. Once the data is found, we also need to move it to the end of the bidirectional list.

Second, let’s see how to delete a piece of data. We need to find the node where the data is and delete it. Using hash tables, we can find the node to delete in O(1) time complexity. Because our linked list is a bidirectional linked list, the bidirectional linked list can obtain the precursor node through the time complexity of the precursor pointer O(1), so in the bidirectional linked list, deleting the node only needs the time complexity of O(1).

Finally, let’s see how to add a piece of data. Adding data to the cache is a little tricky, and we need to see if the data is already in the cache. If it is already there, you need to move it to the end of the bidirectional list; If not, it depends on whether the cache is full. If it is full, delete the nodes in the head of the bidirectional list, and then put the data to the end of the list. If not, the data is put directly to the end of the list.

All of the lookups involved in this process can be done using hash tables. Other operations, such as deleting headers and inserting data at the end of lists, can be done in O(1) time. Therefore, the time complexity of all three operations is O(1). So far, through the combination of hash table and bidirectional linked list, we have realized an efficient cache system prototype that supports LRU cache elimination algorithm.

LRU algorithm description

The LRU algorithm actually lets you design data structures: The first is to receive a capacity parameter as the maximum capacity of the cache, and then implement two apis. One is to put(key, val) to store the key-value pair, and the other is to get(key) to retrieve the corresponding val of the key, and return -1 if the key does not exist.

Note that the get and PUT methods must both be O(1) time. Let’s take a concrete example to see how the LRU algorithm works.

/* Cache size is 2 */ LRUCache cache = new LRUCache(2); cache.put(1, 1); // cache = [(1, 1)] cache.put(2, 2); // cache = [(2, 2), (1, 1)] cache.get(1); Cache = [(1, 1), (2, 2)]; cache = [(1, 1), (2, 2)]; // Cache = [(3, 3), (1, 1)]; // Cache = [(3, 3), (1, 1)]; // Cache = [(3, 3); Cache = [(3, 3), (1, 1)]; put(1, 4); // Cache = [(1, 4), (3, 3)Copy the code

Code implementation

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

  • The bidirectional list stores these key-value pairs in the order in which they are used, with the key-value pair near the head being the most recently used and the key-value pair near the tail being the oldest unused.
  • A hash table is an ordinary hash map (HashMap), which maps the cache data to its location in the bidirectional linked list.

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 the key does not exist, -1−1 is returned.

    • If a key exists, the node corresponding to the key is the most recently used node. Hash the node to its position in the bidirectional list, move it to the head of the bidirectional list, and finally return the value of the node.

  • forputOperation, first judgekeyDoes it exist:
    • ifkeyDoes not exist, usekey 和 valueCreate a new node, add it to the head of the bidirectional list, and set thekeyAnd the object is added to the hash table. Then determine whether the number of nodes in the bidirectional linked list exceeds the capacity, if so, delete the tail nodes of the bidirectional linked list, and delete the corresponding items in the hash table;
    • ifkeyExistence, andgetThe operation is similar to that of locating the node through the hash table and then updating the value of the corresponding node tovalueAnd moves the node to the head of the bidirectional list.

In each of 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)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.

public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; 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; 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, move it to the head moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); NewNode = new DLinkedNode(key, value); if (node == null) {// If the key does not exist, create a new node. // Add to the hash table cache.put(key, newNode); // Add to the head of the bidirectional list addToHead(newNode); ++size; If (size > capacity) {// If (size > capacity) {DLinkedNode tail = removeTail(); Remove (tail.key); // Delete the corresponding entry in the hash table cache.remove(tail.key); --size; }} else {// If the key is present, then change 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

Complexity analysis

  • Time complexity: O(1) for put and GET.

  • Space complexity: O(capacity), because hash tables and bidirectional linked lists store maximum capacity+1 element.