从零实现一个LRU，同时优化我们的版本。

概念

wiki:

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes. LRU is actually a family of caching algorithms with members including 2Q by Theodore Johnson and Dennis Shasha,[5] and LRU/K by Pat O’Neil, Betty O’Neil and Gerhard Weikum.[6]

Least Recently Used 最近最少使用，是一种缓存替换策略。

LRU意味着最近、最多使用的优先级应该提高。

特性
容器头表示优先级高 `Most Recently Used`，容器尾表示优先级低 `Least Recently Used`
每次近期访问都前置元素的位置
插入新数据时判断capacity/size，如果满了capacity，则释放队尾元素
最近：插入新数据，放到队头
最多：多次访问已有数据，放到队头

wiki给出了一个示例，一个序列中访问顺序：A B C D E D F，缓存容量为4。

根据特性实现我们的LRU算法，由于跟缓存紧密联系，大家一般都实现叫做LRUMap，我在github上的实现按照底层的结构来命名。

提供的功能包括：

访问数据 get(K key)
写入数据 put(K key,V val)

实现

我们姑且不论复杂度分析，先按照基本逻辑实现一个可用的版本，根据版本缺陷进行优化。

基于单向链表

首先我们先按照单向链表来实现。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161


public class LinkedListLRU<T> {

    /**
     * 最新数据保存在链表头，最老数据逐渐搬移到链表尾
     */
    LRUListNode<T> dummy;
    /**
     * lru容量
     */
    int capacity;
    /**
     * 当前数据量
     */
    int size;

    public LinkedListLRU(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.dummy = new LRUListNode<T>();
    }

    /**
     * 每次访问：
     * - 无数据时返回null
     * - 有数据时获取到位置，将node搬移到链表头
     * <p>
     * 每次均需遍历整个链表，访问复杂度 O(n)
     *
     * @param val 待查询的key
     * @return 命中的链表节点
     */
    public LRUListNode<T> get(T val) {
        LRUListNode<T> prev = dummy;
        while (prev.next != null) {
            if (prev.next.val.equals(val)) {
                LRUListNode<T> root = dummy.next;
                // 删除curr当前位置
                LRUListNode<T> curr = prev.next;
                prev.next = curr.next;
                // 挪动curr到链表头
                dummy.next = curr;
                curr.next = root;
                return curr;
            } else {
                prev = prev.next;
            }
        }
        return null;
    }

    /**
     * 每次插入：
     * - 原来无对应数据时，将val插入到root的位置，同时判断是否达到capacity，如果达到，淘汰链表尾部节点
     * - 有数据时，找到原位置并删除，插入到root
     * <p>
     * 插入时也需要先遍历链表，复杂度 O(n)
     * 单插入、删除节点复杂度均为
     *
     * @param val 待插入的val
     */
    public void put(T val) {
        if (dummy.next == null) {
            dummy.next = new LRUListNode<>(val);
            if (size > capacity) {
                deleteTail();
            }
            ++size;
            return;
        }

        LRUListNode<T> prev = findPrevByVal(val);
        if (prev == null) {
            insertByPrev(dummy, val);
            if (size > capacity) {
                deleteTail();
            }
        } else {
            deleteByPrev(prev);
            insertByPrev(dummy, val);
        }
    }

    private void deleteByPrev(LRUListNode<T> prev) {
        prev.next = prev.next.next;
        --size;
    }

    /**
     * 根据前序节点插入
     *
     * @param prev 前序
     * @param val  当前节点值
     */
    private void insertByPrev(LRUListNode<T> prev, T val) {
        LRUListNode<T> nextTmp = prev.next;
        LRUListNode<T> newNode = new LRUListNode<>(val);
        newNode.next = nextTmp;
        prev.next = newNode;
        ++size;
    }

    /**
     * 遍历到尾部，遍历复杂度 O(n)，删除复杂度 O(1)
     */
    private void deleteTail() {
        if (dummy.next == null) {
            return;
        }

        LRUListNode<T> prev = dummy;
        while (prev.next.next != null) {
            prev = prev.next;
        }
        prev.next = null;
        --size;
    }

    private LRUListNode<T> findPrevByVal(T val) {
        LRUListNode<T> prev = dummy;
        while (prev.next != null) {
            if (prev.next.val.equals(val)) {
                return prev;
            }
            prev = prev.next;
        }
        return null;
    }

    void print() {
        System.out.println(this);

        LRUListNode<T> curr = dummy.next;
        while (curr != null) {
            System.out.print(curr.val + "-->");
            curr = curr.next;
        }
        System.out.println();
    }

    @Override
    public String toString() {
        return "LinkedListLRU{" +
                "capacity=" + capacity +
                ", size=" + size +
                '}';
    }

