Библиотека LRU‑кеша для внешнего использования

Условие

Требуется создать экспортируемый модуль, который реализует кеш с политикой «наименее недавно использованного». В библиотеке должны быть два публичных метода: Get(key) — возвращает значение, связанное с переданным ключом (или сообщает об отсутствии), и Put(key, value) — вставляет новую пару ключ‑значение либо обновляет существующую, при этом при переполнении удаляя самый «старый» элемент, чтобы поддерживать ограниченный размер кеша.

Ответ

Экспортируйте конструктор и методы Get/Put, а внутри сочетайте map с двусвязным списком. Чтение тоже меняет порядок LRU и требует синхронизации при конкурентном использовании.

Минимальная библиотека для Go 1.18+:

package lru

import (
    "container/list"
    "sync"
)
type entry[K comparable, V any] struct { key K; value V }
type Cache[K comparable, V any] struct {
    mu sync.Mutex
    capacity int
    order *list.List
    items map[K]*list.Element
}
func New[K comparable, V any](capacity int) *Cache[K,V] {
    if capacity < 1 { panic("capacity must be positive") }
    return &Cache[K,V]{capacity: capacity, order: list.New(),
        items: make(map[K]*list.Element)}
}
func (c *Cache[K,V]) Get(key K) (V, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    e, ok := c.items[key]
    if !ok { var zero V; return zero, false }
    c.order.MoveToFront(e)
    return e.Value.(entry[K,V]).value, true
}
func (c *Cache[K,V]) Put(key K, value V) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if e, ok := c.items[key]; ok {
        e.Value = entry[K,V]{key, value}
        c.order.MoveToFront(e)
        return
    }
    c.items[key] = c.order.PushFront(entry[K,V]{key, value})
    if c.order.Len() > c.capacity {
        e := c.order.Back()
        delete(c.items, e.Value.(entry[K,V]).key)
        c.order.Remove(e)
    }
}

Создавайте через New и не копируйте Cache после использования. Операции в среднем O(1), память O(capacity). «Самый старый» означает давно не использованный, не первым вставленный. Mutex защищает контейнер, но возвращаемые ссылочные значения требуют собственной политики неизменяемости или копирования.