前言

LRU（Least Recently Used）是一种常见的页面置换算法，在计算中，所有的文件操作都要放在内存中进行，然而计算机内存大小是固定的，所以我们不可能把所有的文件都加载到内存，因此我们需要制定一种策略对加入到内存中的文件进项选择。

常见的页面置换算法有如下几种：

1. LRU 最近最久未使用
2. FIFO 先进先出置换算法 类似队列
3. OPT 最佳置换算法 （理想中存在的）
4. NRU Clock置换算法
5. LFU 最少使用置换算法
6. PBA 页面缓冲算法

LRU算法

LRU原理

LRU的设计原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要让其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

当我们的数据按照如下顺序进行访问时，LRU的工作原理如下：

正如上面图所表示的意思：每次访问的数据都会放在栈顶，当访问的数据不在内存中，且栈内数据存储满了，我们就要选择移除栈底的元素，因为在栈底部的数据访问的频率是比较低的。所以要将其淘汰。

LRU的实现

如何来设计一款LRU算法呢？对于这种类似序列的结构我们一般可以选择链表或者是数组来构建。

差异对比：

数组: 查询比较快，但是对于增删来说是一个不是一个好的选择

链表: 查询比较慢，但是对于增删来说十分方便O(1)时间复杂度内搞定

有没有办法既能够让其搜索快，又能够快速进行增删操作。

我们可以选择链表+hash表，hash表的搜索可以达到0(1)时间复杂度，这样就完美地解决我们搜索时间慢的问题了

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的实现

1. 构建双向链表节点ListNode，应包含key,value,prev,next这几个基本属性
2. 对于Cache对象来说，我们需要规定缓存的容量，所以在初始化时，设置容量大小，然后实例化双向链表的head,tail，并让head.next->tail tail.prev->head，这样我们的双向链表构建完成
3. 对于get操作,我们首先查阅hashmap，如果存在的话，直接将Node从当前位置移除，然后插入到链表的首部，在链表中实现删除直接让node的前驱节点指向后继节点，很方便.如果不存在，那么直接返回Null
4. 对于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

2. 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，并有两个功能：

1. set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最先进入缓存的数据置换掉。
2. get(key)：返回key对应的value值。

实现：维护一个FIFO队列，按照时间顺序将各数据（已分配页面）链接起来组成队列，并将置换指针指向队列的队列。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。

缺点：判断一个页面置换算法优劣的指标就是缺页率，而FIFO算法的一个显著的缺点是，在某些特定的时刻，缺页率反而会随着分配页面的增加而增加，这称为Belady现象。产生Belady现象现象的原因是，FIFO置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问的，或者没有给进程分配足够的页面，因此FIFO算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加。因此，现在不再使用FIFO算法。