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

А, LRU Cache, ёпта! Ну это ж классика, как "Муму" Тургенева, только без утопления собаки, блядь. Сейчас объясню, как этот цирк работает, чтобы ты не сидел, как Герасим, и мычал "му-му", когда тебя спросят.

Представь себе, у тебя есть полка, но она маленькая, сука, как будто в хрущёвке. На неё можно поставить только, допустим, пять тарелок. А тарелок у тебя — овердохуища. Что делать, блядь? Ставишь самые нужные, которые чаще всего берёшь. А какую убрать, когда место кончилось? Ту, которую ты брал ДАЛЬШЕ ВСЕГО В ПРОШЛОМ! Ту, до которой ты уже руки не доходил сто лет. Вот это и есть Least Recently Used, ёбта.

А теперь технические детали, без них никуда, как без мата в русской речи. Чтобы это всё работало быстро, а не как мартышка с гранатой, нужны две штуки:

1. Хеш-таблица (map). Это твой быстрый пацан, который за O(1) отвечает: "Э, брат, а тарелка с ключом 'борщ' у тебя есть?". И если есть, сразу пальцем тычет, где она.
2. Двусвязный список (list). Это твоя священная хронология, блядь. В начале списка — самые свежие, горячие тарелки, которые ты только что помыл или взял. В конце — те, что покрылись пылью и паутиной, как идеи у чиновника.

Как это всё ебётся в работе:

• Get(key) — достать тарелку. Заходишь на кухню, спрашиваешь у пацана (map): "Где тарелка для пельменей?". Он тебе: "Да вот же она, вон там, в списке". Ты её берёшь, хуяк — и сразу переставляешь в НАЧАЛО стопки. Теперь она самая свежая, царица бала. Возвращаешь её (значение). Если пацан говорит "нет такой", возвращаешь -1, то есть грустный смайлик.

• Put(key, value) — положить или обновить тарелку. Ситуация первая: ты взял тарелку для пельменей, а она грязная. Ты её помыл (обновил значение) и, ясное дело, поставил в начало стопки — она же теперь чистая, блядь. Ситуация вторая: ты купил НОВУЮ тарелку для оливье. Смотришь на полку — а там уже пять штук, мест нет, ёперный театр! Что делаешь? Берёшь самую дальнюю, древнюю, забытую всеми тарелку с ХВОСТА списка (ну ту, для селёдки под шубой, которую никто не ест) и выкидываешь её нахуй в мусорку (удаляешь из map). Освободилось место — ставишь свою новую блестящую тарелку для оливье в НАЧАЛО стопки и записываешь в блокнот пацана (map), что она теперь есть.

Вот и весь алгоритм, в рот меня чих-пых! А теперь смотри, как это выглядит в коде на Go, чтобы ты не думал, что это какая-то пиздопроебибная магия.

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
}

Где это, блядь, применяется? Да везде, где нужно быстро работать, но память не резиновая! Веб-сервера, чтобы не ходить в базу за каждым постом Вконтакте, базы данных, операционки... Короче, везде, где есть хоть капля здравого смысла.