golang lru

发布时间:2024-07-07 00:03:43

LRU Cache in Golang

In computer science, an LRU (Least Recently Used) cache is a popular data structure used to store and manage frequently accessed items. It operates on the principle of discarding the least recently used items when the cache reaches its capacity, allowing for efficient memory management and optimizing data access times. In this article, we will explore how to implement an LRU cache in the Go programming language.

Understanding LRU Cache

The LRU cache is based on the idea that items that haven't been accessed in a long time are less likely to be accessed in the future. It consists of two main data structures: a hash table and a doubly linked list. The hash table allows for constant time lookup of items, while the doubly linked list keeps track of the order in which items were accessed, with the most recently used item at the front and the least recently used item at the end.

Implementing LRU Cache in Golang

To start implementing an LRU cache in Golang, we need to define a data structure that represents a cache. This structure should have a fixed capacity, a hash table to store key-value pairs, and a doubly linked list to keep track of the order of access.


type LRUCache struct {
    capacity int
    cache    map[int]*Node
    head     *Node
    tail     *Node
}

We also need to define a data structure for each node in the doubly linked list. Each node should have fields for storing the key and value, as well as pointers to the previous and next nodes in the list.


type Node struct {
    key   int
    value int
    prev  *Node
    next  *Node
}

Now that we have our data structures, we can start implementing the core operations of the LRU cache: Get and Put. The Get operation retrieves a value from the cache, while the Put operation adds a key-value pair to the cache.

Get Operation

When performing a Get operation, we first check if the key exists in the cache. If it does, we move the corresponding node to the front of the doubly linked list to indicate that it has been accessed recently. If the key doesn't exist, we return -1 to indicate that the value is not present in the cache.


func (c *LRUCache) Get(key int) int {
    if node, ok := c.cache[key]; ok {
        c.moveToFront(node)
        return node.value
    }
    return -1
}

Put Operation

When performing a Put operation, we first check if the key already exists in the cache. If it does, we update the corresponding value and move the node to the front of the list. If the key doesn't exist, we create a new node with the given key-value pair and add it to the front of the list. If the cache reaches its capacity, we remove the least recently used item from the cache.


func (c *LRUCache) Put(key int, value int) {
    if node, ok := c.cache[key]; ok {
        node.value = value
        c.moveToFront(node)
    } else {
        if len(c.cache) >= c.capacity {
            c.removeLRU()
        }
        newNode := &Node{key, value, nil, nil}
        c.cache[key] = newNode
        c.addToFront(newNode)
    }
}

In the Put operation, the moveToFront, removeLRU, and addToFront functions are responsible for updating the doubly linked list accordingly.

Conclusion

In conclusion, the LRU cache is a powerful data structure for managing frequently accessed items. By combining a hash table and a doubly linked list, we can achieve efficient memory management and optimize data access times. The Go programming language provides a convenient environment for implementing an LRU cache, as demonstrated in this article.