A Simple LRU cache

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 115
Joined: Wed Oct 10, 2018 3:48 am

A Simple LRU cache

Post by dendiz » Wed Dec 05, 2018 8:12 am

As I was working on TechScan I needed a way to store some of the chart data in memory for multiple scanners use the same data. My first implementation was a Map but that took too much memory storing old data. I didn't want to use Caffeine and add another dependency so I did a small and simple LRU cache. It has quite an efficient run-time with little overhead.

The idea is the to use a map to track the entries and a double linked list to keep track of what is recently used.

1. Keep a map of Key -> Node(K,V)
2. Keep a linked list of Node(K,V)

for insertion add an entry to the map pointing to the node in the list, and append the node to the end of the list.
for get look up the node using the map, move the node to the end of this list and return the node value.

if during insertion the capacity is reached, remote the HEAD of the list as it is the oldest entry before adding a new node.

Code: Select all

public class LRUCache<K,V> {
    public static class Node<K,V> {
        public V value;
        public K key;
        public Node<K,V> next;
        public Node<K,V> prev;
        public Node(K key, V value) {
            this.value = value;
            this.key = key;
        }
    }
    Map<K, Node<K,V>> map = new HashMap<>();
    Node<K,V> head, tail;
    int capacity, hit, miss, evictions, shifts;
    public LRUCache(int max) {
        if (max < 1) {
            throw new IllegalArgumentException("capacity must be > 0");
        }
        capacity = max;
    }
    
    public boolean containsKey(K key) {
        return map.containsKey(key);
    }
    
    public void put(K key, V v) {
        //empty cache
        if (head == null) {
            head = new Node<K,V>(key,v);
            tail = head;
            map.put(key, head);
            return;
        }
        
        //duplicate entry
        if (map.containsKey(key)) {
            Node<K,V> n = map.get(key);
            shift(n);
            return;
        }
        
        //regular entry
        Node<K,V> n = new Node<>(key, v);
        map.put(key, n);
        if (map.size() > capacity) {
            Node<K,V> evicted = evict();
            map.remove(evicted.key);
        }
        
        append(n);
    }

    public V get(K key) {
        Node<K,V> n = map.get(key);
        if (n == null) {
            miss++;
            stats();
            return null;
        }
        hit++;
        stats();
        //don't shift if there is 1 item
        if (map.size() > 1) {
            shift(n);
        }

        return n.value;
    }
    
    private Node<K,V> evict() {
        Node<K,V> evicted = head;
        head = head.next;
        evicted.next = null;
        evicted.prev = null;
        evictions ++;
        return evicted;
    }
    
    private void append(Node<K,V> n) {
        n.next = null;
        n.prev = tail;
        tail.next = n;
        tail = n;        
    }
    
    public void shift(Node<K,V> n) {
        //case 1: n is head
        shifts++;
        if (n == head) {
            head = n.next;
            append(n);
            return;
        }
        //case 2: n is tail
        if (n == tail) {
            return;
        }
        
        //case 3: n is in the middle 
        //detach
        n.prev.next = n.next;
        n.next.prev = n.prev;
        
        //attach at end
        append(n);
    }
    
}

Post Reply