Thread-safe LFU Cache

Question

I am trying to implement a thread-safe LFU cache algorithm, please review my code and would really appreciate some criticism or suggestion. (on naming, design, data structures used, anything)

Some assumptions:

1. capacity will be larger than 0.
2. If the cache is full and multiple keys have the same frequency, the least recently used will be evicted.

Here is the code:

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public interface CacheAlgorithm<K, V> {
    public V get(K key);
    public void put(K key, V value);
}

public class LFU<K, V> implements CacheAlgorithm<K, V> {

    private final ReentrantLock lock;
    private final int capacity;
    private final TreeMap<Integer, Set<K>> frequencyToKeys;
    private final Map<K, V> entries;
    private final Map<K, Integer> frequencies;

    public LFU(int capacity) {
        this.capacity = capacity;
        lock = new ReentrantLock();
        frequencyToKeys = new TreeMap<>();
        entries = new HashMap<>();
        frequencies = new HashMap<>();
    }

    @Override
    public V get(K key) {
        try {
            V value = entries.get(key);
            if (value != null) {
                incrementFrequency(key);
            }
            return value;
        } finally {
            lock.unlock();
        }
    }

    @Override
    public void put(K key, V value) {
        try {
            if (entries.containsKey(key)) {
                incrementFrequency(key);
                entries.put(key, value);
            } else {
                if (capacity == entries.size()) {
                    removeLeastFrequentEntry();
                }
                addNewEntry(key, value);
            }
        } finally {
            lock.unlock();
        }
    }

    private void addNewEntry(K key, V value) {
        entries.put(key, value);
        setKeyFrequency(key, 1);
    }

    private void incrementFrequency(K key) {
        int frequency = frequencies.get(key);
        Set<K> keys = frequencyToKeys.get(frequency);
        keys.remove(key);
        if (keys.isEmpty()) {
            frequencyToKeys.remove(frequency);
        }
        setKeyFrequency(key, frequency + 1);
    }

    private void setKeyFrequency(K key, int frequency) {
        frequencies.put(key, frequency);
        frequencyToKeys.putIfAbsent(frequency, new LinkedHashSet<>());
        frequencyToKeys.get(frequency).add(key);
    }

    private void removeLeastFrequentEntry() {
        Map.Entry<Integer, Set<K>> entry = frequencyToKeys.firstEntry();
        Integer frequency = entry.getKey();
        Set<K> keys = entry.getValue();
        K keyToEvict = keys.iterator().next();
        keys.remove(keyToEvict);
        if (keys.isEmpty()) {
            frequencyToKeys.remove(frequency);
        }
        frequencies.remove(keyToEvict);
        entries.remove(keyToEvict);
    }
}

Answer 1

Few comments from my side:

Looks like a code bug: I think you want to use ReentrantLock to manage concurrent operations in multithreaded environment. But in your code I don't see any place where you have made a call to lock (neither lock() nor tryLock(long timeout, TimeUnit unit)). While unlock() is used couple of time, which is of no use in this case.

Other suggested updated:

1. CacheAlgorithm interface should be rather renamed to Cache only. Because it doesn't make sense in any class to make use of word Algorithm.

2. Code should prevent using abbreviations as much as possible. So LFU should be renamed to LeastFrequentlyUsed. Which is not a very big name. Along that it should be ended with Cache to make it more clear to user. So the better name would be LeastFrequentlyUsedCache.

3. It would be better to have a default constructor with default capacity, as Java API has for Collection classes.

4. Avoid auto-boxing and auto-unboxing in code. As these are heavy operations. Rather do custom boxing and unboxing as below:

---

final int frequency = frequencies.get(key).intValue();
final Set<K> keys = frequencyToKeys.get(Integer.valueOf(frequency));