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: 恋水无意
腾讯云开发者社区:孟斯特


热门相关:傲娇小萌妃:殿下太腹黑   穹顶之上   兵王传说   回家的诱惑之消失的她   龙组兵王