LRU Cache — what it is, eviction algorithm and how it works

What is LRU Cache?

LRU Cache (Least Recently Used Cache) is a fixed-size data structure that stores a limited number of elements and automatically removes those that have been accessed least frequently. When an application requests an element, it moves to the “fresh” part of the cache, while long-unused elements shift toward the end and are removed when the limit is reached.

The name “Least Recently Used” describes the eviction policy: the element that has not been used the longest among all stored elements is removed. This is based on the assumption of locality of reference — recently requested data is highly likely to be needed again. This is why LRU is considered one of the most effective caching strategies for most applications.

The classic LRU Cache implementation requires two data structures: a hash table for O(1) access to any element by key and a doubly linked list for tracking usage order. The hash table stores references to list nodes, and the list maintains order from the newest element (head) to the oldest (tail).

Basic LRU Cache Operations

The get(key) operation checks whether the key exists in the hash table. If found, the element moves to the head of the list (becomes the newest) and its value is returned. If not found, null is returned or an exception is thrown. The put(key, value) operation inserts a new element: if the key already exists, the value is updated and the element moves to the head. If the cache is full, the tail element of the list is removed before insertion. All operations execute in constant time O(1).

How LRU Cache Works

The LRU Cache algorithm is based on two principles: time-ordered access counting and the eviction mechanism on overflow. Each element is stored in a doubly linked list node, and pointers to these nodes are kept in the hash table. On each access, the element is detached from its current position and inserted at the head of the list.

When the cache size reaches its maximum value (maxSize) and a request to insert a new element arrives, the algorithm removes the tail element of the doubly linked list — this is the least recently used element. After removal, space is freed for the new element, which is inserted at the head of the list. The hash table is updated accordingly: the old key is removed, a new one is added.

A characteristic of LRU is its sensitivity to access patterns with cyclic repetition. If the application periodically accesses a larger data set than the cache size, LRU may suffer from thrashing — frequent element replacement where each new request evicts the previous one. In such scenarios, LFU (Least Frequently Used) or adaptive algorithms may be more effective.

Cache Size and Metrics

Choosing the LRU Cache size is a trade-off between memory consumption and hit-ratio (percentage of successful accesses). Typical values for mobile applications: 10–20% of available memory for image cache and 50–200 entries for network response cache. A hit-ratio of 80–95% is considered good, where the cache justifies memory costs. For monitoring, hitCount and missCount counters are used, available in the LruCache implementation in Android.

LRU Cache Implementation: HashMap + Doubly Linked List

The canonical LRU Cache implementation uses a combination of a hash table and a doubly linked list. The hash table provides O(1) access to any node by key, while the doubly linked list enables O(1) node movement to the head and removal from the tail. Crucially, the list is doubly linked: this allows detaching a node from the middle of the list without iterating through all elements.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

In the implementation, each node (Node) stores a value and references to the previous and next nodes. Sentinel nodes head and tail simplify edge cases — no need to check for null on insertion and removal. The get method moves the found node to the head, and put removes the tail element on overflow. A separate method removeKeyByValue finds the key in the hash table by node reference and removes it.

Built-in LruCache Implementation in Android

The Android SDK provides a ready-made LruCache class in the android.util package, which implements the LRU algorithm using LinkedHashMap in access-order mode. The class is thread-safe, supports hit/miss counting, and provides the entryRemoved callback for resource cleanup on element eviction. Cache size is set in arbitrary units (bytes, number of elements) — simply override the sizeOf method.

LRU Cache vs FIFO and LIFO

All three algorithms — LRU, FIFO and LIFO — solve the same problem: limiting memory consumption by evicting elements on overflow. However, they use fundamentally different criteria for selecting the victim, which determines their effectiveness in different scenarios.

FIFO evicts the oldest element by insertion time, regardless of how often it has been accessed. This can be inefficient if an old element is still relevant. LRU avoids this drawback by considering the access pattern. LIFO evicts the most recently added element — useful for undo scenarios, but unsuitable for caching, since new data is often more needed than old data. LRU is considered the optimal balance between implementation complexity and hit-ratio for most applications.

LRU Cache Code Examples

Let us consider using the built-in LruCache class from the Android SDK for caching downloaded images. The example shows initializing the cache to 1/8 of the available application memory, which is Google’s standard recommendation for image caching.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

The sizeOf method returns the element size in the same units in which cacheSize is specified. Here, the Bitmap size in kilobytes is used (rowBytes × height / 1024). When the sum of all elements’ sizeOf exceeds cacheSize, LruCache automatically evicts the least recently used Bitmaps. The entryRemoved callback can be used to call bitmap.recycle() — freeing memory before eviction.

LRU Cache Implementation in Swift

iOS does not have a built-in LRU Cache class, but it is easy to implement using NSCache (which uses a similar but undocumented eviction policy) or through a custom implementation using Dictionary + Doubly Linked List, as shown below.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

In this Swift implementation, Node is an internal class with value, next and prev fields. The moveToHead method detaches a node from its current position and inserts it at the head of the list. On overflow, the tail — the least recently used element — is removed. For production, it is recommended to add thread safety via NSLock or a DispatchQueue.