扫一扫下方二维码,关注本站官方公众号
获取永久解锁本站全部文章的验证码
还能不定期领现金红包

LRU缓存机制的哈希表+双向链表Go实现-Go语言中文社区

LRU缓存机制的哈希表+双向链表Go实现


LRU(Least Recently Used,最近使用最少,最久未使用)是一种缓存淘汰算法。缓存是计算机中用来提高访问资源速度的一种方法。将从数据库、硬盘、网络或其他地方读取到的数据暂存于方便读取的地方(也就是缓存(Cache)),等再次读取时就不必重新在上述地方查找和读取一遍。通常来说,缓存的空间都是有限的,因此只应该保留经常会被读取的数据,而不常被读取的数据则该被淘汰。

LRU是众多缓存淘汰算法中的一种,在缓存容量满了时,淘汰最久没有被访问的元素。他的算法设计很简单。首先是数据结构设计。对于每个缓存中元素,可以用键值对的方式存储,读取时通过键读取对应的数据。缓存是一个优先队列,元素的优先级在运行中会不断改变。每次访问一个键,该键对应元素优先级设为最低(也就是最近访问)。每次插入一个新元素,如果键已存在,则更新其值,并设为最近使用。如果键不存在,则检查容量满了没有。如果满了,则将缓存中优先级最高的元素,也就是最久未访问的元素删除。然后再新增元素,并设为最近访问。

这个是我的伪代码,凑合着看吧

元素 键:值
缓存容量 N
缓存 [缓存元素0,缓存元素1,。。。,缓存元素N]

访问键为x的元素:

    如果x在缓存中,则将x对应的元素的值返回,并将该元素设为最近访问
    如果不在,则返回空

新增键为y,值为z的元素:
    
    如果缓存中已经存在键为y的元素
        则更新其值为z,并设为最近访问
    如果缓存中不存在键为y的元素
        检查缓存中元素数量是否达容量
            如果是则删除最久未访问的元素
        新增键为y,值为z的元素到缓存中,并将该元素设为最近访问

具体如何实现这个优先队列,一种简单的实现是,让每个缓存的元素维护一个时间变量。如果元素被访问或是新增,则元素时间置0,其余元素时间+1。当缓存满了需要淘汰内存,则将时间值最大的元素删除。这种设计很明显,时间复杂度很高,每次插入和读取都要更新所有元素的时间,淘汰时,也必须遍历找出时间最大的元素。

更高效的做法是,使用哈希表和双向链表实现。哈希表的特点是查找时间复杂度大部分时候为O(1),但是不存在优先级,甚至不存在先后顺序。而双向链表的特点是,在头尾新增和删除高效,但是查找效率低。

所以,可以设置这样的一个缓存结构。一个哈希表用于储存键和对应元素的地址,用于快速访问和判断元素是否存在。双向链表中,每个节点存储一个元素的键值对。当某个元素被制为最优先,则将对应节点置于链表首。当缓存容量满了,则抛弃链表末尾的节点,并同时将哈希表中的键删除。

为了方便操作,链表采用的双向链表,目的是方便删除。双向链表中的头尾节点是不含有用数据的哑节点。双向链表中节点也要存值的原因是,在抛弃元素时。哈希表可从被抛弃的元素中,很方便地获取对应键。

下面是我的代码

对于双向链表数据结构,我实现了这几个操作,方便被缓存调用。

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

// 双向链表
type LRUDoubleList struct {
    head, tail *LRUDoubleListNode
}

// 构造一个初始双向链表
func NewLRUDoubleList() LRUDoubleList {
    l := LRUDoubleList{}
    l.head = &LRUDoubleListNode{}
    l.tail = &LRUDoubleListNode{}
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

// 将节点添加到链表首
func (l *LRUDoubleList) addToHead(node *LRUDoubleListNode) {
    headNext := l.head.next
    l.head.next = node
    headNext.prev = node
    node.next = headNext
    node.prev = l.head
}

// 移除节点
func (l *LRUDoubleList) remove(node *LRUDoubleListNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// 移除链表尾节点
func (l *LRUDoubleList) removeFromTail() *LRUDoubleListNode {
    if l.head.next == l.tail {
        return nil
    }
    node := l.tail.prev
    l.remove(node)
    return node
}

对于缓存结构,则实现了这些操作

// 缓存结构
type LRUCache struct {
    capacity  int
    keymap    map[int]*LRUDoubleListNode
    cache LRUDoubleList
}

// 构造一个缓存
func NewLRUCache(capacity int) LRUCache {
    lru := LRUCache{capacity: capacity}
    lru.keymap = make(map[int]*LRUDoubleListNode)
    lru.cache = NewLRUDoubleList()
    return lru
}

// 设某个键为最近访问
func (lru *LRUCache) setMostRecently(key int) {
    node := lru.keymap[key]
    lru.cache.remove(node)
    lru.cache.addToHead(node)
}

// 新增元素
func (lru *LRUCache) addItem(key, Value int) {
    node := &LRUDoubleListNode{key: key, value: Value}
    lru.keymap[key] = node
    lru.cache.addToHead(node)
}

// 移除元素
func (lru *LRUCache) removeItem(key int) {
    node := lru.keymap[key]
    lru.cache.remove(node)
    delete(lru.keymap, key)
}

// 移除最久未访问元素
func (lru *LRUCache) removeLeastRecently() {
    node := lru.cache.removeFromTail()
    delete(lru.keymap, node.key)
}

// 读取操作
func (lru *LRUCache) Get(key int) int {
    if item, ok := lru.keymap[key]; ok {
        lru.setMostRecently(item.key)
        return item.value
    } else {
        return -1
    }

}

// 新增操作
func (lru *LRUCache) Put(key int, value int) {
    if item, ok := lru.keymap[key]; ok {
        item.value = value
        lru.setMostRecently(item.key)
    } else {
        if len(lru.keymap) >= lru.capacity {
            lru.removeLeastRecently()
        }
        lru.addItem(key, value)
    }
}
版权声明:本文来源Segmentfault,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://segmentfault.com/a/1190000040130515?utm_source=tag-newest
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2021-06-12 12:49
  • 阅读 ( 686 )
  • 分类:Go

0 条评论

请先 登录 后评论

官方社群