To implement a concurrency-safe O(1) LRU cache in Go, use a hashmap for O(1) lookup and a doubly-linked list (container/list) to track recency. Protect state with a sync.RWMutex. Validate capacity and keys to enforce constraints.go
package lru
import (
"container/list"
"errors"
"sync"
)
// Cache is a concurrency-safe LRU cache.
type Cache struct {
mu sync.RWMutex
capacity int
ll *list.List
table map[string]*list.Element
}
type entry struct {
key string
value interface{}
}
// New creates an LRU cache with positive capacity.
func New(capacity int) (*Cache, error) {
if capacity <= 0 {
return nil, errors.New("capacity must be > 0")
}
return &Cache{
capacity: capacity,
ll: list.New(),
table: make(map[string]*list.Element, capacity),
}, nil
}
// Get returns value and whether it existed. Access updates recency.
func (c *Cache) Get(key string) (interface{}, bool) {
if key == "" {
return nil, false
}
c.mu.Lock()
defer c.mu.Unlock()
if ele, ok := c.table[key]; ok {
c.ll.MoveToFront(ele)
return ele.Value.(*entry).value, true
}
return nil, false
}
// Put inserts or updates the key. Evicts least-recently-used when capacity exceeded.
func (c *Cache) Put(key string, value interface{}) {
if key == "" {
return // reject empty keys
}
c.mu.Lock()
defer c.mu.Unlock()
if ele, ok := c.table[key]; ok {
ele.Value.(*entry).value = value
c.ll.MoveToFront(ele)
return
}
ele := c.ll.PushFront(&entry{key: key, value: value})
c.table[key] = ele
if c.ll.Len() > c.capacity {
// evict LRU (back)
ev := c.ll.Back()
if ev != nil {
c.ll.Remove(ev)
delete(c.table, ev.Value.(*entry).key)
}
}
}
// Len returns current size.
func (c *Cache) Len() int {
c.mu.RLock()
defer c.mu.RUnlock()
return c.ll.Len()
}
Unit tests (edge cases: zero capacity, empty key, eviction):go
package lru_test
import (
"testing"
"your/module/path/lru"
)
func TestNewZeroCapacity(t *testing.T) {
if _, err := lru.New(0); err == nil {
t.Fatal("expected error for zero capacity")
}
}
func TestEmptyKeyRejected(t *testing.T) {
c, _ := lru.New(2)
c.Put("", "x")
if c.Len() != 0 {
t.Fatalf("expected len 0, got %d", c.Len())
}
if v, ok := c.Get(""); ok || v != nil {
t.Fatal("expected no value for empty key")
}
}
func TestEvictionOrder(t *testing.T) {
c, _ := lru.New(2)
c.Put("a", 1)
c.Put("b", 2)
// access a to make b the LRU
if _, ok := c.Get("a"); !ok {
t.Fatal("expected a to exist")
}
c.Put("c", 3) // should evict b
if _, ok := c.Get("b"); ok {
t.Fatal("expected b to be evicted")
}
if v, ok := c.Get("a"); !ok || v.(int) != 1 {
t.Fatal("expected a still present")
}
if v, ok := c.Get("c"); !ok || v.(int) != 3 {
t.Fatal("expected c present")
}
}
Key points:- O(1) get/put via map + linked list- sync.RWMutex ensures concurrency safety- Capacity enforced at construction; empty keys rejectedTime complexity: O(1) average for Get/Put. Space: O(capacity). Edge cases: nil/empty keys, concurrent access, updating existing keys, eviction when size > capacity.