    static class LRUListNode<T> {

        T val;

        LRUListNode<T> next;

        public LRUListNode() {
        }

        public LRUListNode(T val) {
            this.val = val;
        }
    }
}

缺点

可以看到基于链表可以实现LRU置换的逻辑，但是由于链表单向指针的局限，我们每次查找一个节点、删除节点都需要O(n)复杂度。

基于数组

开始我先按照只使用数组的思路实现了一版，发现查找没有利用好数组下标随机访问的特性，加入了k2Idx的map结构来加速查找。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138


public class ArrayLRU<K, V> {

    /**
     * 数组装数据
     */
    Entry<K, V>[] elements;
    /**
     * 队头：恒指向0
     */
    int head;
    /**
     * 队尾：指向待插入的下标
     */
    int tail;
    /**
     * 容量
     */
    int capacity;
    /**
     * key——》数组下标，方便访问，降低查坐标复杂度
     */
    Map<K, Integer> k2Idx;

    @SuppressWarnings("unchecked")
    public ArrayLRU(int capacity) {
        this.capacity = capacity;
        this.head = tail = 0;
        elements = new Entry[capacity];
        k2Idx = new HashMap<>(MapUtils.capacity(capacity));
    }

    /**
     * 根据key访问元素：
     * - 无元素时，返回null
     * - 有元素时，返回对应entry
     * <p>
     * 复杂度：
     * 每次均遍历整个数组，并且需要搬移前序数据，时间复杂度 O(n)
     * <p>
     * 优化：
     * 使用map缓存 key->index，降低查找元素位置的复杂度为 O(1)
     *
     * @param key 查询key
     * @return Entry
     */
    public Entry<K, V> get(K key) {
        if (head == tail) {
            return null;
        }
        Integer idx = k2Idx.get(key);
        if (null == idx || idx < head || idx >= tail) {
            return null;
        }
        Entry<K, V> target = elements[idx];
        // 搬移 i到0队头的位置
        moveArrFromEndInclusive(idx, target);
        return target;
//        for (int i = head; i < tail; i++) {
//            Entry<K, V> target = elements[i];
//            if (target.key.equals(key)) {
//                // 搬移 i到0队头的位置
//                moveArrFromEndInclusive(i, target);
//                return target;
//            }
//        }
//        return null;
    }

    /**
     * 从 i往1 的闭区间右移元素
     */
    private void moveArrFromEndInclusive(int i, Entry<K, V> target) {
        for (int j = i; j > 0; j--) {
            elements[j] = elements[j - 1];
            k2Idx.put(elements[j].key, j);
        }
        elements[head] = target;
        k2Idx.put(target.key, head);
    }

    /**
     * 复杂度：
     * 每次均需遍历数组、搬移数据，时间复杂度 O(n)
     */
    public void put(K key, V val) {
        int targetIdx = findIdxByKey(key);

        if (targetIdx >= head && targetIdx < tail) {
            // 元素已存在数组中 搬移
            Entry<K, V> targetEntry = elements[targetIdx];
            targetEntry.val = val;
            moveArrFromEndInclusive(targetIdx, targetEntry);
        } else {
            if (tail > capacity - 1) {
                // 淘汰队尾
                elements[tail - 1] = null;
                --tail;
            }
            ++tail;
            moveArrFromEndInclusive(tail - 1, new Entry<>(key, val));
        }
    }

    private int findIdxByKey(K key) {
        // 优化为从map中获取位置
        Integer idx = k2Idx.get(key);
        return idx == null ? -1 : idx;
//        for (int i = 0; i < tail; i++) {
//            if (elements[i].key.equals(key)) {
//                return i;
//            }
//        }
//        return -1;
    }

    public void print() {
        System.out.println(this);
        Arrays.stream(elements).filter(Objects::nonNull).forEach(element -> {
            System.out.print(element.key + "->" + element.val + "》》");
        });
        System.out.println();
    }

    @Override
    public String toString() {
        return "ArrayLRU{" + "head=" + head + ", tail=" + tail + ", capacity=" + capacity + '}';
    }

    static class Entry<K, V> {
        K key;
        V val;

        public Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
}

优点

加入了k2Idxmap可以加速查找对应元素位置。

缺点

搬移数据依然有较高开销，整体复杂度还是O(n)。

基于双向链表

观察我们上述关键操作：

写入新元素时，基于单向链表可以以O(1)的复杂度原地完成，数组则需要数据搬移；
元素数据量达到容量时，队尾数据需要删除，所以最好可以O(1)完成；
随机元素访问时，我们要以O(1)复杂度找到，这一步已经在基于数组的版本中通过加入map做到了快速定位，当然，有一点内存开销；

因此，除了特性，到这一步我们梳理出了优化点，根据这些优化点，我们基于双向链表来实现。

双向链表写入新元素同样是O(1)复杂度；
可以维护头尾指针，方便头尾操作；
同样维护map来定位随机node；

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161


public class DoubleLinkedListLRU<K, V> {

