2
\$\begingroup\$

Problem

I am creating a generic LRU Cache in Java.

The LRU Cache should have \$\mathcal{O}(1)\$ set/get complexity.

It is not expected to be thread safe.

Feedback

I would especially like your feedback on:

  • Code readability & naming
  • Areas of redundancy

I am personally debating whether the RecencyQueue should live as a private inner class of the LRUCache. However, I somewhat like splitting it into its own file just because of the amount of logic going on in there, although that's perhaps not a great reason.

I would like to use this code to teach others, which is why I have posted here.

All feedback is appreciated!

Code

Interface

import java.util.Optional;

/**
 * A key value store
 * @param <K> The type for any key stored in this cache
 * @param <V> The type for any value stored in this cache
 */
public interface Cache <K, V> {

    /**
     * Set a key-value pair in the cache.
     * @param key   The key for the associated value
     * @param value The value
     */
    void set(final K key, final V value);

    /**
     * Get the value associated with the provided key from the cache
     * @param key The key associated with the value for retrieval
     * @return    An {@link Optional} encapsulating the value associated
     *            with this key.
     */
    Optional<V> get(final K key);
}

CacheItem

/**
 * This class is used to represent an item added to the {@link LRUCache}
 *
 * It is necessary to store the key here, because when an item is evicted
 * from the cache, we will have to remove it from both the RecencyQueue and
 * the Map held by the cache.
 *
 * To remove it from the RecencyQueue we can simply remove the last item in
 * the queue. However, to remove it efficiently from the map, we need to know
 * what key is associated with the evicted node. So by storing the key here, we avoid
 * having to iterate through the map to find the RecencyQueue Node with a value which matches
 * this evicted cache item.
 *
 * @param <K> The type of key stored in this CacheItem
 * @param <V> The type of value stored in this CacheItem
 */
public class CacheItem <K, V> {

    public CacheItem(K key, V value) {
        this.value = value;
        this.key = key;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public String toString() {
        return "Key: %s Value: %s".formatted(key, value);
    }

    private K key;
    private V value;
}

RecencyQueue (Doubly Linked list)

/**
 * The RecencyQueue will always add new items to the head of the queue.
 * Also, retrieving or updating the value of an item will cause that item
 * to be moved to the head of the queue.
 *
 * Therefore, the head of the queue represents the most recently used
 * node, and the tail of the queue represents the least recently used node.
 * @param <T> The type of the object stored in this queue
 */
class RecencyQueue<T> {

    private int currentSize;

    /**
     * Construct an empty RecencyQueue.
     * The first/last values will be null.
     */
    RecencyQueue() {
        this.currentSize = 0;
    }

    /**
     * Appends the value to the start of the queue
     * @param item The item to add to the queue
     */
    public Node<T> add(final T item) {
        final Node<T> node = new Node<>(item, null, null);

        // Setup first/last if the queue is empty
        if (last == null || first == null) {
            first = node;
            last = first;
        }

        setMRU(node);
        currentSize++;
        return node;
    }

    /**
     * Set the most recently used node to the provided node
     * @param node The node to set as the MRU node
     */
    public void setMRU(final Node<T> node) {
        if (node != first) {
            // If this is the last node, ensure we update the last ref before continuing
            if (node == last) {
                last = node.previous;
            }

            node.detach();
            first.previous = node;
            node.next = first;

            first = node;
        }
    }

    /**
     * Update the value for the provided node
     * @param node  The node to update
     * @param value The new value to store in the node
     */
    public void updateNode(final Node<T> node, final T value) {
        node.nodeItem = value;
        setMRU(node);
    }

    /**
     * Remove the least recently used node from the RecencyQueue.
     * @return The evicted node
     */
    public Node<T> evictLRU() {
        final Node<T> oldLast = last;
        /*
        If the queue has a max capacity of 1 then when we evict the LRU
        we are in effect evicting the first & last node. We should null out the first & last
        references in that case so that next item which is added can set itself to first & last
         */
        if (first == last) {
            // Capacity 1 queue
            first = null;
            last = null;
        }
        else {
            last = last.previous;
        }

        currentSize--;
        return oldLast;
    }


    public int getSize() {
        return currentSize;
    }


    private Node<T> first;
    private Node<T> last;

    /**
     * A node in the queue.
     *
     * A node holds:
     * - A value
     * - A reference to the next node
     * - A reference to the previous node
     * @param <T> Type for the value held by this node
     */
    static class Node<T> {

        public Node(final T value, final Node<T> previous, final Node<T> next) {
            this.nodeItem = value;
            this.previous = previous;
            this.next = next;
        }

        public T getNodeItem() {
            return nodeItem;
        }

