What is LRU Cache and How to Implement it

1. What is LRU Cache

LRU is the abbreviation of Least Recently Used, which means least recently used. It is a Cache replacement algorithm.

1.1 What is Cache?

The Cache in the narrow sense refers to the fast RAM located between the CPU and the main memory. Usually it does not use DRAM technology like the system main memory, but uses the expensive but faster SRAM technology. The Cache in the broad sense refers to the fast RAM located between the CPU and the main memory. A structure used to coordinate the difference in data transmission speed between the two types of hardware. In addition to the Cache between the CPU and the main memory, there is also a Cache between the memory and the hard disk, and even between the hard disk and the network in a certain sense. Cache - known as temporary Internet files or network content cache etc.

2. Why Need LRU Algorithm

The capacity of Cache is limited, so when the capacity of Cache is used up (in fact, it will not really be used up, there will be a water level. If the remaining capacity is lower than this water level, the LRU algorithm needs to be executed), new content will be added. you need to select and discard some of the original content to make room for new content. The replacement principle of LRU Cache is to replace the least recently used content.

3. How to Implement LRU Cache

There are many methods and ideas to implement LRU Cache, but to maintain efficient implementation of O(1) put and get, it is the most efficient and classic to use a doubly linked list and a hash table. Doubly linked lists are used because doubly linked lists can achieve any The insertion and deletion at position O(1) uses a hash table because the addition, deletion, and modification of a hash table is also O(1).

3.1 Code Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class LRUCache<K, V> {

    private final int MAX_CACHE_SIZE = 100;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;

    private LinkedHashMap<K, V> map;

    public LRUCache() {
        int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    public synchronized void removeAll(){
        map.clear();
    }

}