前言
LRU(Least Recently Used)是一种常见的页面置换算法,在计算中,所有的文件操作都要放在内存中进行,然而计算机内存大小是固定的,所以我们不可能把所有的文件都加载到内存,因此我们需要制定一种策略对加入到内存中的文件进项选择。
常见的页面置换算法有如下几种:
LRU 最近最久未使用FIFO 先进先出置换算法 类似队列OPT 更佳置换算法 (理想中存在的)NRU Clock置换算法LFU 最少使用置换算法PBA 页面缓冲算法LRU算法
LRU原理
LRU的设计原理就是,当数据在最近一段时间经常被访问,那么它在以后也会经常被访问。这就意味着,如果经常访问的数据,我们需要让其能够快速命中,而不常访问的数据,我们在容量超出限制内,要将其淘汰。
当我们的数据按照如下顺序进行访问时,LRU的工作原理如下:
正如上面图所表示的意思:每次访问的数据都会放在栈顶,当访问的数据不在内存中,且栈内数据存储满了,我们就要选择移除栈底的元素,因为在栈底部的数据访问的频率是比较低的。所以要将其淘汰。
LRU的实现
如何来设计一款LRU算法呢?对于这种类似序列的结构我们一般可以选择链表或者是数组来构建。
差异对比:
数组: 查询比较快,但是对于增删来说是一个不是一个好的选择
链表: 查询比较慢,但是对于增删来说十分方便O(1)时间复杂度内搞定
有没有办法既能够让其搜索快,又能够快速进行增删操作。
我们可以选择链表+hash表,hash表的搜索可以达到0(1)时间复杂度,这样就完美地解决我们搜索时间慢的问题了
基于链表+Hash表Hash表,在Java中HashMap是我们的不二选择
链表,Node一个双向链表的实现,Node中存放的是数结构如下:
class Node<K,V>{ private K key; private V value; private Node<K,V> prev; private Node<K,V> next; }
我们通过HashMap中key存储Node的key,value存储Node来建立Map对Node的映射关系。我们将HashMap看作是一张检索表,我们可以可以快速地检索到我们需要定位的Node
LRU的实现
构建双向链表节点ListNode,应包含key,value,prev,next这几个基本属性对于Cache对象来说,我们需要规定缓存的容量,所以在初始化时,设置容量大小,然后实例化双向链表的head,tail,并让head.next->tail tail.prev->head,这样我们的双向链表构建完成对于get操作,我们首先查阅hashmap,如果存在的话,直接将Node从当前位置移除,然后插入到链表的首部,在链表中实现删除直接让node的前驱节点指向后继节点,很方便.如果不存在,那么直接返回Null对于put操作,比较麻烦。大体代码如下:
package code.fragment; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; public class LRUCache<V> { /** * 容量 */ private int capacity = 1024; /** * Node记录表 */ private Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>(); /** * 双向链表头部 */ private ListNode<String, V> head; /** * 双向链表尾部 */ private ListNode<String, V> tail; public LRUCache(int capacity) { this(); this.capacity = capacity; } public LRUCache() { head = new ListNode<>(); tail = new ListNode<>(); head.next = tail; head.prev = null; tail.prev = head; tail.next = null; } public V get(String key) { ListNode<String, V> node = table.get(key); //如果Node不在表中,代表缓存中并没有 if (node == null) { return null; } //如果存在,则需要移动Node节点到表头 //截断链表,node.prev -> node -> node.next ====> node.prev -> node.next // node.prev <- node <- node.next ====> node.prev <- node.next node.prev.next = node.next; node.next.prev = node.prev; //移动节点到表头 node.next = head.next; head.next.prev = node; node.prev = head; head.next = node; //存在缓存表 table.put(key, node); return node.value; } public void put(String key, V value) { ListNode<String, V> node = table.get(key); //如果Node不在表中,代表缓存中并没有 if (node == null) { if (table.size() == capacity) { //超过容量了 ,首先移除尾部的节点 table.remove(tail.prev.key); tail.prev = tail.next; tail.next = null; tail = tail.prev; } node = new ListNode<>(); node.key = key; node.value = value; table.put(key, node); } //如果存在,则需要移动Node节点到表头 node.next = head.next; head.next.prev = node; node.prev = head; head.next = node; } /** * 双向链表内部类 */ public static class ListNode<K, V> { private K key; private V value; ListNode<K, V> prev; ListNode<K, V> next; public ListNode(K key, V value) { this.key = key; this.value = value; } public ListNode() { } } public static void main(String[] args) { LRUCache<ListNode> cache = new LRUCache<>(4); ListNode<String, Integer> node1 = new ListNode<>("key1", 1); ListNode<String, Integer> node2 = new ListNode<>("key2", 2); ListNode<String, Integer> node3 = new ListNode<>("key3", 3); ListNode<String, Integer> node4 = new ListNode<>("key4", 4); ListNode<String, Integer> node5 = new ListNode<>("key5", 5); cache.put("key1", node1); cache.put("key2", node2); cache.put("key3", node3); cache.put("key4", node4); cache.get("key2"); cache.put("key5", node5); cache.get("key2"); } }
原文链接:https://blog.csdn.net/qq_26440803/article/details/83795122
LInkedHashMap值得一提的是,Java API中其实已经有数据类型提供了我们需要的功能,就是LinkedHashMap这个类。该类内部也是采用HashMap+双向链表实现的。LinkedHashMap提供了按照访问顺序排序的方案,内部也是使用HashMap+双向链表。 v只需要重写removeEldestEntry *** ,当该 *** 返回true时,LinkedHashMap会删除最旧的结点。
既只需要覆写LinkedHashMap的removeEldestEntry *** ,在缓存已满的情况下返回true,内部就会自动删除最老的元素
import java.util.LinkedHashMap; import java.util.Map; /** * 简单用LinkedHashMap来实现的LRU算法的缓存 */ public class LRUCache<K, V> extends LinkedHashMap<K, V> { private int cacheSize; public LRUCache(int cacheSize) { super(16, (float) 0.75, true); this.cacheSize = cacheSize; } protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > cacheSize; } }
import org.slf4j.Logger; import org.slf4j.LoggerFactory; public class LRUCacheTest { private static final Logger log = LoggerFactory.getLogger(LRUCacheTest.class); private static LRUCache<String, Integer> cache = new LRUCache<>(10); public static void main(String[] args) { for (int i = 0; i < 10; i++) { cache.put("k" + i, i); } log.info("all cache :'{}'",cache); cache.get("k3"); log.info("get k3 :'{}'", cache); cache.get("k4"); log.info("get k4 :'{}'", cache); cache.get("k4"); log.info("get k4 :'{}'", cache); cache.put("k" + 10, 10); log.info("After running the LRU algorithm cache :'{}'", cache); } }
FIFO算法
FIFO 算法是一种比较容易实现的算法。它的思想是先进先出(FIFO,队列),这是最简单、最公平的一种思想,即如果一个数据是更先进入的,那么可以认为在将来它被访问的可能性很小。空间满的时候,更先进入的数据会被最早置换(淘汰)掉。
FIFO 算法的描述:设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:
set(key,value):将记录(key,value)插入该结构。当缓存满时,将更先进入缓存的数据置换掉。get(key):返回key对应的value值。实现:维护一个FIFO队列,按照时间顺序将各数据(已分配页面)链接起来组成队列,并将置换指针指向队列的队列。再进行置换时,只需把置换指针所指的数据(页面)顺次换出,并把新加入的数据插到队尾即可。
缺点:判断一个页面置换算法优劣的指标就是缺页率,而FIFO算法的一个显著的缺点是,在某些特定的时刻,缺页率反而会随着分配页面的增加而增加,这称为Belady现象。产生Belady现象现象的原因是,FIFO置换算法与进程访问内存的动态特征是不相容的,被置换的内存页面往往是被频繁访问的,或者没有给进程分配足够的页面,因此FIFO算***使一些页面频繁地被替换和重新申请内存,从而导致缺页率增加。因此,现在不再使用FIFO算法。