使用JAVA实现LRU算法

飞熊 • 2024年1月29日下午10:33 • 技术随笔 • 阅读 226

原理

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

通俗的来讲，就是淘汰使用时间最长的

代码

//使用双向链表+HashMap来实现 -- LRU算法
public class LRUTest {

    //========================链表节点===========================
    class Node{
        Node pre;
        Node next;
        int key,value;
        public Node(int a,int b){
            this.key = a;
            this.value = b;
        }
    }


    //====================链表成员变量======================
    Node head;
    Node tail;

    //默认最大长度为 2
    int maxSize;
    int currentCacheSize;

    HashMap<Integer,Node> map;


    //=====================构造方法===========================

    public LRUTest(int capacity) {
        currentCacheSize = 0;
        this.maxSize = capacity;
        map = new HashMap<>();
    }


    //======================具体的函数实现===========================
    public int get(int index){
        if(!map.containsKey(index)){
            return -1;
        }
        //使用了当前节点还需要把当前节点移到链表头
        transToHead(map.get(index));
        return map.get(index).value;
    }


    public void put(int a,int b){
        Node node = map.get(a);
        if (node == null){
            map.put(a,new Node(a, b));
        }
    }

    //移除map中的
    public Object remove(int k){
        Node node = map.get(k);
        if(node != null){
            if(node.pre != null){
                node.pre.next=node.next;
            }
            if(node.next != null){
                node.next.pre=node.pre;
            }
            if(node == head){
                head = node.next;
            }
            if(node == tail){
                tail = node.pre;
            }
        }

        return map.remove(k);
    }


    public void transToHead(Node node){
        //考虑三种情况： 链表头，链表尾，链表中
        if (node == head){
            return;
        }
        if(node.next != null){
            node.next.pre = node.pre;
        }
        if(node.pre != null){
            node.pre.next = node.next;
        }
        if(node == tail){
            tail = tail.pre;
        }
        //改变头结点为node
        node.next = head;
        head.pre = node;
        head = node;
        head.pre = null;
    }

    public void removeLast(){
        if (tail != null){
            tail = tail.pre;
            //如果尾节点为null
            if(tail == null){
                head = null;
            }else {
                tail.next = null;
            }
        }
    }
}