Что такое LRU Cache и как он устроен?

Ответ

LRU (Least Recently Used) Cache — это алгоритм кеширования, который при заполнении кеша удаляет элементы, которые использовались реже всего (точнее, дальше всего в прошлом).

Как он работает:

Классическая реализация LRU Cache использует две структуры данных:

Хеш-таблица (map): для быстрого доступа к элементу по ключу за время O(1).
Двусвязный список (doubly-linked list): для отслеживания порядка использования элементов. В начало списка помещаются самые свежие (недавно использованные) элементы, а в конце остаются самые старые.

Логика операций:

Get(key) (Получение элемента):
1. Ищем элемент в хеш-таблице.
2. Если нашли, перемещаем соответствующий узел в начало двусвязного списка (делаем его самым свежим).
3. Возвращаем значение.
Put(key, value) (Добавление/обновление элемента):
1. Если элемент уже есть в кеше, обновляем его значение и перемещаем в начало списка.
2. Если элемента нет:
  - Если кеш заполнен, удаляем самый старый элемент (из хвоста списка и из хеш-таблицы).
  - Создаем новый узел и добавляем его в начало списка и в хеш-таблицу.

Пример реализации в Go (с использованием container/list):

import "container/list"

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element // Карта для доступа к узлам списка O(1)
    list     *list.List            // Двусвязный список для порядка использования
}

// Вспомогательная структура для хранения пары ключ-значение в списке
type entry struct {
    key, value int
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem) // Перемещаем в начало как недавно использованный
        return elem.Value.(*entry).value
    }
    return -1
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    if c.list.Len() >= c.capacity {
        // Удаляем самый старый элемент (из хвоста)
        oldest := c.list.Back()
        if oldest != nil {
            c.list.Remove(oldest)
            delete(c.cache, oldest.Value.(*entry).key)
        }
    }

    // Добавляем новый элемент в начало
    newEntry := &entry{key, value}
    elem := c.list.PushFront(newEntry)
    c.cache[key] = elem
}

Применение: кеширование данных в веб-серверах, базах данных, операционных системах — везде, где нужно хранить ограниченный объем часто запрашиваемых данных.