Cache Eviction, Invalidation and Stampedes

import java.util.*;

class LRUCache<K, V> {
    private final int capacity;
    // accessOrder = true: iteration order is least to most recently used
    private final LinkedHashMap<K, V> map;

    LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    synchronized V get(K key) {
        return map.get(key); // also marks it most recently used
    }

    synchronized void put(K key, V value) {
        map.put(key, value);
    }

    synchronized Set<K> keys() {
        return new LinkedHashSet<>(map.keySet());
    }
}

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()  # least to most recently used

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # evict the least recently used

    def keys(self):
        return list(self.data)

import java.util.*;

class LFUCache<K, V> {
    private final int capacity;
    private final Map<K, V> values = new HashMap<>();
    private final Map<K, Integer> counts = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> byCount = new HashMap<>();
    private int minCount = 0;

    LFUCache(int capacity) {
        this.capacity = capacity;
    }

    private void touch(K key) {
        int c = counts.get(key);
        counts.put(key, c + 1);
        byCount.get(c).remove(key);
        if (c == minCount && byCount.get(c).isEmpty()) {
            minCount++;
        }
        byCount.computeIfAbsent(c + 1, x -> new LinkedHashSet<>()).add(key);
    }

    synchronized V get(K key) {
        if (!values.containsKey(key)) {
            return null;
        }
        touch(key);
        return values.get(key);
    }

    synchronized void put(K key, V value) {
        if (capacity == 0) {
            return;
        }
        if (values.containsKey(key)) {
            values.put(key, value);
            touch(key);
            return;
        }
        if (values.size() == capacity) {
            K victim = byCount.get(minCount).iterator().next();
            byCount.get(minCount).remove(victim);
            values.remove(victim);
            counts.remove(victim);
        }
        values.put(key, value);
        counts.put(key, 1);
        byCount.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key);
        minCount = 1;
    }
}

from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}
        self.counts = {}
        self.by_count = defaultdict(OrderedDict)  # count -> keys, least recent first
        self.min_count = 0

    def _touch(self, key):
        c = self.counts[key]
        self.counts[key] = c + 1
        del self.by_count[c][key]
        if c == self.min_count and not self.by_count[c]:
            self.min_count += 1
        self.by_count[c + 1][key] = None

    def get(self, key):
        if key not in self.values:
            return None
        self._touch(key)
        return self.values[key]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.values:
            self.values[key] = value
            self._touch(key)
            return
        if len(self.values) == self.capacity:
            victim, _ = self.by_count[self.min_count].popitem(last=False)
            del self.values[victim]
            del self.counts[victim]
        self.values[key] = value
        self.counts[key] = 1
        self.by_count[1][key] = None
        self.min_count = 1