        /**
         * Detach this node from its neighbouring nodes.
         */
        public void detach() {
            if (previous != null)
                previous.next = next;
            if (next != null)
                next.previous = previous;

            next = null;
            previous = null;
        }

        public String toString() {
            return nodeItem.toString();
        }

        private T nodeItem;
        private Node<T> next;
        private Node<T> previous;
    }
}

LRUCache

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

/**
 * An LRU cache implementation.
 *
 * @param <K> Key type stored in the cache
 * @param <V> Value type stored in the cache
 */
public class LRUCache <K,V> implements Cache <K,V> {

    public LRUCache(final int capacity) {
        if (capacity < 1)
            throw new IllegalArgumentException("Capacity cannot be less than 1");

        this.maxCapacity = capacity;
        map = new HashMap<>(capacity);
        queue = new RecencyQueue<>();
    }

    /**
     * Used to store new data in the cache.
     *
     * If the key already exists in the cache, its value will be updated.
     *
     * If the key does not exist in the cache, its value will be added, in
     * this case, if adding to the cache would cause it to grow beyond its
     * max capacity, the least recently used cache item will be evicted from
     * the cache before adding the new key-value pair.
     * @param key    The key for the corresponding value
     * @param value  The value to add to the cache
     */
    public void set(final K key, final V value) {

        CacheItem<K, V> cacheItem = new CacheItem<>(key, value);

        if (map.containsKey(key)) {
            // Cache hit, we should update the value of the key and
            // move it to the front of the queue
            RecencyQueue.Node<CacheItem<K, V>> node = map.get(key);
            // Updates the value and sets node as MRU
            queue.updateNode(node, cacheItem);
        }
        else {
            if (queue.getSize() == maxCapacity) {
                // Remove the LRU from the queue and the map
                RecencyQueue.Node<CacheItem<K, V>> last = queue.evictLRU();
                map.remove(last.getNodeItem().getKey());

                // Add the new item to the queue and the map
                RecencyQueue.Node<CacheItem<K, V>> newNode = queue.add(cacheItem);
                map.put(key, newNode);
            } else {
                RecencyQueue.Node<CacheItem<K, V>> newNode = newNode = queue.add(cacheItem);
                map.put(key, newNode);
            }
        }

    }

    /**
     * Retrieve the value from the cache which corresponds to the
     * provided key.
     * @param key Key for the value to retrieve
     * @return    An optional encapsulating the value.
     */
    public Optional<V> get(final K key) {
        if (map.containsKey(key)) {
            // Move it to the front of the queue
            RecencyQueue.Node<CacheItem<K, V>> node = map.get(key);
            queue.setMRU(node);
            return Optional.of(node.getNodeItem().getValue());
        }
        else {
            return Optional.empty();
        }
    }

    private final int maxCapacity;
    private final Map<K, RecencyQueue.Node<CacheItem<K, V>>> map;
    private final RecencyQueue<CacheItem<K, V>> queue;
}

LRUCacheTest

import org.junit.jupiter.api.Test;

import java.util.Optional;

import static org.junit.jupiter.api.Assertions.*;

class LRUCacheTest {

    @Test
    void shouldThrowIfCacheCapacityLessOne() {
        IllegalArgumentException expected = assertThrows(
                IllegalArgumentException.class,
                () -> new LRUCache<String, String>(0),
                "Should throw IllegalArgumentException when capacity is less than 1"
        );

        assertEquals("Capacity cannot be less than 1", expected.getMessage());
    }

    @Test
    void shouldReturnEmptyOptionalIfNoEntryInCache() {
        final Cache<Integer, String> cache = new LRUCache<>(1);
        Optional<String> value = cache.get(1);
        assertFalse(value.isPresent());
        assertEquals(Optional.empty(), value, "Optional should be empty when there is no cache entry");
    }

    // Should get item in cache
    @Test
    void shouldRetrieveItemFromCache() {
        final int key = 1;
        final String value = "Value one";

        final int keyTwo = 2;
        final String valueTwo = "Value two";

        final Cache<Integer, String> cache = new LRUCache<>(2);

        cache.set(key, value);
        cache.set(keyTwo, valueTwo);

        assertEquals(value, cache.get(key).get(), "Cache should contain value for key 1");
        assertEquals(valueTwo, cache.get(keyTwo).get(), "Cache should contain value for key 2");
    }

    @Test
    void shouldUpdateExistingValueIfKeyExists() {
        final int key = 1;
        final String value = "Value";
        final String newValue = "New Value";

        final Cache<Integer, String> cache = new LRUCache<>(1);
        cache.set(1, value);
        assertEquals(value, cache.get(key).get(), "Cache should contain value for key 1");

        cache.set(1, newValue);
        assertEquals(newValue, cache.get(key).get(), "Cache should contain updated value for key 1");
    }

