Интервьюер: Можете ли вы написать кэш LRU?

Java
Интервьюер: Можете ли вы написать кэш LRU?

0. Предварительное резюме

Интервьюер:Можете ли вы написать кэш LRU вручную?
ты:Что такое ЛРУ? (растерянное лицо)
Интервьюер:Полное название LRU — «Наименее недавно использованные», которое используется для исключения редко используемых данных и сохранения «горячих» данных.
你写了5分钟，然而只写了个get和put方法体，里面逻辑实在不知道咋写。
Интервьюер:Сначала приходите сюда на сегодняшнее интервью, мы свяжемся с вами, когда будут другие интервью.
我信你个鬼，你个糟老头子坏滴很，还联系啥，凉凉了。
Не волнуйтесь, если кто-то снова спросит вас о LRU, просто киньте ему эту статью и пообещайте сделать предложение на месте.

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;
    }
}

Зачем наследовать LinkedHashMap и переписывать два метода для реализации LRU?
В следующей статье вам предстоит разорвать исходный код LinkedHashMap вручную, и вы обнаружите, что исходный код LinkedHashMap удивительно похож на логику LRU, написанную лампой выше.

)

Категории