lru算法及例题讲解 lru算法？

lru算法？

LRU算法的设计原则是：如果一个数据最近一段时间没有被访问过，那么它在将来就不太可能被访问。换言之，当有限的空间充满数据时，应该消除最长时间未被访问的数据。

执行LRU

1。使用数组存储数据，用访问时间戳标记每个数据项。插入新数据项时，首先增加数组中现有数据项的时间戳，将新数据项的时间戳设置为0，然后将其插入数组中。每次访问数组中的数据项时，所访问数据项的时间戳都设置为0。当数组空间已满时，时间戳最大的数据项将被删除。

2. 使用链表实现，每次插入新数据时，将新数据插入链表的头部；每次缓存命中时，将数据移动到链表的头部（即访问数据）；然后在链表已满时丢弃链表末尾的数据。

3. 使用链表和HashMap。当需要插入新数据项时，如果新数据项存在于链表中（通常称为hit），请将节点移动到链表的头部。如果不存在，则创建一个新节点并将其放在链表的头部。如果缓存已满，请删除链表的最后一个节点。在访问数据时，如果链表中存在该数据项，则节点会移到链表的头，否则返回-1。这样，链表末尾的节点就是最近不可访问的数据项。

对于第一种方法，需要连续维护数据项的访问时间戳。另外，在插入数据、删除数据和访问数据时，时间复杂度为O（n）。对于第二种方法，链表的时间复杂度为O（n）。所以一般来说，第三种方法是实现LRU算法。

lru算法及例题讲解 堆栈型替换算法 lru算法图解

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。