LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最少使用的页面予以淘汰。

基于LinkedHashMap实现LRU

package com.github.xuchengen.cache;

import java.util.LinkedHashMap;
import java.util.Map;

public class SimpleLRUCache<K, V> extends LinkedHashMap<K, V> {

    private int capacity;

    public SimpleLRUCache(int capacity) {
        super(16, 0.75F, true);
        this.capacity = capacity;
    }


    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > capacity;
    }

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

手撕LRU算法

package com.github.xuchengen.cache;

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

public class LRUCache<K, V> {

    private Entry<K, V> head;
    private Entry<K, V> tail;
    private Map<K, Entry<K, V>> cache;
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = new HashMap<>();
        this.head = new Entry<>();
        this.tail = new Entry<>();

        head.next = tail;
        tail.pre = head;
    }

    public V get(K key) {
        Entry<K, V> entry = cache.get(key);
        if (Objects.isNull(entry)) {
            return null;
        }

        moveToHead(entry);
        return entry.value;
    }

    public void put(K key, V value) {
        Entry<K, V> entry = cache.get(key);
        if (Objects.nonNull(entry)) {
            entry.value = value;
            cache.put(key, entry);
            moveToHead(entry);
            return;
        }

        if (capacity <= size) {
            Entry<K, V> lastEntry = tail.pre;
            cache.remove(lastEntry.key);
            remove(lastEntry);
            size--;
        }

        Entry<K, V> newEntry = new Entry<>(key, value);
        cache.put(key, newEntry);
        add(newEntry);
        size++;
    }

    private void moveToHead(Entry<K, V> entry) {
        remove(entry);
        add(entry);
    }

    private void add(Entry<K, V> entry) {
        head.next.pre = entry;
        entry.next = head.next;

        head.next = entry;
        entry.pre = head;
    }

    private void remove(Entry<K, V> entry) {
        entry.pre.next = entry.next;
        entry.next.pre = entry.pre;
    }

    private static class Entry<K, V> {
        private Entry<K, V> pre;
        private Entry<K, V> next;
        private K key;
        private V value;

        public Entry() {
        }

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

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