基于双向链表和哈希表实现LRU

LRU

LRU的定义

• LRU是一种页面置换算法，即当内存中没有空闲页面但又需要内存时，操作系统会选择内存中的一个页面进行淘汰。淘汰页面的规则称为页面置换算法，同样，这种淘汰页面的规则也适用于缓存淘汰。LRU全称是最近最久未使用算法，LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。根据局部性原理，当一个页面最近被访问，他很有可能再次被访问。因此LRU通常性能比较好。

LRU实现分析

• 我们假设将内存中所有到访的页面放置到链表中，新加入的数据尾插。内存中已经存在的页面被访问时，会将其移向链表的尾部。也就是说那些刚加入或者刚访问过的页面都会靠近链表尾部，因此最久未被使用的页面自然就在链表头部。当需要淘汰一个页面时，将链表头部的页面丢弃。

LRU基于链表和哈希表的实现

package collection.List;

import java.util.HashMap;

public class LRU<T> {

    private int capacity;
    private HashMap<Integer, ListNode> map;
    private ListNode head; // 链表的头结点，next指向链表中的第一个元素
    private ListNode tail; //链表的尾节点，链表的最后一个元素的next指向tail
    // 设置一个head和tail是为了方便对链表中的头结点和尾节点进行操作。

    private class ListNode { //双向链表，用来存储缓存的值
        int key;
        int val;
        ListNode prev;
        ListNode next;
        public ListNode(){

        }
        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public LRU(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new ListNode();
        tail = new ListNode();
        head.next = tail; // 初始情况下，头结点的next指向tail表示链表当前为空
        tail.prev = head; // 初始情况下，tail节点的prev指向head
    }

    private void removeNode(ListNode node) { // 在链表中的移除node节点
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addNodeToLast(ListNode node) {
        node.prev = tail.prev; // 首先将node的前驱节点设置为链表中的最后一个节点
        node.prev.next = node; // 然后设置插入节点为原链表中最后一个节点的next
        node.next = tail; //更新tail为当前插入节点的next
        tail.prev= node; //更新tail的prev域
    }

    public void  moveNodeToLast(ListNode node) {
        removeNode(node); // 删除原节点
        addNodeToLast(node); //将原节点的副本加入到链表尾部
    }

    public int get(int key) {
        if(map.containsKey(key)) { // 如果值存在，则将其移动到链表尾部，并返回值
            ListNode node = map.get(key);
            moveNodeToLast(node);
            return node.val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){ // 如果哈希表记录中找到缓存中包含key
            ListNode node = map.get(key);
            node.val = value; // 则重新设置key所对应的value
            map.replace(key, node);
            moveNodeToLast(node); // 将原节点删除，并将其副本加入链表尾部
            return;
        }
        if(map.size() == capacity){ // 如果哈希表中没有找到缓存，且链表满，则将链头节点移除，并在哈希表中将其删除
            map.remove(head.next.key);
            removeNode(head.next);
        }

        ListNode node = new ListNode(key, value);
        map.put(key, node); // 将新节点用哈希表记录
        addNodeToLast(node); // 新节点加入链表尾部
    }
}