← Back to DevBytes
Go August 05, 2026 12 min read

Solving LFU Cache Implementation in Go: Step-by-Step Guide

Solving LFU Cache Implementation in Go: Step-by-Step Guide

The Least Frequently Used (LFU) cache eviction policy is one of the most fascinating and challenging data structures to implement correctly. Unlike its simpler cousin LRU (Least Recently Used), which only tracks access recency, LFU tracks how often each item is accessed and evicts the one with the lowest frequency. In this tutorial, we will build a production-quality LFU cache in Go from scratch, exploring the underlying data structures, the algorithm, and the trade-offs along the way.

What Is an LFU Cache?

An LFU cache is a fixed-capacity key-value store that automatically evicts entries when it runs out of space. The eviction candidate is always the item that has been accessed the fewest times. When multiple items share the same lowest frequency, the least recently used among them is evicted — this tie-breaking rule is what makes LFU a hybrid of frequency and recency tracking.

The cache must support two core operations in constant or near-constant time:

Why LFU Matters

LFU shines in scenarios where access patterns are skewed — a small subset of items is accessed repeatedly while many items are accessed only once. Common real-world applications include:

Compared to LRU, LFU is more resistant to one-time scans flushing out genuinely popular items. However, LFU can suffer from "cache pollution" — items that were popular in the past but are no longer accessed can linger. Many production systems use hybrid policies like LRU-K or W-TinyLFU to mitigate this.

Data Structures Required

To achieve O(1) average time complexity for both Get and Put, we need a combination of three data structures:

We also track a minFreq integer so we always know which frequency list contains the eviction candidate.

Step 1: Defining the Node and Doubly Linked List

Each cache entry is represented by a node holding the key, value, and current frequency. The doubly linked list lets us move nodes between frequency buckets efficiently.

package lfu

// node represents a single cache entry.
type node struct {
    key, value, freq int
    prev, next       *node
}

// doublyList is a frequency bucket holding nodes with the same access count.
type doublyList struct {
    head, tail *node
    size       int
}

func newDoublyList() *doublyList {
    head := &node{}
    tail := &node{}
    head.next = tail
    tail.prev = head
    return &doublyList{head: head, tail: tail}
}

// pushFront inserts a node at the front (most recently used position).
func (dl *doublyList) pushFront(n *node) {
    n.prev = dl.head
    n.next = dl.head.next
    dl.head.next.prev = n
    dl.head.next = n
    dl.size++
}

// remove detaches a node from the list.
func (dl *doublyList) remove(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
    n.prev = nil
    n.next = nil
    dl.size--
}

// back returns the least recently used node in this frequency bucket.
func (dl *doublyList) back() *node {
    if dl.size == 0 {
        return nil
    }
    return dl.tail.prev
}

Step 2: Defining the Cache Structure

Now we wire together the hash map, the frequency map, and the minimum frequency tracker.

// LFUCache is a fixed-capacity Least Frequently Used cache.
type LFUCache struct {
    capacity int
    minFreq  int
    nodes    map[int]*node
    freqs    map[int]*doublyList
}

// New creates an LFUCache with the given capacity.
func New(capacity int) *LFUCache {
    return &LFUCache{
        capacity: capacity,
        minFreq:  0,
        nodes:    make(map[int]*node),
        freqs:    make(map[int]*doublyList),
    }
}

Step 3: Implementing the Frequency Promotion Helper

Whenever a node is accessed, its frequency increases by one. This means removing it from its current frequency bucket and inserting it into the next one. If the old bucket becomes empty and it was the minimum frequency bucket, we bump minFreq.

// promote moves a node from its current frequency bucket to freq+1.
func (c *LFUCache) promote(n *node) {
    oldFreq := n.freq
    newFreq := oldFreq + 1

    // Remove from old bucket.
    oldList := c.freqs[oldFreq]
    oldList.remove(n)
    if oldList.size == 0 {
        delete(c.freqs, oldFreq)
        if c.minFreq == oldFreq {
            c.minFreq = newFreq
        }
    }

    // Insert into new bucket.
    n.freq = newFreq
    newList, ok := c.freqs[newFreq]
    if !ok {
        newList = newDoublyList()
        c.freqs[newFreq] = newList
    }
    newList.pushFront(n)
}

Step 4: Implementing Get

The Get operation looks up the key, promotes the node's frequency, and returns the value. If the key is missing, it returns -1.

// Get returns the value for key, or -1 if not present.
func (c *LFUCache) Get(key int) int {
    n, ok := c.nodes[key]
    if !ok {
        return -1
    }
    c.promote(n)
    return n.value
}

Step 5: Implementing Put

The Put operation has two branches. If the key already exists, we update the value and promote the node. If it is new, we evict the LFU item when at capacity, then insert the new node at frequency 1 and reset minFreq to 1.