    @Test
    void shouldEvictLruFromCache() {
        final int key = 1;
        final String value = "Value one";

        final int keyTwo = 2;
        final String valueTwo = "Value two";

        final Cache<Integer, String> cache = new LRUCache<>(1);

        cache.set(key, value);
        cache.set(keyTwo, valueTwo);

        assertFalse(cache.get(key).isPresent(), "Cache should have evicted value for key 1");
        assertEquals(valueTwo, cache.get(keyTwo).get(), "Cache should contain value for key 2");
    }

    @Test
    void shouldUpdateRecencyWithGet() {
        final int key = 1;
        final String value = "Value one";

        final int keyTwo = 2;
        final String valueTwo = "Value two";

        final int keyThree = 3;
        final String valueThree = "Value three";

        final Cache<Integer, String> cache = new LRUCache<>(2);
        cache.set(key, value);
        cache.set(keyTwo, valueTwo);

        /*
        Getting the value associated with "key" should set it to
        more recently used than keyTwo. So when we add another
        item to the cache, keyTwo should be evicted instead of key
         */
        cache.get(key);
        cache.set(keyThree, valueThree);

        assertEquals(value, cache.get(key).get(), "Cache should contain value for key 1 because cache.get" +
                " call should have set it to most recently used");
        assertFalse(cache.get(keyTwo).isPresent(), "Cache should not contain entry for key two as it should " +
                "be the least recently used");
        assertEquals(valueThree, cache.get(keyThree).get(), "Cache should contain entry for key three as it " +
                "is the second most recently used");
    }

