golang lru implementation

LRU (Least Recently Used) algorithm is a common cache replacement strategy. When the cache reaches the preset limit, the cache will automatically eliminate the least recently used data to free up space.

In Golang, we can use doubly linked lists and hash tables to implement LRU cache. In this article, we describe how to implement an LRU cache using these two data structures.

The function of the doubly linked list is to maintain the cached data order. Every time new data is inserted or data is accessed, the data will be advanced. At the same time, when the cache reaches the upper limit, we can delete the least recently used data from the end of the linked list.

The function of the hash table is to speed up data search. Every time data is accessed, through the data index stored in the hash table, we can quickly find the corresponding cached data. Therefore, we will operate on hash tables during implementation.

Next, we will explain how to implement LRU cache based on doubly linked lists and hash tables. We define a LRUCache structure and declare the head and tail pointers of the linked list, as well as the hash table map and cache capacity.

type LRUCache struct {
    head, tail *entry  // 链表头和链表尾指针
    cache      map[int]*entry  // 哈希表存储缓存中的数据
    capacity   int     // 缓存容量
}

Next, we will define the structure of the doubly linked list node.

type entry struct {
    key, value int        // 存储节点的键值对
    prev, next *entry    // 前驱和后继指针
}

Here, we use prev and next to represent the predecessor and successor pointers of the node respectively, and key and value represent the key-value pair of the node respectively.

Next, we will define the constructor NewLRUCache of LRUCache and pass in the cache capacity capacity.

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

In the constructor, we will initialize the hash table and cache capacity.

Next, we will define the Get and Put methods of LRUCache to access and store data.

Implementation of Get method:

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

First, we find whether the corresponding data exists from the hash table. If it exists, move the node to the head of the linked list and return the node storage value. Otherwise, -1 is returned.

The following is the implementation of the moveToHead method:

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

This method receives a node pointer elem, which is used to move the node to the head of the linked list. First, if the node is already at the head of the linked list, return; otherwise, if the node is at the tail of the linked list, update the tail pointer of the linked list; otherwise, delete the node from the linked list and put the node at the head of the linked list.

Implementation of the Put method:

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

First, we find whether the corresponding data exists from the hash table. If it exists, update the value stored in the node and call the moveToHead method to move the node Move to the head of the linked list. Otherwise, create a new node and insert it at the head of the linked list. If the cache reaches the preset upper limit, the tail node of the linked list and the data in the hash table are deleted.

Finally, we put the complete code together:

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

type entry struct {
    key, value int
    prev, next *entry
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

In this article, we have introduced how to use doubly linked lists and hash tables to implement the LRU cache algorithm. Through the implementation of this algorithm, we can effectively manage cache and optimize data access efficiency.

The above is the detailed content of golang lru implementation. For more information, please follow other related articles on the PHP Chinese website!