package module
Version: v1.0.1 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Aug 16, 2020 License: MIT Imports: 2 Imported by: 1


Lest Frequently Used (LFU) Cache

Build Status codecov Go Report Card GitHub contributors GitHub license PkgGoDev

This is an in memory implementation of a least frequently used (LFU) cache in Go with constant time complexity O(1) for Set, Set, and Cache Eviction operations. The least recently used item is evicted in the case where 2 items thems have the same least frequency.

It's based on this paper http://dhruvbird.com/lfu.pdf by some very smart people


You can use view the standard documentation on https://pkg.go.dev/github.com/NdoleStudio/lfu-cache. I wrote a beginner friendly blog post here


go get https://github.com/NdoleStudio/lfu-cache


  • To get started, import the lfu-cache package and create a cache instance. New() returns an ErrInvalidCap error if you input a capacity which is less than or equal to 0.

    import "github.com/NdoleStudio/lfu-cache"
    // creating the cache with capacity 3
    cache, err := lfucache.New(3)
    if err != nil {
        // the cap is invalid
    cache := lfucache.Cache{}
  • Inserting a value in the cache. Set() returns ErrInvalidCap if the cache capacity is less than or equal to zero. Ideally you should NEVER get this error

    err := cache.Set("key", "value")
    if err != nil {
        // the cap is invalid
  • Getting a value in from the cache. Get() returns ErrCacheMiss if there is a cache miss

    val, err := cache.Get("key")
    if err != nil {
        // cache miss
    if err == lfucache.ErrCacheMiss { 
        // cache miss
    println(val) // val is of type interface{}
    println(val.(string)) // print val as string
  • There are some helper methods like IsEmpty(), Len(), IsFull Cap()

    // creating the cache with capacity 3
    cache, _ := lfucache.New(3)
    // setting a value
    _ = cache.Set("key", "value")
    cache.IsEmpty() // returns false
    cache.Len()     // returns 1 because there is 1 item in the cache
    cache.IsFull()  // returns false because the cache is not full
    cache.Cap()     // returns 3 which is the capacity of the cache
Running Tests

To run tests, cd to the project directory and run

go test -v 


We use SemVer for versioning. For the versions available, see the tags on this repository.


See also the list of contributors who participated in this project.


This project is licensed under the MIT License - see the LICENSE.md file for details



Package lfucache an in memory least frequently used (LFU) cache. All operations have with O(1) complexity. When evicting an item from the cache, if 2 items have the same frequency the (least recently used) LRU item is evicted.

Ideally, you should provide a wrapper around this class to ensure strict type checks for keys and values that can be put into the cache.



This section is empty.


View Source
var (
	// ErrCacheMiss is the error that is returned when there is a Cache during a Get operation
	ErrCacheMiss = errors.New("cache miss")

	// ErrInvalidCap is the error returned when the cache cap is invalid
	ErrInvalidCap = errors.New("cache cap <= 0")


This section is empty.


type Cache

type Cache struct {
	// contains filtered or unexported fields

Cache is the data structure for the LFU Cache. The zero value of this cache is not ready to use because the cap is zero

func New

func New(cap int) (cache *Cache, err error)

New creates a new instance of the LFU Cache. It returns and ErrInvalidCap error if the cap <= 0.

func (*Cache) Cap

func (cache *Cache) Cap() int

Cap returns the cap fo the Cache.

func (*Cache) Get

func (cache *Cache) Get(key interface{}) (value interface{}, err error)

Get returns an item for the Cache having a key. It returns ErrCacheMiss if there's a Cache miss.

func (*Cache) IsEmpty

func (cache *Cache) IsEmpty() bool

IsEmpty determines if there are no items in the Cache.

func (*Cache) IsFull

func (cache *Cache) IsFull() bool

IsFull determines if the Cache is full.

func (*Cache) Len

func (cache *Cache) Len() int

Len returns the number of items in the Cache.

func (*Cache) Set

func (cache *Cache) Set(key interface{}, value interface{}) (err error)

Set is used to an item in the Cache with key and value. It returns ErrInvalidCap if the cache is not initialized.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL