LRU Cache — что это такое, алгоритм вытеснения и как работает

Что такое LRU Cache?

LRU Cache (Least Recently Used Cache) — это структура данных фиксированного размера, которая хранит ограниченное количество элементов и автоматически удаляет те, к которым обращались реже всего. Когда приложение запрашивает элемент, он перемещается в «свежую» часть кэша, а давно неиспользованные элементы смещаются к концу и удаляются при достижении лимита.

Название «Least Recently Used» описывает политику вытеснения: удаляется элемент, который не использовался дольше всех среди всех хранящихся. Это основано на предположении о локальности обращений (locality of reference) — недавно запрошенные данные с высокой вероятностью понадобятся снова. Именно поэтому LRU считается одной из самых эффективных стратегий кэширования для большинства приложений.

Классическая реализация LRU Cache требует две структуры данных: хеш-таблицу для доступа O(1) к любому элементу по ключу и двусвязный список для отслеживания порядка использования. Хеш-таблица хранит ссылки на узлы списка, а список поддерживает порядок от самого нового элемента (голова) до самого старого (хвост).

Основные операции LRU Cache

Операция get(key) проверяет наличие ключа в хеш-таблице. Если элемент найден, он перемещается в голову списка (становится самым новым) и возвращается его значение. Если не найден — возвращается null или выбрасывается исключение. Операция put(key, value) вставляет новый элемент: если ключ уже существует — обновляется значение и элемент перемещается в голову. Если кэш заполнен, перед вставкой удаляется хвостовой элемент списка. Все операции выполняются за константное время O(1).

Как работает LRU Cache

Алгоритм LRU Cache основан на двух принципах: счётчик обращений в порядке времени и механика вытеснения при переполнении. Каждый элемент хранится в узле двусвязного списка, а указатели на эти узлы — в хеш-таблице. При каждом обращении к элементу он отсоединяется от текущей позиции и вставляется в начало списка.

Когда размер кэша достигает максимального значения (maxSize) и поступает запрос на вставку нового элемента, алгоритм удаляет хвостовой элемент двусвязного списка — это и есть наименее недавно использованный элемент. После удаления освобождается место для нового элемента, который вставляется в голову списка. Хеш-таблица при этом обновляется: старый ключ удаляется, новый добавляется.

Особенность LRU — нечувствительность к паттернам доступа с циклическим повторением. Если приложение периодически обращается к большему набору данных, чем размер кэша, LRU может страдать от thrashing — частой замены элементов, когда каждый новый запрос вытесняет предыдущий. В таких сценариях более эффективными могут оказаться LFU (Least Frequently Used) или адаптивные алгоритмы.

Размер кэша и метрики

Выбор размера LRU Cache — компромисс между потреблением памяти и hit-ratio (процентом успешных обращений). Типичные значения для мобильных приложений: 10–20% от доступной памяти для кэша изображений и 50–200 записей для кэша сетевых ответов. Hit-ratio 80–95% считается хорошим показателем, при котором кэш оправдывает затраты памяти. Для мониторинга используют счётчики hitCount и missCount, доступные в реализации LruCache в Android.

Реализация LRU Cache: HashMap + Doubly Linked List

Каноническая реализация LRU Cache использует комбинацию хеш-таблицы и двусвязного списка. Хеш-таблица обеспечивает доступ к любому узлу по ключу за O(1), а двусвязный список — перемещение узла в начало и удаление с конца за O(1). Важно, что список именно двусвязный: это позволяет отсоединять узел из середины списка без перебора всех элементов.

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)
    }
}

В реализации каждый узел (Node) хранит значение и ссылки на предыдущий и следующий узлы. Sentinel-узлы head и tail упрощают граничные случаи — не нужно проверять на null при вставке и удалении. Метод get перемещает найденный узел в голову, а put при переполнении удаляет хвостовой элемент. Отдельный метод removeKeyByValue находит ключ в хеш-таблице по ссылке на узел и удаляет его.

Встроенная реализация LruCache в Android

Android SDK предоставляет готовый класс LruCache в пакете android.util, который реализует LRU алгоритм с использованием LinkedHashMap в режиме access-order. Класс thread-safe, поддерживает подсчёт hit/miss, а также предоставляет колбэк entryRemoved для освобождения ресурсов при вытеснении элемента. Размер кэша задаётся в произвольных единицах (байты, количество элементов) — достаточно переопределить метод sizeOf.

LRU Cache vs FIFO и LIFO

Все три алгоритма — LRU, FIFO и LIFO — решают одну задачу: ограничение потребления памяти через вытеснение элементов при переполнении. Однако они используют принципиально разные критерии для выбора жертвы, что определяет их эффективность в разных сценариях.

FIFO вытесняет самый старый элемент по времени добавления, независимо от того, как часто к нему обращались. Это может быть неэффективно, если старый элемент всё ещё актуален. LRU избегает этого недостатка, учитывая паттерн обращений. LIFO вытесняет свежедобавленный элемент — полезно для сценариев undo, но непригодно для кэширования, так как новые данные часто нужнее старых. LRU считается оптимальным балансом между сложностью реализации и hit-ratio для большинства приложений.

Примеры кода LRU Cache

Рассмотрим использование встроенного класса LruCache из Android SDK для кэширования загруженных изображений. Пример показывает инициализацию кэша на 1/8 доступной памяти приложения, что является стандартной рекомендацией Google для кэша изображений.

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)
    }
}

Метод sizeOf возвращает размер элемента в тех же единицах, в которых задан cacheSize. Здесь используется размер Bitmap в килобайтах (rowBytes × height / 1024). Когда сумма sizeOf всех элементов превышает cacheSize, LruCache автоматически вытесняет наименее недавно использованные Bitmap. Колбэк entryRemoved можно использовать для вызова bitmap.recycle() — освобождения памяти до вытеснения.

Реализация LRU Cache на Swift

В iOS нет встроенного класса LRU Cache, но его легко реализовать через NSCache (который использует схожую, но не документированную политику вытеснения) или через собственную реализацию на Dictionary + Doubly Linked List, как показано ниже.

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)
    }
}

В данной Swift-реализации Node — внутренний класс с полями value, next и prev. Метод moveToHead отсоединяет узел от текущей позиции и вставляет в начало списка. При переполнении удаляется tail — наименее недавно использованный элемент. Для production рекомендуется также добавлять потокобезопасность через NSLock или очередь DispatchQueue.