手写 LRU (Least Recently Used)

前言

我有一个朋友面试的时候被问到过，要手撸一个LRU算法，所以我也准备一下好了。

页面置换算法

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存 「 已无空闲空间 」 时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。

这里通常把选择换出页面的算法称为 「 页面置换算法 」 (Page-Replacement Algorithms)。置换算法的好坏， 将直接影响到系统的性能。

一个好的页面置换算法，应具有 「 较低的页面更换频率 」 。从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再访问的页面调出。存在着许多种置换算法，它们都试图更接近于理论上的目标。

LRU

LRU是Least Recently Used的缩写，即 「 最近最少使用 」 ，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

简单来说 如果一个数据在 「 最近一段时间 」 内 「 使用次数很少 」 ，那么在将来一段时间内被使用的可能性也很小 ，所以我如果 「 内存到了一定限制 」 ，可以先把它淘汰掉这样。

伪代码「其实这就够了」

这里的话我选择用 双向链表 + HashMap 的写法:

1. 首先定义一下Node节点

public class Node {
    private int key;
    private int val;
    private Node pre;
    private Node next;
    
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
        this.pre = null;
        this.next = null;
    }
}

2. 定义双向链表

// 这里的链表只存头和尾，主要是控制最近最少使用「head」，和最新使用的「tail」
public class LinkedList {
    private Node head;
    private Node tail;
    
    // 最新使用的数据的话就需要把数据移动到尾
    public void moveToTail(Node n) {
        // 将已存在的n移到尾部
    }
    
    // 最新使用的新数据就加入到尾
    public void addToTail(Node n) {
        // 将n加入到tail后面
    }
    
    // 到达限制要移除头部
    public Node removeHead() {
        // 移除头部然后返回
    }
}

3. LRUCache

public class LRUCache {
    private HashMap<Integer, Node> map;
    private LinkedList list;
    private capacity;
    
    public int get(int key) {
        // 获取Node
        // 刚用完，移到尾部
        // 返回
    }
    
    public void put(int key, int val) {
        // 查看一下map原来有没有
        // 有 -> 修改val并移到尾部（刚用完）
        // 无 -> 1. 加入尾部，放进map
        // 无 -> 2. 比较map的大小跟限制的长度capacity，大了就移除最近最少使用的head，小了不管就ok。
    }
}

完整代码及分析

import java.util.HashMap;


/**
 * LRUCache
 * @author tonghua
 * @create 2020-03-14 16:53
 */
public class LRUCache {
    
    // 双向链表控制头尾
    private LinkedList list;
    // hashmap保存数据
    private HashMap<Integer, Node> map;
    // capacity限制LRUCache的大小
    private int capacity;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.list = new LinkedList();
        this.capacity = capacity;
    }

    public class Node {
        public int key;
        public int val;
        Node pre;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

    // head为最近最少使用的
    public class LinkedList {
        public Node head;
        public Node tail;

        public LinkedList() {
            this.head = null;
            this.tail = null;
        }
        
        // 最新使用的数据的话就需要把数据移动到尾
        public void moveToTail(Node n) {

            // 如果用的是头，那么把头往后移一个
            if (n == head) {
                head = n.next;
                head.next = null;
            } else {
                n.pre.next = n.next;
                n.next.pre = n.pre;
            }
            
            // 把对应的n移动到尾部
            tail.next = n;
            n.pre = tail;
            n.next = null;
            tail = n;
        }

        // 最新使用的新数据就加入到尾
        public void addToTail(Node n) {
            
            // 如果是第一个，头跟尾都是n
            if (head == null) {
                head = n;
                tail = n;
            } else {
                // 不是第一个就往尾后加n，尾后移一个
                tail.next = n;
                n.pre = tail;
                tail = tail.next;
            }
        }

        // 移除最近最少使用元素
        public Node removeHead() {
            Node n = head;
            // 这种情况只会出现在capacity=1的情况
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                // 正常应该是把头移除，然后返回头（给hashMap移除用的）
                head = head.next;
                head.pre = null;
            }
            return n;
        }
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            Node n = map.get(key);
            list.moveToTail(n);
            return n.val;
        }
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            n.val = val;
            list.moveToTail(n);
        } else {
            Node n = new Node(key, val);
            map.put(key, n);
            list.addToTail(n);

            if (map.size() > capacity) {
                map.remove(list.removeHead().key);
            }

        }
    }
}

PS

都结合网上资料加上自己的一些理解，如果有影响到人的地方，可以联系我： fzfz2007@163.com