LRU Cache in Golang

Lately, caching has become an essential technique used in software development. It helps to improve system performance by storing frequently accessed data in memory. One popular cache implementation is the Least Recently Used (LRU) cache, which is widely used due to its efficiency. In this article, we will explore how to implement an LRU cache in Golang.

Understanding LRU Cache

Before diving into the implementation details, let's understand what an LRU cache is. LRU cache is a key-value store with a fixed capacity. Whenever a new entry is inserted into the cache, and if the cache is at full capacity, the least recently used item is evicted to make room for the new item. This eviction policy ensures that the most frequently used items are always cached, while less used items are removed to optimize space.

Implementing LRU Cache in Golang

To implement an LRU cache in Golang, we can use a combination of a doubly linked list and a hashmap. The doubly linked list helps us maintain the order of the items based on their recent usage. The hashmap provides efficient lookup of the items in the cache.

The cache will consist of the following components:

1. Doubly Linked List: Each node in the list represents a cache entry with a key-value pair and two pointers - prev and next.

2. Hashmap: The hashmap acts as a reference to the nodes of the doubly linked list for quick access and retrieval.

3. Capacity: The maximum number of entries that the cache can hold.

``` type LRUCache struct { capacity int cacheMap map[int]*Node head, tail *Node } type Node struct { key, value int prev, next *Node } ```

Cache Operations

The LRU cache implementation supports the following operations:

1. Get(key int) int

This operation retrieves a value from the cache based on the provided key. If the key exists in the cache, the operation updates the corresponding node's position to mark it as the most recently used and returns the value. Otherwise, it returns -1.

2. Put(key int, value int)

This operation inserts a key-value pair into the cache. If the key already exists, the operation updates the corresponding node's value and position in the list. If the cache has reached its capacity, the operation removes the least recently used node before inserting the new entry.

LRU Cache Implementation

Now, let's dive into the implementation of the cache operations:

1. Get(key int) int

``` func (c *LRUCache) Get(key int) int { if node, ok := c.cacheMap[key]; ok { c.updateRecentlyUsed(node) return node.value } return -1 } func (c *LRUCache) updateRecentlyUsed(node *Node) { if node != c.head { if node == c.tail { c.tail = node.prev } else { node.next.prev = node.prev } node.prev.next = node.next c.head.prev = node node.next = c.head node.prev = nil c.head = node } } ```

2. Put(key int, value int)

``` func (c *LRUCache) Put(key int, value int) { if node, ok := c.cacheMap[key]; ok { // Update existing value and move node to the head node.value = value c.updateRecentlyUsed(node) } else { newNode := &Node{key: key, value: value} c.cacheMap[key] = newNode if c.head == nil { c.head = newNode c.tail = newNode } else { newNode.next = c.head c.head.prev = newNode c.head = newNode } if len(c.cacheMap) > c.capacity { delete(c.cacheMap, c.tail.key) c.tail = c.tail.prev c.tail.next = nil } } } ```

Conclusion

In this article, we explored the implementation of an LRU cache in Golang. The LRU cache uses a combination of a doubly linked list and a hashmap to achieve efficient caching and eviction of least recently used items. This implementation can be used in various scenarios where quick access to frequently used data is required.

A well-designed caching strategy can greatly improve the performance of software systems by reducing the load on underlying data sources. It is always important to consider the specific requirements and usage patterns of your application when selecting and implementing a caching mechanism.

That's all for now! Happy coding!