1.LRU是什么

Least Recently Used的縮寫(xiě)，即最近最少使用

2.如何手寫(xiě)一個(gè)LRU

@使用雙鏈表
@使用map存儲(chǔ)元素
@為了方便操作，給雙鏈表添加偽頭節(jié)點(diǎn)和偽尾節(jié)點(diǎn)

3.實(shí)現(xiàn)說(shuō)明

1.為什么使用雙鏈表
雙鏈表添加、刪除元素只需修改前后指針，時(shí)間復(fù)雜度為O(1)
2.為什么使用map
map存取元素通過(guò)hash計(jì)算位置，時(shí)間復(fù)雜度也為O(1)

4.完成代碼如下

package com.shaw.kratos.common.cache;

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

/**
 * @author shaw
 * @date 2021/6/16
 */
public class LRUCache<K, V> extends AbstractCache<K, V> {

    private int cap;
    private int size = 0;
    private DLinkNode dummyHead;
    private DLinkNode dummyTail;

    private Map<K, DLinkNode<K, V>> map = new HashMap<>();

    public LRUCache(int cap) {
        this.cap = cap;
        this.dummyHead = new DLinkNode<>(-1, -1);
        this.dummyTail = new DLinkNode<>(-1, -1);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    @Override
    public void put(K key, V value) {
        if (size >= cap) {
            // 達(dá)到限制容量，刪除最少使用的元素，最少使用的元素在鏈表末尾
            DLinkNode needRemoveNode = dummyTail.prev;
            removeNode(needRemoveNode);
            map.remove(needRemoveNode.k);
            size--;
        }
        DLinkNode node = map.get(key);
        DLinkNode<K, V> addNode = new DLinkNode<>(key, value);
        if (null == node) {
            map.put(key, addNode);
            addHead(addNode);
            size++;
        } else {
            removeNode(node);
            addHead(addNode);
            map.put(key, addNode);
        }
    }

    @Override
    public V get(K key) {
        DLinkNode<K, V> node = map.get(key);
        if (null == node) {
            return null;
        }
        removeNode(node);
        addHead(node);
        return node.v;
    }

    private void addHead(DLinkNode node) {
        DLinkNode tmp = dummyHead.next;
        dummyHead.next = node;
        node.prev = dummyHead;
        node.next = tmp;
        tmp.prev = node;
    }

    private void removeNode(DLinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private static class DLinkNode<K, V> {
        K k;
        V v;
        DLinkNode prev;
        DLinkNode next;
        DLinkNode(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
}