LRU Cache: An Introduction and Implementation in Go

LRUCache: An implementation in Go

Introduction: An LRUCache is a data structure that uses the scheme of evicting the Least Recently Used item. Basically a cache is a mechanism used by software to effectively handle data access and reading in an efficient manner. Caching improves performances by recently used or frequently used in memory. Using a cache, we avoid the overhead required to fetch an item that is already in memory. LRU (Least Recently Used) is one cache mechanism where we evict an item that is not used to make rooms for new items to be added. Some other popular caching mechanisms are MRU, LFU, etc.

Access: O(1)

Get: O(1)

Space Complexity: O(N)

Use Cases: An LRUCache is the default implementation used by the Android and iOS client for Dropbox and the Linux Client uses something called segmented LRU.

Implementation: An LRU Cache is often implemented by using two data structures, hence the space complexity. The popular ones are using a Doubly Linked list and a HashMap.

Here is an implementation in Go.