// Put inserts or updates a key-value pair.
func (c *LFUCache) Put(key, value int) {
    if c.capacity <= 0 {
        return
    }

    // Update existing key.
    if n, ok := c.nodes[key]; ok {
        n.value = value
        c.promote(n)
        return
    }

    // Evict if at capacity.
    if len(c.nodes) >= c.capacity {
        evictList := c.freqs[c.minFreq]
        lru := evictList.back()
        evictList.remove(lru)
        delete(c.nodes, lru.key)
        if evictList.size == 0 {
            delete(c.freqs, c.minFreq)
        }
    }

    // Insert new node at frequency 1.
    n := &node{key: key, value: value, freq: 1}
    c.nodes[key] = n
    if _, ok := c.freqs[1]; !ok {
        c.freqs[1] = newDoublyList()
    }
    c.freqs[1].pushFront(n)
    c.minFreq = 1
}

Step 6: Putting It All Together

Here is the complete implementation in a single file for reference:

package lfu

type node struct {
    key, value, freq int
    prev, next       *node
}

type doublyList struct {
    head, tail *node
    size       int
}

func newDoublyList() *doublyList {
    head := &node{}
    tail := &node{}
    head.next = tail
    tail.prev = head
    return &doublyList{head: head, tail: tail}
}

func (dl *doublyList) pushFront(n *node) {
    n.prev = dl.head
    n.next = dl.head.next
    dl.head.next.prev = n
    dl.head.next = n
    dl.size++
}

func (dl *doublyList) remove(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
    n.prev = nil
    n.next = nil
    dl.size--
}

func (dl *doublyList) back() *node {
    if dl.size == 0 {
        return nil
    }
    return dl.tail.prev
}

type LFUCache struct {
    capacity int
    minFreq  int
    nodes    map[int]*node
    freqs    map[int]*doublyList
}

func New(capacity int) *LFUCache {
    return &LFUCache{
        capacity: capacity,
        nodes:    make(map[int]*node),
        freqs:    make(map[int]*doublyList),
    }
}

func (c *LFUCache) promote(n *node) {
    oldFreq := n.freq
    newFreq := oldFreq + 1

    oldList := c.freqs[oldFreq]
    oldList.remove(n)
    if oldList.size == 0 {
        delete(c.freqs, oldFreq)
        if c.minFreq == oldFreq {
            c.minFreq = newFreq
        }
    }

    n.freq = newFreq
    newList, ok := c.freqs[newFreq]
    if !ok {
        newList = newDoublyList()
        c.freqs[newFreq] = newList
    }
    newList.pushFront(n)
}

func (c *LFUCache) Get(key int) int {
    n, ok := c.nodes[key]
    if !ok {
        return -1
    }
    c.promote(n)
    return n.value
}

func (c *LFUCache) Put(key, value int) {
    if c.capacity <= 0 {
        return
    }

    if n, ok := c.nodes[key]; ok {
        n.value = value
        c.promote(n)
        return
    }

    if len(c.nodes) >= c.capacity {
        evictList := c.freqs[c.minFreq]
        lru := evictList.back()
        evictList.remove(lru)
        delete(c.nodes, lru.key)
        if evictList.size == 0 {
            delete(c.freqs, c.minFreq)
        }
    }

    n := &node{key: key, value: value, freq: 1}
    c.nodes[key] = n
    if _, ok := c.freqs[1]; !ok {
        c.freqs[1] = newDoublyList()
    }
    c.freqs[1].pushFront(n)
    c.minFreq = 1
}

Step 7: Writing a Usage Example

Let us verify the implementation with a small driver program that exercises both Get and Put, including an eviction scenario.

package main

import (
    "fmt"
    "yourmodule/lfu"
)

func main() {
    cache := lfu.New(2)

    cache.Put(1, 1)            // cache: {1=1(freq1)}
    cache.Put(2, 2)            // cache: {1=1(freq1), 2=2(freq1)}
    fmt.Println(cache.Get(1))  // returns 1, freq of key 1 becomes 2
    cache.Put(3, 3)            // evicts key 2 (lowest freq, LRU among freq1)
    fmt.Println(cache.Get(2))  // returns -1 (evicted)
    fmt.Println(cache.Get(3))  // returns 3
    fmt.Println(cache.Get(1))  // returns 1
    cache.Put(4, 4)            // evicts key 3 (freq1, LRU among freq1)
    fmt.Println(cache.Get(3))  // returns -1 (evicted)
    fmt.Println(cache.Get(4))  // returns 4
    fmt.Println(cache.Get(1))  // returns 1
}

Expected output:

1
-1
3
1
-1
4
1

Step 8: Adding Concurrency Safety

The implementation above is not safe for concurrent use. In production, wrap the cache with a sync.RWMutex or use a sharded design for higher throughput under contention.

package lfu

import "sync"

type SafeLFUCache struct {
    mu    sync.RWMutex
    inner *LFUCache
}