    /**
     * first head 指向第一个真实节点的prev
     */
    DoubleLinkedListNode<K, V> head;
    /**
     * last tail 指向最后真实节点的next
     */
    DoubleLinkedListNode<K, V> tail;
    /**
     * 当前数据量
     */
    int size;
    /**
     * lru容量
     */
    int capacity;
    /**
     * 通过key定位链表中的双向链表节点
     */
    Map<K, DoubleLinkedListNode<K, V>> k2Node;

    public DoubleLinkedListLRU(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        k2Node = new HashMap<>(MapUtils.capacity(capacity));
        this.head = new DoubleLinkedListNode<>();
        this.tail = new DoubleLinkedListNode<>();
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        // O(1)
        DoubleLinkedListNode<K, V> node = k2Node.get(key);
        if (node == null) {
            return null;
        }
        // O(1)
        // 删除原位置元素
        removeNode(node);
        insertNewHead(node);
        return node.entry.val;
    }

    public void put(K key, V val) {
        // O(1)
        DoubleLinkedListNode<K, V> targetNode = k2Node.get(key);
        if (targetNode == null) {
            // 数据原来不存在
            if (size == capacity) {
                // 淘汰末尾元素
                evictTail();
            }
            DoubleLinkedListNode<K, V> newNode = new DoubleLinkedListNode<>(key, val);
            insertNewHead(newNode);
            ++size;
        } else {
            // 数据原来已存在，直接更换节点位置
            removeNode(targetNode);
            insertNewHead(targetNode);
        }
    }

    // O(1)
    private void evictTail() {
        DoubleLinkedListNode<K, V> last = tail.prev;
        tail.prev = last.prev;

        last.prev.next = tail;

        last.next = null;
        last.prev = null;
        k2Node.remove(last.entry.key);
        --size;
    }

    // O(1)
    private void insertNewHead(DoubleLinkedListNode<K, V> targetNode) {
        if (head.next == tail) {
            tail.prev = targetNode;
        }
        targetNode.next = head.next;
        targetNode.prev = head;

        head.next.prev = targetNode;

        head.next = targetNode;
        k2Node.put(targetNode.entry.key, targetNode);
    }

    // O(1)
    private void removeNode(DoubleLinkedListNode<K, V> targetNode) {
        targetNode.prev.next = targetNode.next;
        targetNode.next.prev = targetNode.prev;
        k2Node.remove(targetNode.entry.key);
    }

    public DoubleLinkedListNode<K, V> randomNode() {
        int i = NumberUtils.randomInt(size);
        System.out.println("randomI:" + i);
        DoubleLinkedListNode<K, V> curr = head;
        while (i > 0) {
            curr = curr.next;
            --i;
        }
        return curr;
    }

    public void print() {
        System.out.println(this);

        DoubleLinkedListNode<K, V> curr = head;
        while (curr != null) {
            if (curr.entry != null) {
                System.out.print(curr.entry.val + "-->");
            }
            curr = curr.next;
        }
        System.out.println();
    }

    @Override
    public String toString() {
        return "DoubleLinkedListLRU{" + ", size=" + size + ", capacity=" + capacity + '}';
    }

    static class DoubleLinkedListNode<K, V> {
        DoubleLinkedListNode<K, V> prev;
        DoubleLinkedListNode<K, V> next;
        Entry<K, V> entry;

        public DoubleLinkedListNode(K key, V val) {
            this.entry = new Entry<>(key, val);
        }

        public DoubleLinkedListNode() {
        }

        @Override
        public String toString() {
            return "DoubleLinkedListNode{" + "prev=" + (prev == null ? "null" : prev.entry) + ", next=" + (next == null ? "null" : next.entry) + ", entry=" + entry + '}';
        }
    }

    static class Entry<K, V> {
        K key;
        V val;

        public Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Entry{" + "key=" + key + ", val=" + val + '}';
        }
    }
}

可以看到在我们的关键操作上，基于双向链表的版本都做到了O(1)。

总结

以上，实现了不同版本的LRU，根据前面的版本缺陷分析优化得出了基于双向链表的版本。

想要实现一个bug free并且工业级的LRU，还有更多细节需要处理。

Ref

https://en.wikipedia.org/wiki/Cache_replacement_policies

概念#

实现#

基于单向链表#

缺点#

基于数组#

优点#

缺点#

基于双向链表#

总结#

Ref#

概念

实现

基于单向链表

缺点

基于数组

优点

缺点

基于双向链表

总结

Ref