How would you implement an LFU cache using a hash table and a doubly linked list ?

Implementing an LFU (Least Frequently Used) cache is a common challenge in system design interviews and a practical requirement for optimizing data access in applications. This strategy prioritizes items that have been accessed most frequently, ensuring they remain in the cache longer, regardless of their recent usage.

Direct Summary: LFU Cache Implementation

To implement an LFU cache, you primarily combine a hash table with a collection of doubly linked lists. The hash table facilitates quick O(1) key-to-node lookups, while the doubly linked lists manage items based on their access frequency. Specifically, a common and efficient approach involves using a map where keys are frequencies, and values are doubly linked lists containing all cache items with that specific frequency. When an item’s frequency changes, it is moved from its current frequency list to the next appropriate frequency list. Eviction targets the least recently used item within the lowest frequency list.

Understanding the Core Components

An efficient LFU cache relies on the synergistic operation of two fundamental data structures:

1. Hash Table (Map)

• Purpose: The hash table (often implemented as a Map in JavaScript or HashMap in Java) is essential for rapid key-to-value lookups. It stores the cache’s key-value pairs, where the “value” is typically a pointer or reference to the actual cache node located within a doubly linked list.
• Performance: It provides near O(1) average time complexity for get, put, and delete operations. This constant-time access is critical for cache performance, as slow lookups would negate the benefits of caching.

2. Doubly Linked Lists (Frequency Buckets)

• Purpose: Instead of a single linked list, a robust LFU implementation often uses a collection of doubly linked lists, managed by another map (e.g., freqMap). Each key in freqMap is a frequency count, and its value is a FreqList (a doubly linked list) containing all cache nodes that currently have that frequency.
• Node Structure: Each node in these lists typically stores:
  • key: The unique identifier of the cached item.
  • value: The actual data being cached.
  • freq: The current access frequency of this item.
  • prev: Pointer to the previous node in its current frequency list.
  • next: Pointer to the next node in its current frequency list.
• Efficiency: Doubly linked lists are ideal because they allow for O(1) insertion and deletion of nodes, provided you have a reference to the node itself. This efficiency is crucial for moving nodes between frequency lists when their access counts change.

LFU Cache Operations

Frequency Tracking and Node Updates

When an item is accessed (via get) or added/updated (via put):

1. The item’s current frequency is incremented.
2. The item’s node is removed from its current frequency’s doubly linked list.
3. The node is then added to the doubly linked list corresponding to its new, incremented frequency. If this new frequency list doesn’t exist, it’s created.
4. A crucial part of this process is managing a minFreq variable, which tracks the lowest frequency for which there is at least one item in the cache. If the list from which a node was moved becomes empty, and its frequency was equal to minFreq, then minFreq is incremented.

This approach ensures that all operations (get, put) remain efficient, typically O(1) on average.

Eviction Strategy

When the cache reaches its capacity and a new item needs to be added:

1. The cache identifies the least frequent item(s). This is done by looking at the minFreq variable.
2. It then accesses the doubly linked list associated with minFreq.
3. The item to be evicted is the least recently used item within that lowest frequency list. Since nodes are typically added to the tail of their frequency list (making the head the LRU for that frequency), this is simply the head node of the minFreq list.
4. This head node is removed from its frequency list and also from the main hash table. This is an O(1) operation.

Tie-breaking: LFU-LRU

A pure LFU cache might evict an item that was accessed long ago but still has a higher frequency than a recently used item. To refine this, LFU often incorporates an LRU tie-breaker:

• If multiple items share the same lowest frequency, the one that was least recently used among them is evicted.
• This is naturally handled by the “map of frequency lists” structure: within each FreqList, new nodes are typically added to the tail (most recently used for that frequency), meaning the head of that list is the least recently used item at that frequency.

Code Sample (JavaScript)

The following JavaScript code demonstrates a common implementation of an LFU cache using a Map for key-to-node mapping and another Map for frequency-to-doubly-linked-list mapping.

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.freq = 1;
        this.prev = null;
        this.next = null;
    }
}

class FreqList {
    constructor() {
        this.head = new Node(null, null); // Dummy head
        this.tail = new Node(null, null); // Dummy tail
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    // Add a node to the end of the list (before tail)
    add(node) {
        node.next = this.tail;
        node.prev = this.tail.prev;
        this.tail.prev.next = node;
        this.tail.prev = node;
        this.size++;
    }

    // Remove a node
    remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.size--;
    }

