LRU算法简介

原创

孟斯特

发布于 2024-01-28 15:34:07

5250

发布于 2024-01-28 15:34:07

文章被收录于专栏：code人生

LRU（Least Recently Used）算法是一种缓存淘汰算法，常用于缓存系统中，通过保留最近使用的数据而淘汰最久未使用的数据，以提高缓存的命中率。LRU算法的核心思想是基于时间局部性原理：最近访问的数据在未来会被再次访问。

基本原理

LRU算法的基本原理如下：

维护使用顺序：LRU算法通过维护一个使用顺序链表（通常是双向链表），链表中的节点按照数据的访问顺序排列。最近被访问的数据节点被移动到链表的头部，而最久未被使用的数据节点位于链表的尾部。
数据访问时的操作：
1. 当某个数据被访问时，如果数据已经在缓存中，将其从链表中移到头部，表示最近使用。
2. 如果数据不在缓存中，将其添加到链表头部，并在缓存中进行相应的存储。如果缓存已满，需要淘汰链表尾部的数据节点，即淘汰最久未使用的数据。
淘汰数据的操作：
1. 当需要淘汰数据时，选择链表尾部的节点，即最久未使用的数据，进行淘汰。
2. 淘汰操作包括在链表和缓存中删除相应的节点。

数据结构：

LRU算法通常使用两个数据结构来实现：

双向链表：用于存储缓存中的数据，按照访问顺序排列。每次访问数据时，将该数据移到链表头部表示最近使用，而最近未使用的数据则位于链表尾部。
哈希表：用于快速查找缓存中是否存在某个数据，以及定位该数据在双向链表中的位置。哈希表的键是数据的键，值是指向双向链表节点的指针。

算法操作：

LRU算法主要包含以下几个操作：

获取数据（Get）：
- 当需要获取某个数据时，首先在哈希表中查找。
- 如果数据存在，将其从双向链表中移动到链表头部，表示最近使用。
- 如果数据不存在，返回缓存未命中的标志。
插入数据（Put）：
- 当需要插入新数据时，首先在哈希表中查找。
- 如果数据已经存在，更新数据的值，并将其从双向链表中移动到链表头部。
- 如果数据不存在，插入新数据到双向链表的头部，并在哈希表中添加对应的映射。
- 如果插入后缓存容量超过限制，则从双向链表尾部移除最久未使用的数据，并在哈希表中删除对应的映射。

时间复杂度和空间复杂度：

LRU算法的时间复杂度和空间复杂度主要取决于哈希表和双向链表的操作。

时间复杂度：
- Get操作和Put操作的时间复杂度都是O(1)，因为哈希表的查找和修改操作都是常数时间复杂度。
- 在双向链表中插入、删除和移动节点的操作也是O(1)。
空间复杂度：
- 空间复杂度主要由哈希表和双向链表的大小决定。哈希表的空间复杂度为O(n)，其中n是缓存中的数据量。双向链表的空间复杂度也是O(n)。

示例实现：

下面是一个简单的LRU算法的示例实现，使用Golang语言：

package main

import "fmt"

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

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

func Constructor(capacity int) LRUCache {
    head := &DoublyListNode{}
    tail := &DoublyListNode{}
    head.next = tail
    tail.prev = head
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*DoublyListNode),
        head:     head,
        tail:     tail,
    }
}

func (lru *LRUCache) moveToHead(node *DoublyListNode) {
    lru.removeNode(node)
    lru.addToHead(node)
}

func (lru *LRUCache) removeNode(node *DoublyListNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (lru *LRUCache) addToHead(node *DoublyListNode) {
    node.next = lru.head.next
    node.prev = lru.head
    lru.head.next.prev = node
    lru.head.next = node
}

func (lru *LRUCache) removeTail() {
    tail := lru.tail.prev
    lru.removeNode(tail)
    delete(lru.cache, tail.key)
}

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

func (lru *LRUCache) Put(key int, value int) {
    if node, ok := lru.cache[key]; ok {
        node.value = value
        lru.moveToHead(node)
    } else {
        newNode := &DoublyListNode{key: key, value: value}
        lru.cache[key] = newNode
        lru.addToHead(newNode)
        if len(lru.cache) > lru.capacity {
            lru.removeTail()
        }
    }
}

func main() {
    lruCache := Constructor(2)
    lruCache.Put(1, 1)
    lruCache.Put(2, 2)
    fmt.Println(lruCache.Get(1)) // 输出 1
    lruCache.Put(3, 3)            // 该操作会使得密钥 2 作废
    fmt.Println(lruCache.Get(2)) // 输出 -1（未找到）
    lruCache.Put(4, 4)            // 该操作会使得密钥 1 作废
    fmt.Println(lruCache.Get(1)) // 输出 -1（未找到）
    fmt.Println(lruCache.Get(3)) // 输出 3
    fmt.Println(lruCache.Get(4)) // 输出 4
}

在这个示例中，LRUCache结构体包含了哈希表和双向链表。DoublyListNode结构体表示双向链表的节点。通过moveToHead、removeNode、addToHead、removeTail等方法实现了对双向链表的操作。Get方法用于获取缓存中的值，Put方法用于插入新值或更新已有值，并在需要时淘汰最久未使用的数据。

我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！