手撕LRU算法

定义

LRU(Least Recently Used)即最少使用，是一种内存管理算法。LRU算法基于一种假设：长期不被使用的数据，在未来被使用的几率也不大。因此当数据量达到一定阈值时，则需要删除最近最少被使用的数据。

LRU实现的思路

使用HashMap+双向链表的方式。

当访问Key3时，会将Value3在链表中的位置更新至表尾

如果容量满了，此时插入数据会将表头的键值对删除，再将新的节点添加至表尾以及HashMap中

代码实现

其实JDK已经为我们封装好了HashMap+双向链表的数据结构，即LinkedHashMap，当然我们也可以自己去实现。

接口定义

public interface LRUCache {

    Object getKey(String key);

    void putKey(String key, Object value);

}

LinkedHashMap实现

public class LinkedHashMapLRUCache implements LRUCache {

    private LinkedHashMap<String, Object> linkedHashMap;
    /**
     * 容量
     */
    private final int cacheSize;

    public LinkedHashMapLRUCache(int capacity) {
        this.cacheSize = capacity;
        // 三个构造函数的意义:
        // 第一个参数表示容量
        // 第二个参数表示负载因子
        // 第三个为linkedHashMap的排序模式.true代表根据最近访问顺序排序,false表示根据插入顺序排序.
        linkedHashMap = new LinkedHashMap<String, Object>(capacity, 0.75f, true) {
            /**
             * 钩子方法，通过put新增键值对的时候，若该方法返回true
             * 便移除该map中最老的键和值
             */
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                // 当 map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
                return size() > cacheSize;
            }
        };
    }

    @Override
    public Object getKey(String key) {
        return linkedHashMap.get(key);
    }

    @Override
    public void putKey(String key, Object value) {
        System.out.println("===> putKey:" + key + ",value:" + value);
        linkedHashMap.put(key, value);
    }
}

自定义HashMap+LinkedList实现

public class CustomLRUCache implements LRUCache {

    private HashMap<String, Node> hashMap;
    // 头节点
    private Node head;
    // 尾节点
    private Node tail;

    /**
     * 容量
     */
    private final int cacheSize;

    public CustomLRUCache(int cacheSize) {
        hashMap = new HashMap<>(cacheSize);
        this.cacheSize = cacheSize;
    }

    /**
     * 双向链表的节点
     */
    public class Node {
        // 前驱节点
        private Node prev;
        // 后驱节点
        private Node next;
        // key值
        private String key;
        // value值
        private Object value;

        public Node(String key, Object value) {
            this.key = key;
            this.value = value;
        }

    }


    @Override
    public Object getKey(String key) {
        Node node = hashMap.get(key);

        //如果为空则返回空
        if (node == null) {
            return null;
        }

        //如果不为空则更新Node位置
        refreshNode(node);
        // 返回数据
        return node.value;

    }

    @Override
    public void putKey(String key, Object value) {
        Node node = hashMap.get(key);

        if (node == null) {
            // node 不存在,则需要插入数据

            // 如果数据量大于等于阈值,则删除表头节点
            if (hashMap.size() >= cacheSize) {
                String headKey = head.key;
                deleteNode(head);
                hashMap.remove(headKey);
            }
            // 表尾插入新节点
            Node newNode = new Node(key, value);
            addNode(newNode);
            hashMap.put(key, newNode);

        } else {
            // node 存在,则更新节点
            node.value = value;
            refreshNode(node);
        }
    }

    /**
     * 更新Node位置
     */
    private void refreshNode(Node node) {
        // 如果访问的是尾节点，无需移动节点
        if (node == tail) {
            return;
        }
        // 移除节点
        deleteNode(node);
        // 重新插入节点
        addNode(node);
    }

    /**
     * 移除节点
     */
    private void deleteNode(Node node) {
        if (node == tail) {
            // 如果该节点是尾结点,则移除尾节点
            tail = tail.prev;
        } else if (node == head) {
            // 如果该节点是头结点,则移除头节点
            head = head.next;
        } else {
            // 如果该节点是中间结点
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    /**
     * 插入一个节点
     */
    private void addNode(Node node) {
        if (tail != null) {
            tail.next = node;
            node.prev = tail;
            node.next = null;
        }
        // 该节点为尾节点
        tail = node;
        if (head == null) {
            head = node;
        }
    }

}