How to implement a generic LRU cache in Go

Use Go generics and container/list to achieve thread-safe LRU cache; 2. Core components include maps, bidirectional linked lists and mutex locks; 3. Get and Add operations ensure concurrency security through locks, with a time complexity of O(1); 4. Automatically eliminate the longest unused entry when the cache is full; 5. In the example, the cache with capacity of 3 successfully eliminates the longest unused "b". This implementation fully supports generic, efficient and scalable.

Implementing a generic LRU (Least Recently Used) cache in Go is straightforward using Go's built-in data structures and the container/list package. With Go 1.18 generics, you can create a reusable LRU cache that works with any key and value types, as long as the key is comparable.

Here's how to build a thread-safe, generic LRU cache:

✅ Key Components

We'll use:

• map[K]*list.Element — to store key-to-node mapping for O(1) access.
• list.List — a double-linked list to maintain access order (most recently used at back, least at front).
• A sync.Mutex — for thread safety.
• Generics — to allow any comparable key type K and any value type V .

? Step-by-step Implementation

 package main

import (
    "container/list"
    "sync"
)

// LRUCache is a generic LRU cache.
type LRUCache[K comparable, V any] struct {
    capacity int
    cache map[K]*list.Element
    ll *list.List // double-linked list to track order
    mu sync.Mutex
}

// entry is a key-value pair stored in the list
type entry[K comparable, V any] struct {
    key K
    value V
}

// NewLRUCache creates a new LRU cache with the given capacity.
func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V] {
    return &LRUCache[K, V]{
        capacity: capacity,
        cache: make(map[K]*list.Element),
        ll: list.New(),
    }
}

// Get retrieves a value by key. Returns value and true if found.
func (c *LRUCache[K, V]) Get(key K) (V, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    var zero V
    elem, exists := c.cache[key]
    if !exists {
        return zero, false
    }

    // Move the accessed element to the back (most recently used)
    c.ll.MoveToBack(elem)
    return elem.Value.(*entry[K, V]).value, true
}

// Add inserts a key-value pair into the cache.
// If the key exists, it updates the value and marks it as recently used.
// If the cache is full, it evils the least recently used item.
func (c *LRUCache[K, V]) Add(key K, value V) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, exists := c.cache[key]; exists {
        // Update value and move to back
        elem.Value.(*entry[K, V]).value = value
        c.ll.MoveToBack(elem)
        Return
    }

    // Add new element to the back
    newElem := c.ll.PushBack(&entry[K, V]{key: key, value: value})
    c.cache[key] = newElem

    // Evict if over capacity
    if c.ll.Len() > c.capacity {
        c.evict()
    }
}

// evict removes the least recently used item (front of list)
func (c *LRUCache[K, V]) evict() {
    if elem := c.ll.Front(); elem != nil {
        c.ll.Remove(elem)
        key := elem.Value.(*entry[K, V]).key
        delete(c.cache, key)
    }
}

// Len returns the current number of items in the cache.
func (c *LRUCache[K, V]) Len() int {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.ll.Len()
}

✅ Example Usage

 func main() {
    cache := NewLRUCache[string, int](3)

    cache.Add("a", 1)
    cache.Add("b", 2)
    cache.Add("c", 3)

    // Access "a" → moves to back (most recently used)
    if val, ok := cache.Get("a"); ok {
        println("Got:", val) // Got: 1
    }

    // Add "d" → should evict "b" ( least recently used)
    cache.Add("d", 4)

    // Check contents
    if _, ok := cache.Get("b"); !ok {
        println("b was evicted")
    }
    if _, ok := cache.Get("a"); ok {
        println("a still exists")
    }
    if _, ok := cache.Get("d"); ok {
        println("d exists")
    }
}

? Thread Safety

The cache is thread-safe due to the sync.Mutex . All operations are protected by a mutex lock. For high-concurrency use, consider using RWMutex (read-write mutex) to allow concurrent reads.

⚙️ Performance

• Get : O(1)
• Add : O(1)
• Eviction : O(1)

This makes it efficient for most practical use cases.

? Notes

• The key type K must be comparable (required by Go maps).
• The value type V can be any type ( any ).
• You can extend this with features like TTL (time-to-live), callbacks on eviction, or size-based eviction.

That's it. You now have a clean, generic, thread-safe LRU cache in Go.

The above is the detailed content of How to implement a generic LRU cache in Go. For more information, please follow other related articles on the PHP Chinese website!