基于 HashMap 和双向链表实现 LRU

需求

假设用户信息存储在数据库里，为了提高性能，不是每次的业务方请求时都要查询数据库，可以在内存中创建一个缓存（可以理解为高速缓冲存储器cache），每当要查找一个用户信息时，会首先在哈希表（缓存）中进行查询，以此来提高访问的性能。假设使用哈希链表来缓存用户信息，并假设目前已缓存了4个用户，这4个用户是按照时间顺序依次从链表右端插入的。
在这里插入图片描述
此时，业务方访问用户5，由于哈希链表中没有用户5的数据，需要从数据库中读取出来，插入到缓存当中。此时，链表中最右端是最新访问到的用户5，最左端是最近最少访问的用户1，假设此时已达到缓存容量上限5，如下图所示。
在这里插入图片描述
接下来要做如下几件事：

（1）业务方要访问用户2，哈希链表中存在用户2的数据，怎么做呢？

（2）业务方请求访问用户4的信息，该怎么做？

（3）业务方请求访问用户6的信息，该怎么做？

LRU算法

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法就是将最近最久未使用的页面予以淘汰。

LRU原理（针对需求）

假设 n 个用户的数据顺序存储在数据库（数组）中。
数据结构： 用一个类 Node 存储用户数据，缓冲区由 HashMap 与 Node 组成的双向链表组成。其中 HashMap 存储number（key）到双向链表中 Node（value）的映射关系。这样可以做到访问缓冲区数据的时间为 O(1)，双向链表也便于对缓存区数据进行增、删、移动。数据结构结构如下图：
在这里插入图片描述

原理：

每次访问数据先访问HashMap，如果有该用户的数据，则保存到Node的实例对象node中，并返回查询结果；如果没有，则线性扫描数组（简易数据库），如果有该用户的数据，则保存到Node的的实例对象node中，数组中若没有就抛出异常。
1）如果node是通过HashMap访问双向链表得到的，则在双向链表中将其移动到head的下一个结点。2）如果node是访问数据库得到的，且缓存未满，则将其插入head的下一个结点，然后更新HashMap。3）如果node是访问数据库得到的，且缓存已满，则将 tail 上一个结点删除，然后将其插入到head的下一个结点，然后更新HashMap。
Java代码

import java.util.ArrayList;

import java.util.HashMap;

import java.util.NoSuchElementException;

import java.util.Scanner;



public class LRU {



    class Node {               //data structure

        int primarykey;

        String username;

        Node last;

        Node next;



        public Node(int key, String username) {

            this.primarykey = key;

            this.username = username;

            this.last = null;

            this.next = null;

        }



        public Node() {

            this.primarykey = 0;

            this.username = null;

            this.last = null;

            this.next = null;

        }

    }



    private Node head, tail;

    private ArrayList<Node> database = new ArrayList<>();    //database use a ArrayList

    private HashMap<Integer, Node> cache = new HashMap<>();  //cache

    private int count = 0;

    private int capacity;

    private final int database_size = 10;



    public LRU(int capacity) {

        this.capacity = capacity;

        head = new Node();

        tail = new Node();

        head.next = null;

        head.last = tail;

        tail.next = head;

        tail.last = null;

        //first parameter is key, second is name(for simplicity, use english compress of key).

        saveToDatebase(1, "one");

        saveToDatebase(2, "two");

        saveToDatebase(3, "three");

        saveToDatebase(4, "four");

        saveToDatebase(5, "five");

        saveToDatebase(6, "six");

        saveToDatebase(7, "seven");

        saveToDatebase(8, "eight");

        saveToDatebase(9, "nine");

        saveToDatebase(10, "ten");

    }



    private void saveToDatebase(int key, String username) {

        if (database.size() < database_size)

            database.add(new Node(key, username));

        else

            System.out.println("To much data, I can't save it, Sorry");

    }



    private void print(Node node) {

        if (node != null)

            System.out.println("number:" + node.primarykey + ", name:" + node.username);

        else

            throw new IllegalArgumentException("node is null!");

    }



    private void get(int key) {

        Node node = cache.get(key), beitai = cache.get(key);

        if (beitai == null) {          //不在缓存中。

            System.out.println(

                    "Cache don't have the information about that user,load from database!");

            node = searchDatabase(key);

        }

        System.out.print("Information about that user: ");

        print(node);

        //不在缓存中且缓存未满。        

        if (cache.size() < capacity && beitai == null) { 

            addnode(node);

            cache.put(node.primarykey, node);

        }

        //不在缓存中且缓存已满。

        else if (cache.size() == capacity && beitai == null) { 

            cache.remove(tail.next.primarykey);

            cache.put(node.primarykey, node);

            removenode(tail.next);

            addnode(node);

        }

        //在缓存中。

        else if (beitai != null) {

            movenode(node);

        }

    }



    private Node searchDatabase(int key) {

        for (Node node : database) {

            if (node.primarykey == key)

                return node;

        }

        throw new NoSuchElementException("Database doesn't have that data!");

    }

     //移动结点到最前面

    private void movenode(Node node) {

        removenode(node);

        addnode(node);

    }

     //在最前面添加结点

    private void addnode(Node node) {

        node.next = head;

        node.last = head.last;

        head.last.next = node;

        head.last = node;

    }

     //删除最后面的结点

    private void removenode(Node node) {

        node.next.last = node.last;

        node.last.next = node.next;

    }



    private void printcache() {

        for (Node node = tail.next; node != head; node = node.next) {

            print(node);

        }

    }



    public static void main(String[] args) {

        LRU l = new LRU(5);

        int q; //random initialization;

        Scanner input = new Scanner(System.in);



        while (true) {

            System.out.print("Input the id of user you want to query(0 to quit): ");

            q = input.nextInt();

            if (q == 0)

                break;

            l.get(q);

            System.out.println("Current cache: ");

            l.printcache();

            System.out.println();

        }

    }

}
//写的比较烂，大家凑活看。