基于Java的LRU算法的實作

1.思想：基于HashMap和雙向循環連結清單實作

 2.代碼實作

/**
 * @program: JavaDemo
 * @author: alian
 * @description: 測試
 * @create: 2022-07-10 17:55
 **/
package alian;

import java.util.HashMap;
import java.util.Set;

class Main {
    public static void main(String[] args) {
        LRU lru = new LRU(3);
//        lru.add(3);
//        lru.add(2);
//        lru.add(1);
//        lru.add(0);
        // 0 1 2

//        lru.add(3);
//        lru.add(2);
//        lru.add(1);
//        lru.get(3);
//        lru.add(0);
//        0 1 3
        Set<Object> keys = lru.map.keySet();
        for (Object key : keys) {
            System.out.print(key + " ");
        }
    }
}

// 循環雙向連結清單
class Node {
    Object key;

    public Node(Object key) {
        this.key = key;
        pre = null;
        next = null;
    }

    Node pre;
    Node next;
}

class LRU {
    HashMap<Object, Object> map;
    Node head;
    int size;
    int cval;

    public LRU(int size) {
        map = new HashMap<>();
        head = null;
        this.size = size;
        cval = 0;
    }

    // 新插入的對象放在循環雙向連結清單的首部
    public void add(Object obj) {
        Node node = new Node(obj);
        map.put(obj, node);
        if (head == null) {
            head = node;
            node.next = node;
            node.pre = node;
            cval++;
        } else {
            Node tail = head.pre;
            node.next = head;
            head.pre = node;
            node.pre = tail;
            tail.next = node;
            head = node;
            cval++;
            delete();
        }
    }

    public void delete() {
        if (cval > size) {
            Node tep = head.pre.pre;
            //删除最後的一個節點
            map.remove(head.pre.key);
            head.pre = tep;
            tep.next = head;
            cval--;
        }
    }

    public Object get(Object obj) {
        if (!map.containsKey(obj)) {
            return null;
        }
        //更新雙向連結清單的順序
        Node node = (Node) map.get(obj);
        Node pre1 = node.pre;
        Node pre2 = node.next;
        pre1.next = pre2;
        pre2.pre = pre1;
        //将通路值放在雙向隊列的首尾
        Node tail = head.pre;
        node.next = head;
        head.pre = node;
        node.pre = tail;
        tail.next = node;
        head = node;
        cval++;
        return obj;
    }
}