LRUTest: Least Recently Used to get put pot, LRUTest: Least Recently Used to get put pot, LRUTest: Least Recently Used to get put pot, LRUTest: Least Recently Used to get put pot Hot elements in front, cold elements in the back, will be eliminatedCopy the code

1. The code is as follows

1.1 LRU. Java:

package com.yuhl;

import java.util.HashMap;

/ * * *@author yuhl
 * @Date2020/10/24 now *@Classname LRUTest
 * @DescriptionLRUTest: Least Recently Used to get * pot, get method write * LRU algorithm implementation: two-way list +HashMap implementation LRU algorithm, do not allow LinkedHashMap */
public class LRU {


    /** * Node Node definition */
    class Node{
        int key;
        int value;
        Node pre;
        Node next;
    }

    public HashMap<Integer,Node> hashMap ;
    public Node head;
    public Node tail;
    public int capacity;
    public int size;

    public LRU(int capacity) {
        this.head = new Node();
        this.tail = new Node();
        this.hashMap = new HashMap<>();
        this.head.next = tail;
        this.tail.pre = head;
        this.capacity = capacity;
        this.size = 0;
    }

    // Insert the header when hotspot data is used
    public void addNode(Node node){
        node.pre = this.head;
        node.next = this.head.next;

        this.head.next.pre = node;
        this.head.next = node;
    }

    // Put the cold one at the end of the list
    public void moveToHead(Node node){
        removeNode(node);
        addNode(node);
    }

    / / delete node
    public void removeNode(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // Remove and return the last element
    public Node popTail(a){
        Node res = this.tail.pre;
        removeNode(this.tail.pre);
        return res;
    }

    // Add elements
    public void put(int key,int value){
        Node node = new Node();
        node.key = key;
        node.value = value;

        Node oldNode = this.hashMap.get(key);
        // There is no key duplication
        if(oldNode == null){
            addNode(node);
            this.hashMap.put(key,node);

            // Remove the oldest node if the size exceeds
            if(+ +this.size>capacity){
                Node tail = popTail();
                this.hashMap.remove(tail.key); size --; }}else{
            // Update the value and set the endoldNode.value = value; moveToHead(oldNode); }}public int get(int key){
        Node node = this.hashMap.get(key);
        if(node == null) return -1;
        moveToHead(node);
        returnnode.value; }}Copy the code

1.2 lrutest.java: test class

package com.yuhl;

import java.util.HashMap;

/ * * *@author yuhl
 * @Date 2020/10/24 23:02
 * @Classname LRUTest
 * @DescriptionTest LRU algorithm * when 5 is added and squeezed out */
public class LRUTest {
    public static void main(String[] args) {
        LRU lru = new LRU(4);
        lru.put(1.1);
        lru.put(2.2);
        lru.put(3.3);
        lru.put(4.4);
        lru.put(5.5);
        int i = lru.get(4);
        System.out.println(i);

        System.out.println(lru.hashMap);//5 is added and squeezed out}}Copy the code

2. Execution Results:

"C: \ Program Files \ Java \ jdk1.8.0 _201 \ bin \ Java exe" 
4
{2=com.yuhl.LRU$Node@1b6d3586, 3=com.yuhl.LRU$Node@4554617c, 4=com.yuhl.LRU$Node@74a14482, 5=com.yuhl.LRU$Node@1540e19d}
Copy the code