回到顶部 暗色模式

Leetcode题解(5):LRU与LinkedHashMap

LeetCode146

        为了记录访问顺序,我们可以使用一个双向链表,首节点为最近最少访问的数据,尾节点为最近访问的数据。为了快速获取值,我们可以额外使用一个 $Map$ 存储键值映射。

public class LRUCache {
    private int capacity;
    private int size;
    private Map<Integer, Node> map;
    private Node head;
    private Node tail;

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

    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.val;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.val = value;
            return;
        }
        if (++size > capacity) removeHead();
        node = new Node(key, value);
        putToTail(node);
        map.put(key, node);
    }

    private Node getNode(int key) {
        Node node = map.get(key);
        if (node == null) return null;
        putToTail(node);
        return node;
    }

    private void removeHead() {
        map.remove(head.key);
        if (head == tail) head = tail = null;
        else {
            head = head.next;
            head.prev = null;
        }
        --size;
    }

    private void putToTail(Node node) {
        if (head == null) {
            head = tail = node;
            return;
        } else if (node == tail)
            return;
        if (head == node) head = head.next;
        Node p = node.prev, n = node.next;
        if (n != null) n.prev = p;
        if (p != null) p.next = n;
        tail.next = node;
        node.prev = tail;
        node.next = null;
        tail = node;
    }

    private class Node {
        int key;
        int val;
        Node prev;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

        讲完了 $LRUCache$ 之后就可以讲讲 $LRUCache$ 与 $LinkedHashMap$ 之间的关系了。默认情况下 $LinkedHashMap$ 是一种保存了值写入顺序的 $HashMap$ ,扩展了 $HashMap$ ,也就是说底层与 $HashMap$ 相同。而写入顺序是通过一个双向链表存储的,在每次写入和删除时更新。
        可以发现 $LinkedHashMap$ 里面有一个特殊的构造函数:

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

        $accessOrder$ 是一个标志位,当它设置为 $true$ 时,允许我们通过访问顺序改变链表。以 $get$ 方法为例:

public V get(Object key) {
    Node<K, V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

        可以发现在每次 $get$ 之后,都会判断 $accessOrder$ ,然后调用 $afterNodeAccess$ 方法。后者的实现如下:

void afterNodeAccess(Node<K, V> e) {
    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;
    }
}

        可以看到逻辑很简单,就是将节点 $p$ 置于链表尾部。而这个节点 $p$ 是我们刚刚通过 $get$ 方法尝试访问的节点 $e$ 转化过来的,也就是说这个方法实际上是将最近访问的节点放到链表尾部。除了 $get$ 方法之外,$put$ 方法和 $replace$ 方法也会调用该方法。
        除了这个方法外,$put$ 方法在添加键值对时,还会调用另一个方法:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    /*
    将值插入表内
    */
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

        $LinkedHashMap$ 本身并没有重写 $put$ 方法,也就是说它调用的是 $HashMap$ 中的版本。而在 $HashMap$ 里,$afterNodeInsertion$ 方法是空实现,也就是不执行任何操作。$LinkedHashMap$ 重写了该方法:

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

        方法实现很简单,只要 $evict = true$ 、链表非空并且 $removeEldestEntry$ 方法为 $true$ ,就移除首节点,也就是最近最少访问的节点。而 $removeEldestEntry$ 方法的实现如下:

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

        可以发现默认返回 $false$ ,也就是不移除节点。所以如果要使用 $LinkedHashMap$ 实现 $LRUCache$ ,就需要重写该方法。而除了 $afterNodeInsertion$ 和 $afterNodeAccess$ 方法之外,还有一个用于移除时的 $afterNodeRemoval$ 方法,实现逻辑大致相同,在此就不赘述。
        使用 $LinkedHashMap$ 实现 $LRUCache$ 的方法如下:

public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

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

    public int get(int key) {
        return getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

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