1. Introduction

LRU stands for Least Recently Used. It is a common page replacement algorithm that selects the pages that have not been Used for the most recent time to eliminate the page. The algorithm assigns each page an access field, which is used to record the time T experienced by a page since it was visited last time. When a page needs to be eliminated, the page with the largest T value in the existing page, that is, the least recently used page, is selected to be eliminated.

2. Principle analysis

LRU algorithm mainly uses two-way linked list + hash table data structure. The time complexity of LRU algorithm can be O(1) by taking advantage of the fast lookup of hash table and the fast insertion and deletion of bidirectional linked list, but the space complexity will be slightly increased as a side effect.

A few points to note:

  1. When data that is already in the cache is manipulated (fetched or added), the manipulated data needs to be moved to the head node of the list.
  2. When the cache capacity is full and data is added, delete the last node of the bidirectional list before adding data.

3. The source code

/** * LRU algorithm Created by MOON **@param <K>
 * @param <V>
 */
public class LruCache<K.V> {
    // LRU algorithm (Least recently used)
    // The algorithm filters out data based on the historical access record of the data. The core idea is that "if the data has been accessed recently, the probability of being accessed in the future is higher".

    // Nodes whose basic data type is bidirectional linked list have precursor nodes and subsequent nodes.
    private class Node {
        private K k;
        private V v;
        private Node pre;
        private Node next;

        public Node(a) {}public Node(K k, V v) {
            this.k = k;
            this.v = v; }}/ / two-way LinkedList
    private class DoubleLinkedList {
        private Node head, tail;
        private int size;

        public DoubleLinkedList(a) {
            // Head and tail are used as sentries. They are not the real head and tail of data
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        // Add nodes to the head of the list
        public void addFirst(Node node) {
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
            node.pre = head;
            size++;
        }

        // Delete a node from the list
        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            size--;
        }

        // Delete the last node in the list
        public Node removeLast(a) {
            if (size > 0) {
                Node last = tail.pre;
                remove(last);
                return last;
            } else {
                return null; }}public int getSize(a) {
            returnsize; }}// Hash table, used to locate data in the cache at O(1) speed
    private HashMap<K, Node> map;
    // Two-way list, used to store cache data, because it is two-way can be added and deleted at O(1) speed
    private DoubleLinkedList cache;
    // Cache capacity
    private int capacity;

    public LruCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleLinkedList();
    }

    / / to get
    public V get(K key) {
        if(! map.containsKey(key)) {return null;
        }
        V value = map.get(key).v;
        // When the cache is manipulated, it needs to be moved to the head of the list
        put(key, value);
        return value;
    }

    / / insert
    public void put(K key, V value) {
        Node node = new Node(key, value);
        if (map.containsKey(key)) {
            cache.remove(map.get(key));
            cache.addFirst(map.get(key));
        } else {
            if (cache.size >= capacity) {
                Node lastNode = cache.removeLast();
                map.remove(lastNode.k);
            }
            cache.addFirst(node);
        }
        map.put(key, node);
    }

    // Prints the key and value
    public void print(a) {
        Set keys = map.keySet();
        Iterator iterator = keys.iterator();

        while (iterator.hasNext()) {
            Object obj = iterator.next();
            System.out.print("key: " + obj);
            System.out.println(" value: "+ map.get(obj).v); }}// Prints the key and value of the last node in the bidirectional list
    public void printLastNode(a) {
        System.out.print("key: " + cache.tail.pre.k);
        System.out.println(" value: "+ cache.tail.pre.v); }}Copy the code