Java实现LRU策略缓冲

1.基于双向链表+HashMap实现：

• 访问某个节点时，将该节点从双向链表中原位置删除，并重新插入链表头。这样可以保证链表尾部节点就是最近最久未被使用的，当节点数量大于缓存空间就淘汰链表尾部节点；

• 为了能在O(1)时间内从链表删除某个节点，不能通过遍历链表查找该节点。需要借助HashMap存储key与节点的映射，通过key在O(1)时间内找到节点，并在O(1)时间内删除该节点。

public class LRU<K, V> implements Iterable<K> {
    private Node head;
    private Node tail;
    private HashMap<K, Node> map;
    private int maxSize;

    private class Node {
        Node pre;
        Node next;
        K k;
        V v;
        public Node(K k, V v) {
            this.k = k;
            this.v = v;
        } 
    }
    
    public LRU(int maxSize) {
        this.maxSize = maxSize;
        this.map = new HashMap<>(maxSize * 4 / 3);
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.pre = head;
    }
    
    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node node = map.get(key);
        unlink(node);
        appendHead(node);
        return node.v;
    }
    
    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            unlink(node);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        appendHead(node);
        if (map.size() > maxSize) {
            Node toRemove = removeTail();
            map.remove(toRemove.k);
        }
    }
    
    private void unlink(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        node.pre = null;
        node.next = null;
    }
    
    private void appendHead(Node node) {
        Node next = head.next;
        node.next = next;
        next.pre = node;
        node.pre = head;
        head.next = node;
    }
    
    private Node removeTail() {
        Node node = tail.pre;
        Node pre = node.pre;
        tail.pre = pre;
        pre.next = tail;
        node.pre = null;
        node.next = null;
        return node;
    }
    
    @Override
    public Iterator<K> iterator() {
        return new Iterator<K>() {
            private Node cur = head.next;
            @Override
            public boolean hasNext() {
                return cur != tail;
            }
            @Override
            public K next() {
                Node node = cur;
                cur = cur.next;
                return node.k;
            }
        };
    }
}

2.使用Java容器中的LinkedHashMap

• LinkedHashMap继承自HashMap，因此具有和HashMap一样的快速查找特性；
• 内部维护了一个双向链表，用来维护插入顺序或者LRU顺序；accessOrder字段决定了顺序，默认为false（插入顺序）；
• 因此，LinkedHashMap = 双向链表+HashMap.
• 但是LinkedHashMap实现的LRU缓存与第1个实现方式有一点 区别，即LinkedHashMap的链表首部才是最近最久未使用节点 ；当然，这个区别对于双向链表来说不是事儿，只是寓意上的区别而已（在我看来）。

访问一个节点时，调用get()方法，get()中有一个函数afterNodeAccess()；该方法用于将该节点移到链表尾部（最近访问节点）

​

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

在put等操作之后执行afterNodeInsertion()，当removeEldestEntry()方法返回true时会移除最晚的节点，也就是链表首
部节点；evict只有在构建Map时才为false，在这里为true.

​

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry()默认为false，也就是说put操作后执行的afterNodeInsertion()并没有移除首部节点，也就没有L
RU缓存淘汰的说法了；如果需要让它为true，需要继承LinkedHashMap并且覆盖该方法；

​

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

• 因此，要用LinkedHashMap来实现一个LRU缓存，需要：
  1.设定最大缓存空间MAX_ENTRIES
  2.使用LinkedHashMap的构造方法将accessOrder设置为true，开启LRU顺序；
  3.覆盖removeEldestEntry（）方法实现，在节点多于MAX_ENTRIES就会将最近最久未使用的节点删除。

class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_ENTRIES = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}
public class LRUTest{
    - public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>();
        cache.put(1, "a");
        cache.put(2, "b");
        cache.put(3, "c");
        cache.get(1);
        cache.put(4, "d");
        System.out.println(cache.keySet());
    }
}

​