func NewSafe(capacity int) *SafeLFUCache {
    return &SafeLFUCache{inner: New(capacity)}
}

func (s *SafeLFUCache) Get(key int) int {
    s.mu.Lock()
    defer s.mu.Unlock()
    return s.inner.Get(key)
}

func (s *SafeLFUCache) Put(key, value int) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.inner.Put(key, value)
}

For read-heavy workloads, you might consider a copy-on-write approach or a sync.Map-style structure, but the mutex wrapper above is sufficient for most applications.

Best Practices

Generic Version (Go 1.18+)

For modern Go codebases, a generic version is more reusable. Here is the same cache adapted to type parameters:

package lfu

type gnode[K comparable, V any] struct {
    key   K
    value V
    freq  int
    prev  *gnode[K, V]
    next  *gnode[K, V]
}

type glist[K comparable, V any] struct {
    head, tail *gnode[K, V]
    size       int
}

func newGList[K comparable, V any]() *glist[K, V] {
    head := &gnode[K, V]{}
    tail := &gnode[K, V]{}
    head.next = tail
    tail.prev = head
    return &glist[K, V]{head: head, tail: tail}
}

func (l *glist[K, V]) pushFront(n *gnode[K, V]) {
    n.prev = l.head
    n.next = l.head.next
    l.head.next.prev = n
    l.head.next = n
    l.size++
}

func (l *glist[K, V]) remove(n *gnode[K, V]) {
    n.prev.next = n.next
    n.next.prev = n.prev
    n.prev = nil
    n.next = nil
    l.size--
}

func (l *glist[K, V]) back() *gnode[K, V] {
    if l.size == 0 {
        return nil
    }
    return l.tail.prev
}

type Cache[K comparable, V any] struct {
    capacity int
    minFreq  int
    nodes    map[K]*gnode[K, V]
    freqs    map[int]*glist[K, V]
}

func NewCache[K comparable, V any](capacity int) *Cache[K, V] {
    return &Cache[K, V]{
        capacity: capacity,
        nodes:    make(map[K]*gnode[K, V]),
        freqs:    make(map[int]*glist[K, V]),
    }
}

func (c *Cache[K, V]) promote(n *gnode[K, V]) {
    oldFreq := n.freq
    newFreq := oldFreq + 1

    oldList := c.freqs[oldFreq]
    oldList.remove(n)
    if oldList.size == 0 {
        delete(c.freqs, oldFreq)
        if c.minFreq == oldFreq {
            c.minFreq = newFreq
        }
    }

    n.freq = newFreq
    newList, ok := c.freqs[newFreq]
    if !ok {
        newList = newGList[K, V]()
        c.freqs[newFreq] = newList
    }
    newList.pushFront(n)
}

func (c *Cache[K, V]) Get(key K) (V, bool) {
    var zero V
    n, ok := c.nodes[key]
    if !ok {
        return zero, false
    }
    c.promote(n)
    return n.value, true
}

func (c *Cache[K, V]) Put(key K, value V) {
    if c.capacity <= 0 {
        return
    }

    if n, ok := c.nodes[key]; ok {
        n.value = value
        c.promote(n)
        return
    }

    if len(c.nodes) >= c.capacity {
        evictList := c.freqs[c.minFreq]
        lru := evictList.back()
        evictList.remove(lru)
        delete(c.nodes, lru.key)
        if evictList.size == 0 {
            delete(c.freqs, c.minFreq)
        }
    }

    n := &gnode[K, V]{key: key, value: value, freq: 1}
    c.nodes[key] = n
    if _, ok := c.freqs[1]; !ok {
        c.freqs[1] = newGList[K, V]()
    }
    c.freqs[1].pushFront(n)
    c.minFreq = 1
}

Using the generic version is straightforward:

cache := lfu.NewCache[string, []byte](1000)
cache.Put("user:42", []byte("payload"))
val, ok := cache.Get("user:42")

Complexity Analysis

Both Get and Put run in O(1) average time. Here is why each step is constant:

Space complexity is O(capacity) — each entry occupies one node plus map overhead.

Common Pitfalls

Conclusion

Implementing an LFU cache in Go is a rewarding exercise that combines hash maps, doubly linked lists, and careful state tracking into a single elegant data structure. By maintaining a frequency-to-list map and a minFreq pointer, we achieve O(1) operations for both reads and writes while correctly handling the recency tie-break that distinguishes LFU from naive frequency counting. Whether you use the concrete or generic version, remember to wrap it with synchronization for concurrent environments, add observability metrics, and consider frequency aging to prevent stale popular items from dominating the cache. With these pieces in place, you have a robust, production-ready LFU cache that can serve as the backbone for database result caching, API response memoization, or any workload where access frequency is the right eviction signal.

— Ad —

Google AdSense will appear here after approval

← Back to all articles