    @Test
    void shouldUpdateRecencyWithUpdate() {
        final int key = 1;
        final String value = "Value one";
        final String altValue = "Value alt";

        final int keyTwo = 2;
        final String valueTwo = "Value two";

        final int keyThree = 3;
        final String valueThree = "Value three";

        final Cache<Integer, String> cache = new LRUCache<>(2);
        cache.set(key, value);
        cache.set(keyTwo, valueTwo);

        /*
        Getting the value associated with "key" should set it to
        more recently used than keyTwo. So when we add another
        item to the cache, keyTwo should be evicted instead of key
         */
        cache.set(key, altValue);
        cache.set(keyThree, valueThree);

        assertEquals(altValue, cache.get(key).get(), "Cache should contain entry for key 1 as updating its" +
                " value should have set it as the most recently used");
        assertFalse(cache.get(keyTwo).isPresent(), "Cache should not contain entry for key two as it should" +
                " be the least recently used");
        assertEquals(valueThree, cache.get(keyThree).get(), "Cache should contain entry for key three as it" +
                " is the second most recently used");
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ newNode = newNode = queue.add seems like a typo. \$\endgroup\$
    – vnp
    Jun 12, 2022 at 20:17

1 Answer 1

1
\$\begingroup\$

Thanks for a very solid first question. Here are my thoughts, randomly assembled:

General

In idiomatic java, class-level variables appear at the top of the class, not the bottom. This formatting decision is decidedly nonstandard and not in common use. It will make the code harder to read, and should be avoided.

In idiomatic java, curly braces go on the same line, so } else {, not else {.

Classes which are not designed to be extended should be marked final.

Methods that override their parents, notably toString(), should be annotated with @Override.

Curly braces should always be used, even when optional. They improve readability and eliminate a category of error common to new developers.

Cache

`final` in this context means that a parameter’s value can not be reassigned in the body of the method. The methods declared on this interface have no body, so `final` is noise here and should be removed.

CacheItem

This class is intended for use inside its package, not outside. It should have package-private (aka default) scope.

I would expect toString to indicate the class name, and perhaps to be formatted with more than a single space between the end of the key and the beginning of “Value”.

RecencyQueue

Presumably this class is used instead of a `LinkedList` as a `Deque` for educational reasons? Otherwise reusing `LinkedList`, either the top level or encapsulated by RecencyQueue, would be preferable.

The constructor does nothing and can be removed. The class is already package-private, so it can’t be externally instantiated, and the value of an int member variable defaults to zero. If, for educational reasons, the zero needs to be called out, it can be assigned where currentSize is declared.

It is entirely unreasonable to ask readers to look for instance variables at both the top and in the middle of a class.

It is confusing for some operations on node relations to be managed in this class, and some (detach()) to be managed in Node.

The number of entries in the cache can be tracked by the size of the map in LRUCache. There’s no need to track it here also.

Nit: in add(), I think first = node; last = node; (on 2 lines) would read more cleanly. Another option would be first = last = node; which I personally don’t like but others do.

Acronyms such as MRU should be avoided as they’re hard to read. The extra characters cost nothing and enhance readability in most cases. If they are used, prefer to only capitalize the first letter of the acronym, so setMru.

setMRU would be cleaner with a guard clause (if (node == first) { return; }). It would be even cleaner if you just let the normal flow of logic handle the case. A trivial performance hit for improved readability is almost always a win.

The comment In evictLRU is misleading. The issue occurs when the current capacity is one, whether or not it’s the max capacity.

RecencyQueue.Node

`final` has limited value in the constructor parameter list.

It reduces readability that what code outside of Node passes in as a “value” gets renamed inside Node as a “nodeItem” Unless there’s a compelling reason to do so, keep the same name throughout.

Consider using sentinel nodes at the head and tail of the list to clean up the detach() method.

toString only containing the value of the node, with no information about its links, would seem to be of limited utility.

Node seems like a concept shared between the queue and the cache. Should it be top-level?

LRUCache

In `set`, returning early would be cleaner than nested if-else clauses.

In set, newNode = newNode = queue.add(cacheItem); is probably an error.

In set, common logic in the if and else blocks of the queue size branches can be extracted.

set can be cleaned up a decent bit if the size check is changed to if (queue.getSize() > maxCapacity) and is moved to the end.

In get, the else clause is not necessary because the if clause returns.

In get, it’s slightly more efficient to call get on the map and check the value for nullness rather than calling containsKey and get. Pick whichever you find more readable.

In get, it might be cleaner to check map.containsKey and return empty from that.

Alternative approach

I think that having Node, CacheItem, and RecencyQueue is a lot more complexity than a simple LRU cache requires. The code could be rewritten to merge Node and CacheItem, and have LRUCache manage `mostRecentlyUsed` and `leastRecentlyUsed`.
public final class LruCache <K,V> implements Cache <K,V> {

    private final int maxCapacity;
    private final Map<K, CacheItem<K, V>> map;
    private CacheItem<K, V> mostRecentlyUsed;
    private CacheItem<K, V> leastRecentlyUsed;

    public LruCache(final int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException("Capacity cannot be less than 1");
        }

        this.maxCapacity = capacity;
        map = new HashMap<>(capacity);
    }

    public void set(final K key, final V value) {
        CacheItem<K, V> cacheItem = map.getOrDefault(key, new CacheItem<K, V>(key, value));
        cacheItem.setValue(value);
        map.put(key, cacheItem);
        /* probably too complex, but you can replace the prior three lines with:
         * CacheItem<K, V> cacheItem = map.compute(key, (k, v) -> (v != null) ? v : new CacheItem<K, V>(k, value));
         */
        setMostRecentlyUsed(cacheItem);

        if (map.size() == 1) {
            leastRecentlyUsed = cacheItem;
        }

        if (map.size() > maxCapacity) {
            evictLeastRecentlyUsed();
        }
    }

    public Optional<V> get(final K key) {
        if (!map.containsKey(key)) {
            return Optional.empty();
        }

        CacheItem<K, V> cacheItem = map.get(key);
        setMostRecentlyUsed(cacheItem);

        return Optional.of(cacheItem.getValue());
    }

    private void setMostRecentlyUsed(CacheItem<K, V> cacheItem) {
        detach(cacheItem);
        cacheItem.setNext(mostRecentlyUsed);

        if (mostRecentlyUsed != null) {
            mostRecentlyUsed.setPrevious(cacheItem);
        }
        mostRecentlyUsed = cacheItem;
    }

    private void evictLeastRecentlyUsed() {
        CacheItem<K, V> evictedCacheItem = leastRecentlyUsed;
        detach(evictedCacheItem);
        map.remove(evictedCacheItem.getKey());
    }

    private void detach(CacheItem<K, V> cacheItem) {        
        CacheItem<K, V> previous = cacheItem.getPrevious();
        CacheItem<K, V> next = cacheItem.getNext();

        if (cacheItem == leastRecentlyUsed) {
            leastRecentlyUsed = previous;
        }
        if (previous != null) {
            previous.setNext(next);
        }
        if (next != null) {
            next.setPrevious(previous);
        }

        cacheItem.setPrevious(null);
        cacheItem.setNext(null);
    }
}

The corresponding CacheItem class would look like:

final class CacheItem <K, V> {

    private K key;
    private V value;
    private CacheItem<K, V> previous;
    private CacheItem<K, V> next;
    
    public CacheItem(K key, V value) {
        this.value = value;
        this.key = key;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
    
    public void setValue(V value) {
        this.value = value;
    }
    
    public CacheItem<K, V> getPrevious() {
        return previous;
    }
    
    public void setPrevious(CacheItem<K, V> previous) {
        this.previous = previous;
    }
    
    public CacheItem<K, V> getNext() {
        return next;
    }
    
    public void setNext(CacheItem<K, V> next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "CacheItem{Key: %s,  Value: %s}".formatted(key, value);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.