LRU（Least Recently Used）(最近最少使用)

1. 新資料插入到連結清單頭部；
2. 每當緩存命中(即緩存資料被通路)，則将資料移到連結清單頭部；
3. 當連結清單滿的時候，将連結清單尾部的資料丢棄。

package com.hmx.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: datastructureandalgorithm
 * @description:
 * @author: hmx
 * @create: 2021-06-29 20:51
 **/
public class LRU {
    class Node{
        int key;
        int value;
        Node prev;
        Node next;
    }

    Node first;
    Node last;
    int capacity;
    Map<Integer, Node> map;

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

    public int get(int key){
        Node node = map.get(key);
        if(node == null){
            //為空傳回-1
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value){
        Node node = map.get(key);
        if(node == null){
            node = new Node();
            node.key = key;
            node.value = value;
            if(map.size() == capacity){
                removeLast();
            }
            addToHead(node);
            map.put(key,node);
        } else{
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(Node node) {
        if(node == first){
            return;
        } else if(node == last){
            last.prev.next = null;
            last = last.prev;
        } else{
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.prev = first.prev;
        first.prev = node;
        node.next = first;
        first = node;
    }

    private void removeLast() {
        map.remove(last.key);
        if(last.prev != null){
            Node a = last.prev;
            a.next = null;
            last.prev = null;
            last = a;
        }
    }

    private void addToHead(Node node) {
        if(first == null){
            first = node;
            last = node;
        } else {
            first.prev = node;
            node.next = first;
            first = node;
        }
    }

    @Override
    public String toString() {
        return map.keySet().toString();
    }

    public static void main(String[] args) {
        LRU cache = new LRU(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1);
        cache.put(4, 3);
        System.out.println(cache);
    }
}
           

測試:

image.png