Создание LRU‑кэша с методами Get и Put

Условие

Необходимо реализовать структуру данных LRU‑кеш, предоставляющую два публичных метода. Метод Get(key) возвращает сохранённое значение по заданному ключу, а если ключ отсутствует — возвращает -1. Метод Put(key, value) вставляет новую пару или обновляет существующую. При достижении предельного размера кэша следует удалять элемент, который использовался дольше всех.

type LRUCache struct {}

func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Пример применения:

cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
cache.Get(1)    // вернёт 1
cache.Put(3, 3) // удалит ключ 2
cache.Get(2)    // вернёт -1 (не найден)
cache.Put(4, 4) // удалит ключ 1
cache.Get(1)    // вернёт -1 (не найден)
cache.Get(3)    // вернёт 3
cache.Get(4)    // вернёт 4

Ответ

LRU реализуется сочетанием map и двусвязного списка: map находит запись за O(1) в среднем, список переносит её в начало и удаляет самый давно использованный элемент с конца.

Нужен импорт container/list:

type pair struct { key, value int }
type LRUCache struct {
    capacity int
    order *list.List
    items map[int]*list.Element
}
func Constructor(capacity int) LRUCache {
    return LRUCache{capacity, list.New(), make(map[int]*list.Element)}
}
func (c *LRUCache) Get(key int) int {
    e, ok := c.items[key]
    if !ok { return -1 }
    c.order.MoveToFront(e)
    return e.Value.(pair).value
}
func (c *LRUCache) Put(key, value int) {
    if c.capacity <= 0 { return }
    if e, ok := c.items[key]; ok {
        e.Value = pair{key, value}
        c.order.MoveToFront(e)
        return
    }
    c.items[key] = c.order.PushFront(pair{key, value})
    if c.order.Len() > c.capacity {
        e := c.order.Back()
        delete(c.items, e.Value.(pair).key)
        c.order.Remove(e)
    }
}

Создавайте через Constructor и не копируйте работающий экземпляр. Память O(capacity); конкурентный доступ требует общей блокировки и для Get, поскольку он меняет порядок. Здесь вытесняется давно не использованный, а не дольше всего хранившийся ключ.