简单明了的方式学Lru算法

小灰灰 2023-07-10 12:39 4阅读 0赞

## 一. 简介 ##

Lru全拼Least Recently Used（字面意思最少、最近使用），即最近最久使用算法，是一种常用的置换算法。

**通俗解释：**  
简单点说，就是把**最近未使用的**予以淘汰。

## 二. 举例说明 ##

**举个例子：**  
定义一个容器只能存储3个对象

**第一次**：依次添加对象A、B、C ==> \[A, B, C\]  
**第二次**：添加对象D ==> \[B, C, D\]  
此时把第一次添加的A对象给淘汰了  
如果此时再添加一个对象，肯定是要淘汰B了

但是把B对象给使用一次，就会把B对象的优先级位置拉到最前面  
**第三次**：使用对象B ==> \[C, D, B\]  
**第四次**：添加对象E ==> \[D, B, E\]

## 三. 代码示例 ##

结合小例子，应该很快就明白该算法的操作顺序原理了，通过LinkedList编写了一段代码来实现，仅供参考

import java.util.LinkedList;
    
    /** * @author yanghao * @version LruTest.java, v 0.1 2020-01-14 15:15 */
    public class LruTest { 
    
        static MyStorage<String> storage = new MyStorage<>();
    
        static class MyStorage<T>{ 
    
            private LinkedList<T> list = new LinkedList<>();
    
            public boolean add(T t){ 
                if(list.size() > 2){ 
                    list.removeFirst();
                }
    
                return list.add(t);
            }
    
            public T use(int index){ 
                T t = list.get(index);
    
                list.remove(index);
                list.add(t);
    
                return t;
            }
    
            public T get(int index){ 
                return list.get(index);
            }
    
        }
    
        public static void main(String[] args){ 
            storage.add("A");
            storage.add("B");
            storage.add("C");
            System.out.println(storage.get(0) + storage.get(1) + storage.get(2));
    
            storage.add("D");
            System.out.println(storage.get(0) + storage.get(1) + storage.get(2));
    
            storage.use(0);
            System.out.println(storage.get(0) + storage.get(1) + storage.get(2));
    
            storage.add("E");
            System.out.println(storage.get(0) + storage.get(1) + storage.get(2));
    
        }
    }

**运行结果如下：**

ABC
    BCD
    CDB
    DBE