FIFO(First In, First Out,即先进先出)是一种简单且直观的缓存替换算法。它的工作原理是,当缓存满了需要替换时,优先移除最早进入缓存的项。FIFO算法类似于排队系统,最早进入的缓存项最先被移除。
package fifo
import (
"container/list"
"sync"
)
type FIFOCache struct {
mtx sync.Mutex
capacity int
queue *list.List
cache map[any]*list.Element
}
func NewFIFOCache(capacity int) *FIFOCache {
return &FIFOCache{
capacity: capacity,
queue: list.New(),
cache: make(map[any]*list.Element),
}
}
// Get returns the item from the cache.
func (c *FIFOCache) Get(item any) any {
c.mtx.Lock()
defer c.mtx.Unlock()
if node, exists := c.cache[item]; exists {
return node.Value
}
return nil
}
// Put adds the given item to the cache.
func (c *FIFOCache) Put(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 elem, found := c.cache[item]; found {
c.queue.MoveToBack(elem)
return
}
// if the cache is full, remove the front element in queue
if c.queue.Len() == c.capacity {
c.evict()
}
// add the new item to the back of the list
node := c.queue.PushBack(item)
c.cache[item] = node
}
// evict removes the oldest entry from the cache
func (c *FIFOCache) evict() {
elem := c.queue.Front()
if elem != nil {
c.queue.Remove(elem)
delete(c.cache, elem.Value)
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。