投稿
  1. 首页
  2. 随笔

Java 实现缓存淘汰算法LRU（Least Recently Used) 三种实现（数组、链表、链表+HashMap）几乎原生实现 详细代码和注释

钢结构图集 • 2022-10-21 • 随笔 • 阅读 2

Java 实现缓存淘汰算法LRU（Least Recently Used) 三种实现（数组、链表、链表+HashMap）几乎原生实现 详细代码和注释,第1张

Java 实现缓存淘汰算法LRU（Least Recently Used) 三种实现（数组、链表、链表+HashMap）几乎原生实现 详细代码和注释

文章目录
  • 原理
  • 数组实现LRU
  • 链表实现LRU
  • 链表 + HashMap实现LRU

原理

LRU（Least Recently Used) ：指最近最少使用，也可以理解为插入数据比较早，但一直没有使用该数据

三种实现方式：

  1. 数组，每个节点额外都记录着插入和使用时间（以1970年到现在的毫秒计算），那么时间最小的就是最近最少使用的，即插入数据比较早，但一直没有使用的
  2. 链表，插入数据时往链表头插入数据节点，则链表尾就是最开始插入的数据节点，获取数据时先遍历链表找到数据节点，将其移到链表头，表示最近使用过
  3. 链表+HashMap，插入数据时除了往链表头插入数据节点，还要往HashMap中插入，获取数据时就无须遍历链表，直接从HashMap获取该节点，然后将其移到链表头
数组实现LRU 
class Node {
	// 数据节点的键
    public int key;
    // 数据节点的值
    public int value;
    // 数据节点插入或查询的时间
    public long timeStamp;

    public Node(int key, int value, long timeStamp) {
        this.key = key;
        this.value = value;
        this.timeStamp = timeStamp;
    }
}

public class ArrayImplLRU {
    // 数据节点数组
    public Node[] list = new Node[10];
    // 数组中有效节点个数
    public int size = 0;

    public void add(int key, int value) {
    	// 如果数组未满，不需要淘汰数据
        if (size < 10) {
            list[size] = new Node(key, value, System.currentTimeMillis());
            size++;
        } else {
            int index = 0;
            long min = list[0].timeStamp;
            // 遍历数组，获取timeStamp最小的节点的下标
            for (int i = 1; i < list.length; i++) {
                if (min > list[i].timeStamp) {
                    min = list[i].timeStamp;
                    index = i;
                }
            }
            // 淘汰找到的节点
            list[index] = new Node(key, value, System.currentTimeMillis());
        }
    }

    public int get(int key) {
    	// 遍历数组查找节点
        for (int i = 0; i < size; i++) {
            if (key == list[i].key) {
            	//  将找到的节点timeStamp更新为当前时间
                list[i].timeStamp = System.currentTimeMillis();
                return list[i].value;
            }
        }
        return 0;
    }

    public static void main(String[] args) throws InterruptedException {
        ArrayImplLRU arrayImplLRU = new ArrayImplLRU();
        for (int i = 1; i <= 10; i++) {
            arrayImplLRU.add(i, i * 100);
            // 不加这行，由于添加太快，每个timeStamp都一样
            Thread.sleep(1);
        }
        for (int i = 11; i <= 15; i++) {
            arrayImplLRU.add(i, i * 100);
            Thread.sleep(1);
        }
        for (Node node : arrayImplLRU.list) {
            System.out.print(node.key +", ");
        }
    }
}
链表实现LRU 
class LNode {
    public int key;
    public int value;
    // 双向链表
    LNode next;
    LNode prev;

