LRU Cache

LRU Cache - полное решение

Описание задачи

LRU (Least Recently Used) Cache - это кэширующая структура данных с фиксированной ёмкостью, которая автоматически вытесняет наименее недавно использованный элемент при переполнении. Это часто используется для оптимизации доступа к часто используемым данным.

Архитектурное решение

Для достижения O(1) сложности для обеих операций используем комбинацию двух структур данных:

1. Двусвязный список (doubly-linked list) - для хранения элементов в порядке использования
2. *HashMap (map[int]Node) - для быстрого поиска элемента за O(1)

Двусвязный список позволяет за O(1) переместить элемент в конец (самый свежий) и удалить элемент из начала (самый старый).

Реализация

package main

import "fmt"

type Node struct {
    key, value int
    prev, next *Node
}

type LRUCache struct {
    capacity int
    cache    map[int]*Node
    head     *Node // dummy head для удобства
    tail     *Node // dummy tail для удобства
}

func NewLRUCache(capacity int) *LRUCache {
    head := &Node{}
    tail := &Node{}
    head.next = tail
    tail.prev = head
    
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*Node),
        head:     head,
        tail:     tail,
    }
}

// Get возвращает значение по ключу и обновляет его как недавно использованный
func (c *LRUCache) Get(key int) (int, bool) {
    node, exists := c.cache[key]
    if !exists {
        return 0, false
    }
    
    // Переместить в конец (самый свежий)
    c.moveToEnd(node)
    return node.value, true
}

// Put добавляет или обновляет значение в кэше
func (c *LRUCache) Put(key, value int) {
    if node, exists := c.cache[key]; exists {
        // Ключ уже существует - обновляем значение и перемещаем в конец
        node.value = value
        c.moveToEnd(node)
        return
    }
    
    // Новый ключ
    newNode := &Node{key: key, value: value}
    c.cache[key] = newNode
    c.addToEnd(newNode)
    
    // Если превышена ёмкость - удаляем самый старый элемент
    if len(c.cache) > c.capacity {
        oldest := c.head.next
        c.removeNode(oldest)
        delete(c.cache, oldest.key)
    }
}

// moveToEnd перемещает узел в конец (самый свежий)
func (c *LRUCache) moveToEnd(node *Node) {
    c.removeNode(node)
    c.addToEnd(node)
}

// addToEnd добавляет узел в конец (перед tail)
func (c *LRUCache) addToEnd(node *Node) {
    prev := c.tail.prev
    prev.next = node
    node.prev = prev
    node.next = c.tail
    c.tail.prev = node
}

// removeNode удаляет узел из списка
func (c *LRUCache) removeNode(node *Node) {
    prev := node.prev
    next := node.next
    prev.next = next
    next.prev = prev
}

// Пример использования
func main() {
    cache := NewLRUCache(2)
    
    cache.Put(1, 1)
    cache.Put(2, 2)
    
    val, ok := cache.Get(1)
    fmt.Printf("Get(1): %d, %v\\n", val, ok) // 1, true
    
    cache.Put(3, 3) // Вытесняет ключ 2
    
    val, ok = cache.Get(2)
    fmt.Printf("Get(2): %v\\n", ok) // false
    
    val, ok = cache.Get(3)
    fmt.Printf("Get(3): %d, %v\\n", val, ok) // 3, true
}

Анализ сложности

• Time:

  • Get(key) - O(1) (lookup в map + переместить в конец)
  • Put(key, value) - O(1) (добавить/обновить + управление списком)

• Space: O(capacity) - храним максимум capacity элементов

Ключевые моменты реализации

1. Dummy узлы (head и tail) - упрощают код, избегаем nil checks при добавлении/удалении
2. Двусвязный список - позволяет за O(1) удалить узел из любой позиции
3. HashMap - обеспечивает O(1) lookup при получении значения
4. Порядок элементов - head.next указывает на самый старый, tail.prev на самый свежий

Альтернативы

• Контейнер list - можно использовать встроенный пакет list вместо ручной реализации
• sync.Map с RWMutex - для многопоточного кэша требуется добавление синхронизации