Mastering LRU Cache: O(1) Design with HashMap and Doubly Linked List

LRU Principle

Standard OS textbooks illustrate LRU by assuming a memory that can hold three pages and accessing pages in the order 7 0 1 2 0 3 0 4, using a stack representation where the top is the most recently used and the bottom the least recently used.

A naive design that keeps pages physically sorted by access time would require massive memory copies, making performance unacceptable.

To achieve O(1) insertion and removal, the access order must be maintained without real sorting; a common solution is to use a doubly linked list.

Implementing LRU

1. Using an array with timestamps: each insertion increments timestamps of existing items, sets the new item's timestamp to 0, and evicts the item with the largest timestamp. This approach has O(n) time for insert, delete, and access.

2. Using a simple linked list: insert new items at the head, move accessed items to the head, and evict from the tail when full. Locating items still costs O(n).

3. Combining a linked list with a hashmap: the hashmap stores keys for O(1) lookup, while the doubly linked list maintains LRU order. This method provides O(1) time for both save and get operations and is the preferred implementation.

HashMap + Doubly Linked List Implementation

The design stores keys in a HashMap for constant‑time access, and each hashmap value points to a node in a doubly linked list that represents the LRU order.

The list has a head (most recent) and a tail (least recent). When the cache reaches its capacity, the tail node is removed in O(1) time. New or accessed nodes are moved to the head.

An example sequence with capacity 3 shows how the list evolves after a series of save and get operations.

Core operations:

save(key, value) : look up the key in the hashmap; if it exists, update the value and move the node to the head; if not, create a new node, insert it at the head, and evict the tail if the cache is full.

get(key) : locate the node via the hashmap, move it to the head, and return its value; if the key is absent, return –1.

Complete Java reference implementation:

class DLinkedNode {
    String key;
    int value;
    DLinkedNode pre;
    DLinkedNode post;
}

public class LRUCache {
    private Hashtable<Integer, DLinkedNode> cache = new Hashtable<>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.post = tail;
        tail.pre = head;
    }

    public int get(String key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1; // should raise exception here.
        }
        moveToHead(node);
        return node.value;
    }

    public void set(String key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            cache.put(key, newNode);
            addNode(newNode);
            ++count;
            if (count > capacity) {
                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                --count;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.post = head.post;
        head.post.pre = node;
        head.post = node;
    }

    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;
        pre.post = post;
        post.pre = pre;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addNode(node);
    }

    private DLinkedNode popTail() {
        DLinkedNode res = tail.pre;
        removeNode(res);
        return res;
    }
}

Simple implementation extending LinkedHashMap:

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;
    public LRUCache(int cacheSize) {
        super((int)Math.ceil(cacheSize/0.75)+1, 0.75f, true);
        CACHE_SIZE = cacheSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > CACHE_SIZE;
    }
}

Redis LRU Implementation

Redis uses an approximate LRU algorithm to avoid the overhead of storing explicit prev/next pointers. It maintains a global LRU clock ( server.lruclock) and periodically updates it based on server.unixtime and a configurable resolution.

#define REDIS_LRU_BITS 24
unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1 /* LRU clock resolution in seconds */

void updateLRUClock(void) {
    server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) & REDIS_LRU_CLOCK_MAX;
}

The function estimateObjectIdleTime computes how many seconds a key has not been accessed, handling clock wrap‑around.

unsigned long estimateObjectIdleTime(robj *o) {
    if (server.lruclock >= o->lru) {
        return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
    } else {
        return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) * REDIS_LRU_CLOCK_RESOLUTION;
    }
}

Redis supports two LRU‑related eviction policies: volatile-lru (only keys with an expiration) and allkeys-lru (all keys). During eviction, Redis samples a configurable number of keys (default 5), estimates their idle times, and removes the one with the highest idle time.

for (k = 0; k < server.maxmemory_samples; k++) {
    de = dictGetRandomKey(dict);
    thiskey = dictGetKey(de);
    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
        de = dictFind(db->dict, thiskey);
    o = dictGetVal(de);
    thisval = estimateObjectIdleTime(o);
    if (bestkey == NULL || thisval > bestval) {
        bestkey = thiskey;
        bestval = thisval;
    }
}

Increasing server.maxmemory_samples makes Redis's approximation closer to true LRU at the cost of higher CPU usage.

Source: https://www.cnblogs.com/weknow619/p/10730653.html