    public LNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class linkedImplLRU {
    // 链表头节点
    private LMNode head;
    // 链表尾节点
    private LMNode tail;
    // 有效节点个数
    private int size = 0;

    public void add(int key, int value) {
    	// 如果链表为空，初始化头尾节点
        if (head == null) {
            head = new LNode(key, value);
            tail = head;
        } else {
        	// 判断链表容量有无达到极限，没有无须进行缓存淘汰
            if (size < 10) {
            	// 双向链表操作无非就创建一个节点，然后把节点与节点之间的线连好，
				// 初学者最好拿张纸画下，每个节点有前后两条线，代码就是为了处理不同节点的两条线
                LNode temp = new LNode(key, value);  // 创建一个节点 temp
                 // 往链表头插入节点
                temp.next = head;// 连好temp后面的线 temp ——> head
                head.prev = temp;// 连好head前面的线 temp <—— head
                head = temp;// 将头节点指针从原先的头节点移到temp
                size++;
            } else {
                // 删除双向链表最后的结点
                LNode tailPrev = tail.prev;
                tail.prev = null;
                tailPrev.next = null;
                tail = tailPrev;

                // 在链表头增加结点
                LNode temp = new LNode(key, value);
                temp.next = head;
                head.prev = temp;
                head = temp;
            }
        }
    }

    public int get(int key) {
        LNode temp = head;
        // 遍历链表查找结点
        while (temp != null) {
            if (temp.key == key) {
                int result = temp.value;
                if (temp == head) {

                }
                // 如果temp是尾结点
                else if (temp.next == null) {
                    // 设置尾结点
                    tail = temp.prev;
                    // 解除和前一结点的连接
                    temp.prev.next = null;
                    temp.prev = null;
                    //插入队头
                    temp.next = head;
                    head.prev = temp;
                    head = temp;

                }
                // 如果temp是中间结点
                else {
                    // 建立前一结点和后一结点联系
                    temp.prev.next = temp.next;
                    temp.next.prev = temp.prev;
                    // 解除和前一结点的连接
                    temp.prev = null;
                    // 解除和后一结点的连接
                    temp.next = null;

                    //插入队头
                    temp.next = head;
                    head.prev = temp;
                    head = temp;
                }
                // 返回结果
                return result;
            }
            temp = temp.next;
        }
        return 0;
    }

    public static void main(String[] args) throws InterruptedException {
        linkedImplLRU linkedImplLRU = new linkedImplLRU();
        for (int i = 1; i <= 10; i++) {
            linkedImplLRU.add(i, i * 100);
            Thread.sleep(1);
        }
        linkedImplLRU.get(2);
        linkedImplLRU.get(4);
        for (int i = 11; i <= 15; i++) {
            linkedImplLRU.add(i, i * 100);
            Thread.sleep(1);
        }
        LNode temp = linkedImplLRU.head;
        while (temp != null) {
            System.out.println(temp.key);
            temp = temp.next;
        }
    }
}
链表 + HashMap实现LRU 
class LMNode {
    public int key;
    public int value;
    // 双向链表
    LMNode next;
    LMNode prev;

    public LMNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class linkedHashMapImplLRU {
	// 链表头节点
    private LMNode head;
    // 链表尾节点
    private LMNode tail;
    // 有效节点个数
    private int size = 0;
    // HashMap的键为LMNode节点的key，值为LMNode节点
    private Map map = new HashMap<>();

    public void add(int key, int value) {
		// 如果链表为空，初始化头尾节点
        if (head == null) {
            head = new LMNode(key, value);
            // 将第一个节点添加进HashMap
            map.put(key, head);
            tail = head;
            size++;
        } else {
        	// 判断链表容量有无达到极限，没有无须进行缓存淘汰
            if (size < 10) {
				// 双向链表操作无非就创建一个节点，然后把节点与节点之间的线连好，
				// 初学者最好拿张纸画下，每个节点有前后两条线，代码就是为了处理不同节点的两条线
                LMNode temp = new LMNode(key, value); // 创建一个节点 temp
                map.put(key, temp);
                // 往链表头插入节点
                temp.next = head; // 连好temp后面的线 temp ——> head
                head.prev = temp; // 连好head前面的线 temp <—— head
                head = temp; // 将头节点指针从原先的头节点移到temp
                size++;
            } else {
				// 删除HashMap中对节点的引用
                map.remove(tail.key);

                // 删除双向链表最后的结点
                LMNode tailPrev = tail.prev;
                tail.prev = null;
                tailPrev.next = null;
                tail = tailPrev;

                // 在链表头增加结点
                LMNode temp = new LMNode(key, value);
                map.put(key, temp);
                temp.next = head;
                head.prev = temp;
                head = temp;
            }
        }
    }

    public int get(int key) {
        LMNode temp = map.get(key);
        if (temp.key == key) {
            int result = temp.value;
            if (temp == head) {

            }
            // 如果temp是尾结点
            else if (temp.next == null) {
                // 设置尾结点
                tail = temp.prev;
                // 解除和前一结点的连接
                temp.prev.next = null;
                temp.prev = null;
                //插入队头
                temp.next = head;
                head.prev = temp;
                head = temp;

            }
            // 如果temp是中间结点
            else {
                // 建立前一结点和后一结点联系
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                // 解除和前一结点的连接
                temp.prev = null;
                // 解除和后一结点的连接
                temp.next = null;

                //插入队头
                temp.next = head;
                head.prev = temp;
                head = temp;
            }
            // 返回结果
            return result;
        }
        return 0;
    }


    public static void main(String[] args) throws InterruptedException {
        linkedHashMapImplLRU linkedHashMapImplLRU = new linkedHashMapImplLRU();
        for (int i = 1; i <= 10; i++) {
            linkedHashMapImplLRU.add(i, i * 100);
            Thread.sleep(1);
        }
        // 最近使用过了就不会淘汰
        linkedHashMapImplLRU.get(2);
        linkedHashMapImplLRU.get(4);
        for (int i = 11; i <= 15; i++) {
            linkedHashMapImplLRU.add(i, i * 100);
            Thread.sleep(1);
        }
        LMNode temp = linkedHashMapImplLRU.head;
        while (temp != null) {
            System.out.println(temp.key);
            temp = temp.next;
        }
    }
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/3974546.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
钢结构图集 钢结构图集 一级用户组
0 0
上一篇 2022-10-21
下一篇 2022-10-21

发表评论

登录后才能评论

评论列表（0条）

保存