乐趣区

关于java:面试官你能手写一个LRU缓存吗

jiezi

0. 前情提要

面试官： 你能手写个 LRU 缓存吗？
你： LRU 是什么货色？（一脸懵逼状）
面试官： LRU 全称 Least Recently Used（最近起码应用），用来淘汰不罕用数据，保留热点数据。
你写了 5 分钟，然而只写了个 get 和 put 办法体，外面逻辑切实不晓得咋写。
面试官： 明天的面试先到这吧，有其余面试咱们会再分割你。
我信你个鬼，你个糟老头子坏滴很，还分割啥，凉凉了。
别放心，再有人问你 LRU，就把这篇文章丢给他，保障当场发 offer。

1. 实现思路

目标是把最不罕用的数据淘汰掉，所以须要记录一下每个元素的拜访次数。最简略的办法就是把所有元素按应用状况排序，最近应用的，移到开端。缓存满了，就从头部删除。

2. 应用哪种数据结构实现？

罕用的数据结构有数组、链表、栈、队列，思考到要从两端操作元素，就不能应用栈和队列。
每次应用一个元素，都要把这个元素移到开端，蕴含一次删除和一次增加操作，应用数组会有大量的拷贝操作，不适宜。
又思考到删除一个元素，要把这个元素的前一个节点指向下一个节点，应用双链接最合适。
链表不适宜查问，因为每次都要遍历所有元素，能够和 HashMap 配合应用。
双链表 + HashMap

3. 代码实现 

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

/**
 * @author yideng
 */
public class LRUCache<K, V> {

    /**
     * 双链表的元素节点
     */
    private class Entry<K, V> {
        Entry<K, V> before;
        Entry<K, V> after;
        private K key;
        private V value;
    }

    /**
     * 缓存容量大小
     */
    private Integer capacity;
    /**
     * 头结点
     */
    private Entry<K, V> head;
    /**
     * 尾节点
     */
    private Entry<K, V> tail;
    /**
     * 用来存储所有元素
     */
    private Map<K, Entry<K, V>> caches = new HashMap<>();

    public LRUCache(int capacity) {this.capacity = capacity;}

    public V get(K key) {final Entry<K, V> node = caches.get(key);
        if (node != null) {
            // 有拜访，就移到链表开端
            afterNodeAccess(node);
            return node.value;
        }
        return null;
    }

    /**
     * 把该元素移到开端
     */
    private void afterNodeAccess(Entry<K, V> e) {
        Entry<K, V> last = tail;
        // 如果 e 不是尾节点，才须要挪动
        if (last != e) {
            // 删除该该节点与前一个节点的分割，判断是不是头结点
            if (e.before == null) {head = e.after;} else {e.before.after = e.after;}

            // 删除该该节点与后一个节点的分割
            if (e.after == null) {last = e.before;} else {e.after.before = e.before;}

            // 把该节点增加尾节点，判断尾节点是否为空
            if (last == null) {head = e;} else {
                e.before = last;
                last.after = e;
            }
            e.after = null;
            tail = e;
        }
    }

    public V put(K key, V value) {Entry<K, V> entry = caches.get(key);
        if (entry == null) {entry = new Entry<>();
            entry.key = key;
            entry.value = value;
            // 新节点增加到开端
            linkNodeLast(entry);
            caches.put(key, entry);
            // 节点数大于容量，就删除头节点
            if (this.caches.size() > this.capacity) {this.caches.remove(head.key);
                afterNodeRemoval(head);
            }
            return null;
        }
        entry.value = value;
        // 节点有更新就挪动到未节点
        afterNodeAccess(entry);
        caches.put(key, entry);
        return entry.value;
    }

    /**
     * 把该节点增加到尾节点
     */
    private void linkNodeLast(Entry<K, V> e) {
        final Entry<K, V> last = this.tail;
        if (head == null) {head = e;} else {
            e.before = last;
            last.after = e;
        }
        tail = e;
    }

    /**
     * 删除该节点
     */
    void afterNodeRemoval(Entry<K, V> e) {if (e.before == null) {head = e.after;} else {e.before.after = e.after;}

        if (e.after == null) {tail = e.before;} else {e.after.before = e.before;}
    }

}

4. 其实还有更简略的实现 

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

/**
 * @author yideng
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    // 最大容量
    private final int maximumSize;

    public LRUCache(final int maximumSize) {
        // true 代表按拜访程序排序，false 代表按插入程序
        super(maximumSize, 0.75f, true);
        this.maximumSize = maximumSize;
    }

    /**
     * 当节点数大于最大容量时，就删除最旧的元素
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry eldest) {return size() > this.maximumSize;
    }
}
退出移动版