TheAlgorithms/Java · error · RuntimeException

cache cannot be empty!

Error message

cache cannot be empty!

What it means

Internal assertion inside the private evict() method of LRUCache. It fires when eviction is attempted but the doubly-linked list head is null, meaning the cache's linked list is empty while eviction logic expected at least one entry. LRUCache is explicitly documented as thread-unsafe; in correct single-threaded use the caller guards (setCapacity loops on data.size(), put() checks data.size() == cap) prevent evict() being called on an empty list. Hitting this almost always means concurrent access corrupted the internal state or there is a library bug.

Source

Thrown at src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java:79

     * @param newCapacity the new capacity of the cache
     */
    private void setCapacity(int newCapacity) {
        checkCapacity(newCapacity);
        for (int i = data.size(); i > newCapacity; i--) {
            Entry<K, V> evicted = evict();
            data.remove(evicted.getKey());
        }
        this.cap = newCapacity;
    }

    /**
     * Evicts the least recently used item from the cache.
     *
     * @return the evicted entry
     */
    private Entry<K, V> evict() {
        if (head == null) {
            throw new RuntimeException("cache cannot be empty!");
        }
        Entry<K, V> evicted = head;
        head = evicted.getNextEntry();
        head.setPreEntry(null);
        evicted.setNextEntry(null);
        return evicted;
    }

    /**
     * Checks if the capacity is valid.
     *
     * @param capacity the capacity to check
     */
    private void checkCapacity(int capacity) {
        if (capacity <= 0) {
            throw new RuntimeException("capacity must greater than 0!");
        }
    }

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Wrap all put/get access in a synchronized block or ReentrantLock to prevent concurrent state corruption
2. Replace LRUCache with a thread-safe alternative such as Caffeine, Guava Cache, or ConcurrentHashMap with access-order
3. If strictly single-threaded and still hitting it, file a bug against the library with a reproducer

Example fix

// before — shared unsynchronized cache, triggers race
LRUCache<String,String> cache = new LRUCache<>(100);
// many threads call cache.put(...) / cache.get(...)

// after — external synchronization
LRUCache<String,String> cache = new LRUCache<>(100);
private final Object lock = new Object();
public String safeGet(String k) {
    synchronized (lock) { return cache.get(k); }
}
public void safePut(String k, String v) {
    synchronized (lock) { cache.put(k, v); }
}

// LRUCache is thread-unsafe; prevent concurrent access by design.
// Ensure only one thread ever touches the cache instance:
private final Object cacheLock = new Object();
void safePut(LRUCache<K,V> cache, K k, V v) {
    synchronized (cacheLock) { cache.put(k, v); }
}
V safeGet(LRUCache<K,V> cache, K k) {
    synchronized (cacheLock) { return cache.get(k); }
}

// Not recommended as primary defense — fix concurrency instead.
// If you must catch:
try {
    cache.put(key, val);
} catch (RuntimeException e) {
    if (e.getMessage().equals("cache cannot be empty!")) {
        // internal state corrupted by race; rebuild cache
        cache = new LRUCache<>(capacity);
    } else throw e;
}

When it happens

Trigger: Multiple threads calling put() and/or get() on the same LRUCache instance concurrently. The HashMap field 'data' and the linked-list pointers 'head'/'tail' are independent and unsynchronized, so a race can leave data.size() > 0 while head == null; the next put() that triggers eviction then hits the null head. Also reachable if a future code change to setCapacity or put breaks the size/list invariant.

Common situations: Wrapping LRUCache behind a web request handler, async pipeline, or message consumer without external synchronization. Treating it as a drop-in replacement for Guava/Caffeine caches that are thread-safe by default.

Related errors

• Cache cannot be empty!
• capacity must greater than 0!
• Capacity must be greater than zero.
• Cannot enqueue null item.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/36ea0d9eea747d84. Report an issue: GitHub.