146. LRU cache

LRUWhat is?

Least recently used algorithm. A queue, put the most recently used element at the head of the queue, when the queue length is insufficient, remove the last element of the queue, which is the least recently used element.

Solution 1: InheritanceLinkedHashMap

The opportunistic solution (best implemented yourself) takes advantage of Java’s LinkedHashMap already implemented, so simply inherits LinkedHashMap as the parent class.

You can read the LinkedHashMap source code for yourself. Focus on these three methods:

  • afterNodeAccess(): After accessing the element, place it at the end of the bidirectional list
  • afterNodeRemoval(): Deletes an element from the bidirectional list
  • afterNodeInsertion(): Indicates whether to remove the least recently used element after an element is inserted
/** ** /
class LRUCache extends LinkedHashMap {

    /** * Capacity */
    private int capacity;

    /** * Call the constructor of the parent class * capacity: capacity * 0.75f: load factor * true: enable LRU caching algorithm */
    public LRUCache(int capacity) {
        super(capacity, 0.75 F.true);
        this.capacity = capacity;
    }
    
    /** * get the element, call the parent class constructor * principle: * (1) first remove the element from the queue * (2) then add the element to the queue header */
    public int get(int key) {
        return (int) super.getOrDefault(key, -1);
    }
    
    /** * get the element, call the parent constructor * principle: * (1) First check whether the element represented by key is already in the queue * (2) If it is in the queue, then overwrite the value of the element * (3) After overwrite, remove the element from the queue, and then add it to the queue header * (4) At this point, the operation is complete * (5) if it is not in the queue, (7) If the capacity is not enough, remove the last element in the queue * (8) and add the element to the queue head. At this point, the operation is complete */
    public void put(int key, int value) {
        super.put(key, value);
    }

    /** * Remove element condition method, because it is empty in LinkedHashMap * so we need to rewrite the method and define our own logic * here is to remove element when capacity is insufficient */
    @Override
    public boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() > capacity; }}Copy the code

Solution 2: Hash + bidirectional linked list

Very important, this is what the interviewer wants you to write down. Be able to write it by hand!

class LRUCache {

    /** * Two-way linked list length */
    private int size;

    /** * Maximum capacity */
    private int capacity;

    /** * hash table, store data */
    private Map<Integer, DoubleLinkedNode> cache;

    /** * two-way list header node, does not store any value, identify the function */
    private DoubleLinkedNode head;

    /** * two-way list end node, does not store any value, identify the function */
    private DoubleLinkedNode tail;

    /** * constructor */
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new DoubleLinkedNode();
        this.tail = new DoubleLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    /** * get the element */
    public int get(int key) {
        DoubleLinkedNode node = this.cache.get(key);

        // If the node to obtain does not exist
        if (node == null) {
            return -1;
        }
        // Move to the head of the two-way list
        moveToHead(node);
        / / the return value
        return node.value;
    }
    
    /** * add element */
    public void put(int key, int value) {
        DoubleLinkedNode node = cache.get(key);
        // If the element does not exist
        if (node == null) {
            node = new DoubleLinkedNode(key, value);
            // add to the hash table
            cache.put(key, node);
            // The length of the bidirectional list increases by 1
            size++;
            // Add to the head of the bidirectional list
            addToHead(node);
            // If the length is greater than the capacity, the element is about to be deleted
            if (size > capacity) {
                // Remove the last element from the bidirectional list
                DoubleLinkedNode tail = removeTail();
                // Delete the corresponding element from the hash table
                cache.remove(tail.key);
                // The length is reduced by 1
                size--;
            }
        // If the element exists
        } else {
            / / modify the value
            node.value = value;
            // Move to the head of the two-way listmoveToHead(node); }}/** * construct a bidirectional list node */
    class DoubleLinkedNode {

        / * * * * /
        int key;

        / * * * * /
        int value;

        /** ** Precursor node */
        DoubleLinkedNode prev;

        /** * the successor node */
        DoubleLinkedNode next;

        /** * constructor */
        public DoubleLinkedNode(a) {}
        public DoubleLinkedNode(int key, int value) {
            this.key = key;
            this.value = value; }}/** * Add a node to the head of the bidirectional list */
    private void addToHead(DoubleLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        node.next.prev = node;
        head.next = node;
    }

    /** * Removes a node from the bidirectional list */
    private void removeNode(DoubleLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = null;
        node.next = null;
    }

    /** * Moves a node in the bidirectional list to the head */
    private void moveToHead(DoubleLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /** * Removes the last node in the bidirectional list */
    private DoubleLinkedNode removeTail(a) {
        DoubleLinkedNode node = this.tail.prev;
        removeNode(node);
        returnnode; }}Copy the code