    // Get the first node (least frequent/LRU tiebreaker)
    getHead() {
        if (this.size === 0) return null;
        return this.head.next;
    }
}

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.minFreq = 0;
        this.cache = new Map(); // Map key to node
        this.freqMap = new Map(); // Map frequency to FreqList
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }

        const node = this.cache.get(key);
        const val = node.value;
        this.updateFreq(node);
        return val;
    }

    put(key, value) {
        if (this.capacity === 0) {
            return;
        }

        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.value = value; // Update value
            this.updateFreq(node);
        } else {
            // Check capacity
            if (this.size >= this.capacity) {
                // Evict LFU item
                const listToEvict = this.freqMap.get(this.minFreq);
                const nodeToEvict = listToEvict.getHead();
                listToEvict.remove(nodeToEvict);
                this.cache.delete(nodeToEvict.key);
                this.size--;
            }

            // Add new node
            const newNode = new Node(key, value);
            this.cache.set(key, newNode);
            // Add to freq 1 list
            if (!this.freqMap.has(1)) {
                this.freqMap.set(1, new FreqList());
            }
            this.freqMap.get(1).add(newNode);
            this.minFreq = 1; // New node starts at freq 1
            this.size++;
        }
    }

    updateFreq(node) {
        const currentFreq = node.freq;
        const nextFreq = currentFreq + 1;

        // Remove node from current frequency list
        const currentList = this.freqMap.get(currentFreq);
        currentList.remove(node);

        // If current frequency list is empty and it was the minFreq, increment minFreq
        if (currentFreq === this.minFreq && currentList.size === 0) {
            this.minFreq++;
        }

        // Add node to next frequency list
        if (!this.freqMap.has(nextFreq)) {
            this.freqMap.set(nextFreq, new FreqList());
        }
        const nextList = this.freqMap.get(nextFreq);
        nextList.add(node);

        // Update node's frequency
        node.freq = nextFreq;
    }
}

// Example Usage:
const cache = new LFUCache(2);
cache.put(1, 1); // cache: {1: freq 1}
cache.put(2, 2); // cache: {1: freq 1, 2: freq 1}
console.log(cache.get(1)); // returns 1, cache: {1: freq 2, 2: freq 1}, minFreq = 1
cache.put(3, 3); // Evicts key 2 (LFU), cache: {1: freq 2, 3: freq 1}, minFreq = 1
console.log(cache.get(2)); // returns -1
console.log(cache.get(3)); // returns 3, cache: {1: freq 2, 3: freq 2}, minFreq = 2
cache.put(4, 4); // Evicts key 1 (LFU), cache: {3: freq 2, 4: freq 1}, minFreq = 1
console.log(cache.get(1)); // returns -1
console.log(cache.get(3)); // returns 3, cache: {3: freq 3, 4: freq 1}, minFreq = 1
console.log(cache.get(4)); // returns 4, cache: {3: freq 3, 4: freq 2}, minFreq = 2
    

Performance Considerations and Trade-offs

LFU vs. LRU Cache

An LRU (Least Recently Used) cache evicts the item that hasn’t been accessed for the longest time, while an LFU cache evicts the item that has been used the fewest times. LRU is generally simpler to implement, often requiring just a hash table and a single doubly linked list. However, LFU shines in scenarios where usage patterns are predictable and certain data is consistently accessed, even if there are occasional gaps in its use. LFU protects these frequently used items from eviction, leading to higher cache hit ratios in suitable environments.

Implementation Complexity vs. Performance

LFU is inherently more complex to implement than LRU due to the need to track frequencies and manage multiple lists or a more sophisticated structure. This added complexity, however, can be justified by the performance gains in specific use cases, such as caching database query results or static assets with consistent access patterns. The trade-off is between simpler code and potentially better cache efficiency for certain workloads.

Alternative Data Structures: Min-Heap

While a hash table combined with frequency-based doubly linked lists is a common LFU implementation, a min-heap could also be considered. A min-heap stores cache entries ordered by frequency (or a composite key like frequency and timestamp for tie-breaking).

• Benefits: Evicting the LFU item (the root) is an O(log N) operation.
• Drawbacks: Updating an item’s frequency and re-positioning it in the heap (which might involve a “decrease key” or “increase key” operation) can also take O(log N) time. This contrasts with the O(1) operations (remove from one list, add to another) of the multiple doubly linked list approach.

The choice between these structures depends on the expected access patterns and the relative frequency of get/put operations versus eviction needs. For frequent updates, the doubly linked list approach is often more efficient.

Handling Concurrent Access

For a production-ready LFU cache in a multi-threaded or concurrent environment, thread safety is paramount. Without proper synchronization, concurrent operations could lead to data corruption or inconsistent cache states.

• Locking Mechanisms: A common approach is to use a reader-writer lock. This allows multiple threads to read from the cache concurrently but ensures that only one thread can write (modify) the cache at any given time. This balances read performance with data consistency.
• Concurrent Data Structures: Alternatively, using built-in concurrent data structures provided by the programming language or framework (e.g., ConcurrentHashMap in Java, ConcurrentDictionary and ConcurrentQueue in C#) can simplify the implementation and leverage optimized, thread-safe primitives. The choice depends on the specific concurrency requirements and the level of control needed over locking granularity.

Conclusion

Implementing an LFU cache using a hash table and a map of doubly linked lists provides an efficient and robust solution for frequency-aware cache eviction. This design offers average O(1) time complexity for crucial cache operations like get, put, and eviction, making it a powerful tool for optimizing system performance where data access patterns are predictable and frequency of use is a key factor.