本文共 3266 字，大约阅读时间需要 10 分钟。

前言

比如我们在使用Redis中如果出现内存不够的时候，它会有一个内存淘汰策略，比如Random和LRU和LFU，而且我们使用最多的也就是LRU，所以我今天讲讲这个是如何实现的。

LRU

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

4. 最开始时，内存空间是空的，因此依次进入A、B、C是没有问题的
5. 当加入D时，就出现了问题，内存空间不够了，因此根据LRU算法，内存空间中A待的时间最为久远，选择A,将其淘汰
6. 当再次引用B时，内存空间中的B又处于活跃状态，而C则变成了内存空间中，近段时间最久未使用的
7. 当再次向内存空间加入E时，这时内存空间又不足了，选择在内存空间中待的最久的C将其淘汰出内存，这时的内存空间存放的对象就是E->B->D

实现

使用LinkedHashMap实现

LinkedHashMap内部维护一个一个双向链表和一个hash表，所以在O(1)的时间复杂度下实现LRU。

/** * 使用jdk库类实现LRU */class LRUCacheByLinkedHashMap {       private LinkedHashMap<Integer, Integer> nodes;    private int size;    public LRUCacheByLinkedHashMap(int capacity) {           //实现LRU的linkedHashMap的构造方法        nodes = new LinkedHashMap<>(capacity, 0.75f, true);        this.size = capacity;    }    public int get(int key) {           Integer ret = nodes.get(key);        return ret == null ? -1 : ret;    }    public void put(int key, int value) {           nodes.put(key, value);        if (nodes.size() > size) {               //使用迭代器删除第一个数据            Iterator<Map.Entry<Integer, Integer>> iterator = nodes.entrySet().iterator();            if (iterator.hasNext()) {                   iterator.next();                iterator.remove();            }        }    }}

自己实现LRU

我们通过看LinkedHashMap的源代码，知道其所以然后就可以自己实现它。

class LRUCache {       static class Node {           int key;        int val;        Node prev;        Node next;        private Node(){   }        public Node(int key, int val) {               this.key = key;            this.val = val;        }    }    private int size;    private HashMap<Integer, Node> map;    private int capacity;    private Node head;    private Node tail;    public LRUCache(int capacity) {           this.size = 0;        this.capacity = capacity;        map = new HashMap<>();        head = new Node();        tail = new Node();        head.next = tail;        tail.prev = head;    }    public int get(int key) {           Node node = map.get(key);        if (node == null) {               //没有这个节点            return -1;        }        //需要移动到最前面        moveHead(node);        return node.val;    }    private void moveHead(Node node) {           //先删除这个节点，然后再将这个节点添加到头部        deleteNode(node);        addHead(node);    }    private void addHead(Node node) {           node.prev = head;        node.next = head.next;        head.next.prev = node;        head.next = node;    }    private void deleteNode(Node node) {           node.prev.next = node.next;        node.next.prev = node.prev;    }    public void put(int key, int value) {           Node node = map.get(key);        if (node == null) {               //得新建节点            Node cur = new Node(key, value);            map.put(key, cur);            //将这个节点放到头部            addHead(cur);            ++size;            if (size > capacity) {                   //删除尾节点 下面这俩步不能放反，放反的话map中删除的节点就是待删除的前一个节点                map.remove(tail.prev.key);                deleteTailNode();                --size;            }        } else {               //说明有这个节点了            node.val = value;            moveHead(node);        }    }    private void deleteTailNode() {           Node node = tail.prev;        deleteNode(node);    }}