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

package com.LRU;

import java.util.StringJoiner;
import java.util.concurrent.ConcurrentHashMap;

public class LUR20210428<K.V> {

    /** * Initializes the LRU cache class **@paramCacheSize Cache chain size */
    LUR20210428(int cacheSize){
        // Cache chain size
        this.cacheSize=cacheSize;
        // Initialize the map size
        data=new ConcurrentHashMap<>(cacheSize);

        // Initialize the head of the chain
        first=new Node();
        first.last=null;
        // Initializes the end of the chain
        penultimate=new Node();
        penultimate.nest=null;

        // Initializes the end of the chain
        first.nest=penultimate;
        penultimate.last=first;
    }
    // The length of the cached data
    private int cacheSize;
    // Current data size
    private int count=0;
    // The first node
    private Node first;
    // The last node
    private Node penultimate;
    // The structure to store data
    ConcurrentHashMap<K,Node> data;

    // Class to store data
    class Node{
        Node last;
        Node nest;
        K key;
        V value;
    }
    // Get the data size
    int getSize(a){
        return count;
    }

    /** * Get data from key *@param key
     * @return* /
    public synchronized V get(K key){
        Node node = data.get(key);
        if(node==null) {return null;
        }
        // If the data is not null, delete the node in the chain
        removeOne(node);
        // Then add the node to the header
        insertFirst(node);
        return  data.get(key).value;
    }

    /** * Add cached data *@param key
     * @param value
     * @return* /
    public synchronized Boolean put(K key,V value){
        Node node = data.get(key);
        if(node! =null) {// Delete the data in the chain and add it to the header
            node.value=value;
            removeOne(node);
            insertFirst(node);
        }else {
            // Create a new node without that data and add it to the header
            node = new Node();
            node.key=key;
            node.value=value;
            insertFirst(node);
        }
        // Finally update to map
        data.put(key,node);
        return true;
    }

    /** * Delete node * by key@param key
     * @return* /
    public synchronized Boolean remove(K key){
        Node node = data.get(key);
        if(node! =null){
            removeOne(node);
            return true;
        }
        return false;
    }


    /** * The private method adds node to the header *@param node
     * @return* /
    private Node insertFirst(Node node){

        // If the data size is close to the cache size, delete the last data
        if (count>=cacheSize){
            removeLastOne();
        }
        // Insert the data into the node after first
        Node oldFirst = first.nest;
        oldFirst.last=node;
        node.nest=oldFirst;

        node.last=first;
        first.nest=node;
        count++;
        return node;
    }

    /** * Private delete node and delete map data *@param node
     */
    private void removeOne(Node node){
        data.remove(node.key);
        Node last= node.last;
        Node nest= node.nest;
        last.nest=nest;
        nest.last=last;
        count--;
    }

    /** * privatize delete the last obsolete node */
    private void removeLastOne(a){
        // Delete data from data
        data.remove(penultimate.last.key);
        // Then delete the data at the end of the chain
        Node needRemoveNode = penultimate.last;
        Node newPenultimate  = needRemoveNode.last;
        newPenultimate.nest=penultimate;
        penultimate.last=newPenultimate;
        count--;
    }


    /** * visual output chain number and chain structure easy to view the running process */
    public void printLink(a){
        StringJoiner stringJoiner=new StringJoiner(">");
        Node firstNode=first.nest;
        while(firstNode.nest! =null){
            stringJoiner.add(firstNode.key+"");
            firstNode=firstNode.nest;
        }
        System.out.println( "count :"+count+"|"+ stringJoiner.toString()); }}Copy the code

test

package com.LRU;

import java.util.concurrent.locks.ReentrantLock;

public class test {
    public synchronized  static void main(String[] args) {

        LUR20210428<Integer,Integer> lruCache= new LUR20210428<Integer, Integer>(4);
        lruCache.put(1.10);
        lruCache.put(2.20);
        lruCache.put(3.30);

        lruCache.printLink();
        lruCache.put(4.40);
        lruCache.printLink();
        lruCache.put(4.40);
        lruCache.printLink();
        lruCache.put(4.40);
        lruCache.printLink();
        lruCache.put(5.50);
        lruCache.printLink();
        lruCache.remove(4);
        lruCache.remove(5); lruCache.printLink(); }}Copy the code

Modified adding map for thread safety