LRU算法简介

LRU（Least Recently Used，最近最少使用）算法是一种常用于缓存管理的算法，用于在缓存空间有限的情况下，决定哪些数据应该被移除。它的基本思想是：如果一个数据最近被访问过，那么在将来一段时间内它被再次访问的概率较高。因此，当缓存已满，需要移除数据时，优先移除那些最近最少被使用的数据。

LRU算法的基本概念

1. 缓存命中（Cache Hit）：当访问的数据已经在缓存中时，称为缓存命中。
2. 缓存未命中（Cache Miss）：当访问的数据不在缓存中，需要从外部存储加载数据时，称为缓存未命中。
3. 缓存替换（Cache Replacement）：当缓存已满，需要替换掉某些数据以腾出空间时，称为缓存替换。

LRU算法的实现

LRU算法的实现通常需要两个数据结构：

1. 哈希表（Hash Table）：用于快速访问缓存中的数据。
2. 双向链表（Doubly Linked List）：用于维护数据的使用顺序，链表头部是最近使用的数据，尾部是最久未使用的数据。

LRU缓存的操作

1. 访问数据：
   • 如果数据在缓存中（缓存命中），将其移动到链表头部。
   • 如果数据不在缓存中（缓存未命中），将数据插入到链表头部。
     • 如果缓存已满，移除链表尾部的数据，以腾出空间。
2. 插入数据：
   • 将数据插入到链表头部。
   • 更新哈希表，使其指向新节点。
   • 如果缓存已满，移除链表尾部的数据，并在哈希表中删除相应的项。

Go示例

package lru

import (
	"container/list"
	"sync"
)

type LRUCache struct {
	mtx      sync.Mutex            // protects the cache
	capacity int                   // capacity of the cache
	cache    map[any]*list.Element // nearly O(1) lookups
	list     *list.List            // O(1) insert, update, delete
}

// NewLRUCache creates a new LRU cache with the given capacity.
func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		cache:    make(map[any]*list.Element),
		list:     list.New(),
	}
}

// Contains checks if the given item is in the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Contains(item any) bool {
	c.mtx.Lock()
	defer c.mtx.Unlock()

	node, exists := c.cache[item]
	if exists {
		c.list.MoveToFront(node)
	}
	return exists
}

// Get returns the item from the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Get(item any) any {
	node, exists := c.cache[item]
	if exists {
		c.mtx.Lock()
		c.list.MoveToFront(node)
		c.mtx.Unlock()
		return node.Value
	} else {
		c.Add(item)
		return item
	}
}

// Add adds the given item to the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Add(item any) {
	c.mtx.Lock()
	defer c.mtx.Unlock()

	// if capacity is 0, nothing can be added, so just return
	if c.capacity == 0 {
		return
	}

	// check if the item is already in the cache
	if node, exists := c.cache[item]; exists {
		c.list.MoveToFront(node)
		return
	}

	// if the cache is full, remove the last element
	if c.list.Len() == c.capacity {
		last := c.list.Back()
		c.list.Remove(last)
		delete(c.cache, last.Value)
	}

	// add the new item to the front of the list
	node := c.list.PushFront(item)
	c.cache[item] = node
}

// Delete removes the given item from the cache if exists.
// This function is safe for concurrent access.
func (c *LRUCache) Delete(item any) {
	c.mtx.Lock()
	defer c.mtx.Unlock()

	// check if the item is already in the cache
	if node, exists := c.cache[item]; exists {
		c.list.Remove(node)
		delete(c.cache, item)
	}
}

// Len returns the number of items in the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Len() int {
	c.mtx.Lock()
	defer c.mtx.Unlock()

	return c.list.Len()
}

声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意
腾讯云开发者社区：孟斯特