Как бы вы реализовали LRU-кэш на Go? Расскажите о структурах данных, которые вы бы использовали, и их временной сложности.

Ответ

Да, реализация LRU (Least Recently Used) кэша — это классическая задача, которая отлично демонстрирует понимание структур данных.

Для эффективной реализации LRU-кэша в Go я бы использовал комбинацию двух структур данных:

*Хэш-мапа (`map[keyType]list.Element`): для хранения пар ключ-значение. Она обеспечивает быстрый доступ к элементам кэша по ключу за среднее время O(1)**.
Двусвязный список (container/list): для отслеживания порядка использования элементов. Самый недавно использованный элемент будет в начале списка, а самый давно неиспользуемый — в конце. Операции добавления в начало и удаления элемента из любой части списка (при наличии указателя на него) выполняются за O(1).

Сочетание этих двух структур позволяет добиться того, что и операция Get, и операция Put будут иметь временную сложность O(1).

Пример реализации:

package main

import "container/list"

// LRUCache представляет собой LRU-кэш.
// Важно: данная реализация не является потокобезопасной.
// Для конкурентного использования необходимо добавить мьютекс (sync.RWMutex).
type LRUCache struct {
    capacity int
    cache    map[int]*list.Element // Ключ -> Указатель на узел в списке
    list     *list.List            // Двусвязный список для порядка использования
}

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

// NewLRUCache создает новый LRU-кэш с заданной вместимостью.
func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

// Get получает значение по ключу. Если ключ найден, элемент перемещается в начало списка.
func (l *LRUCache) Get(key int) int {
    if elem, ok := l.cache[key]; ok {
        l.list.MoveToFront(elem) // O(1)
        return elem.Value.(*entry).value
    }
    return -1
}

// Put добавляет или обновляет значение по ключу.
func (l *LRUCache) Put(key, value int) {
    // Если элемент уже существует, обновляем его значение и перемещаем в начало.
    if elem, ok := l.cache[key]; ok {
        l.list.MoveToFront(elem) // O(1)
        elem.Value.(*entry).value = value
        return
    }

    // Если кэш заполнен, удаляем самый старый элемент (из конца списка).
    if l.list.Len() >= l.capacity {
        oldest := l.list.Back() // O(1)
        if oldest != nil {
            l.list.Remove(oldest) // O(1)
            delete(l.cache, oldest.Value.(*entry).key) // O(1)
        }
    }

    // Добавляем новый элемент в начало списка и в мапу.
    newEntry := &entry{key, value}
    elem := l.list.PushFront(newEntry) // O(1)
    l.cache[key] = elem // O(1)
}

Принцип работы и сложность:

Get(key): Мы ищем ключ в map (O(1)). Если находим, то получаем указатель на узел в списке и перемещаем этот узел в начало списка с помощью MoveToFront (O(1)). Общая сложность — O(1).
Put(key, value):
- Если элемент существует, мы находим его в map (O(1)), обновляем значение и перемещаем в начало списка (O(1)).
- Если элемента нет и кэш переполнен, мы удаляем последний элемент из списка (list.Back() и list.Remove(), оба O(1)) и из map (O(1)).
- Затем добавляем новый элемент в начало списка (PushFront, O(1)) и в map (O(1)).
- Общая сложность в любом случае — O(1).

Важное замечание: Эта реализация не является потокобезопасной. Для использования в конкурентной среде необходимо добавить sync.RWMutex для защиты доступа к cache и list.