Previously on Twitter

Interviewer: Can you write an LRU cache by hand? You: What is LRU? Interviewer: LRU stands for Least Recently Used. It is Used to eliminate less commonly Used data and retain hot data. You’ve been writing for 5 minutes, but all you’ve got is a body of get and put methods. Interviewer: That’s all for today’s interview. We will contact you when there are other interviews. I believe you. You’re a bad old man. You’re a bad old man. Don’t worry, if anyone asks you about LRU, throw this article at him and make sure you send him an offer on the spot.

1. Implementation ideas

The goal is to weed out the least used data, so you need to keep track of how many times each element is accessed. The easiest way to do this is to sort all the elements by their usage, most recently used, to the end. When the cache is full, it is removed from the header.

2. Which data structure is used?

Common data structures include arrays, linked lists, stacks, and queues. Considering that you want to manipulate elements from both ends, you cannot use stacks and queues. Every time you use an element, you have to move it to the end. There is a delete and an add operation. Using an array would involve a lot of copying and is not suitable. When you remove an element, you want to point the previous node of that element to the next node, and double links are the most appropriate. Linked lists are not suitable for queries because you have to iterate over all the elements at a time and can be used in conjunction with hashMaps. Double linked list + HashMap

3. Code implementation

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

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

    /** * Double linked list element nodes */
    private class Entry<K.V> {
        Entry<K, V> before;
        Entry<K, V> after;
        private K key;
        private V value;
    }

    /** * Cache size */
    private Integer capacity;
    /** * Header node */
    private Entry<K, V> head;
    /** * Last node */
    private Entry<K, V> tail;
    /** * to store all elements */
    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) {
            // Move to the end of the list if there is access
            afterNodeAccess(node);
            return node.value;
        }
        return null;
    }

    /** * move the element to the end */
    private void afterNodeAccess(Entry<K, V> e) {
        Entry<K, V> last = tail;
        // If e is not the tail node, move it
        if(last ! = e) {// Delete the connection between this node and the previous node, and determine whether it is a head node
            if (e.before == null) {
                head = e.after;
            } else {
                e.before.after = e.after;
            }

            // Delete the connection between this node and the next node
            if (e.after == null) {
                last = e.before;
            } else {
                e.after.before = e.before;
            }

            // Add this node to the tail node and check whether the tail node is null
            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;
            // Add the new node to the end
            linkNodeLast(entry);
            caches.put(key, entry);
            // If the number of nodes is greater than capacity, delete the head node
            if (this.caches.size() > this.capacity) {
                this.caches.remove(head.key);
                afterNodeRemoval(head);
            }
            return null;
        }
        entry.value = value;
        // If the node is updated, move to the node not updated
        afterNodeAccess(entry);
        caches.put(key, entry);
        return entry.value;
    }

    /** * add this node to the tail node */
    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; }}}Copy the code

4. There are simpler implementations

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

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

    // Maximum capacity
    private final int maximumSize;

    public LRUCache(final int maximumSize) {
        // True means sort by access order, false means sort by insertion order
        super(maximumSize, 0.75 f.true);
        this.maximumSize = maximumSize;
    }

    /** * Delete the oldest element */ when the number of nodes is greater than the maximum capacity
    @Override
    protected boolean removeEldestEntry(final Map.Entry eldest) {
        return size() > this.maximumSize; }}Copy the code

Why inherit LinkedHashMap, override two methods, and implement LRU?

Next article with your hand to tear the source code of LinkedHashMap, when you will find that the source code of LinkedHashMap and above a light write LRU logic unexpectedly have surprising similarities.