LRU кеш. Алгоритм и реализация в Go.

LRU - вытеснение наименее недавно использованного. Структура: хеш-таблица (ключ -> узел) + двусвязный список по времени доступа. При обращении перемещать узел в голову; при переполнении удалять хвост. В Go: map + список (container/list или свой). Готовые реализации: hashicorp/golang-lru. Сложность Get/Put - O(1).

type LRU struct {
    cap  int
    m    map[string]*list.Element
    list *list.List
}
func (c *LRU) Get(key string) (interface{}, bool) {
    if e, ok := c.m[key]; ok {
        c.list.MoveToFront(e)
        return e.Value.(*item).val, true
    }
    return nil, false
}