LRUCache的Java实现

发表于 | 分类于

LRUCache简介

没错，面试的时候让我写LRUCache，当时只知道需要一个HashMap和一个链表，但是考虑的问题不全名，也没有考虑到多线程的问题。回来以后学习了下LRUCache的一些Java实现，其实可以套用LinkedHashMap，很多方法都给实现好了，当然也可以使用HashMap+链表，但是后者写起来更加复杂，当时面试的情况，感觉是让我利用LinkedHashMap数据结构。

  • 首先缓存的大小是固定的，给缓存分配一个固定的大小。
  • 每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新。

  • 需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。

    熟悉LinkedHashMap的话可以继承LinkedHashMap来实现LRU缓存。因此需要去查看LinkedHashMap的源码。顺手写了一篇LinkedHashMap源码剖析，写的不是很深刻，不过可以了解其大概的实现方案。

LinkedHashMap实现LRUCache

LinkedHashMap自身实现了顺序存储，通过其初始化参数accessOrder可以指定其顺序方式，accessOrder为false时，采用默认的存储顺序，按照插入顺序存储，也就是一个FIFO缓冲实现，因为最老的总在最前面。而accessOrder为true时，采用的是访问顺序存储，也就是最近读取的数据放在最前面，最早读取的数据放在最后面。同时还有一个判断是否删除最老数据的方法，默认返回false，而我们需要当前缓存的长度小于链表长度时删除链表头的元素。

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
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * Created by cdx0312
 * 2018/4/3
 * 继承LinkedHashMap实现
 */
public class LRUCache1<K, V> extends LinkedHashMap<K, V> {
    //缓存的大小
    private int cacheSize;
    //初始化时保证LinkedHashMap的初始大小要大于CacheSize+1，否则会发生扩容
    public LRUCache1(int cacheSize) {
        super(16, 0.75f, true);
        this.cacheSize = cacheSize;
    }
    /**
     * 重写该方法，当连表的size大于CacheSize时删除最老元素
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<K, V> entry : entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        LRUCache1<String, String> lruCache1 = new LRUCache1<>(6);
        for (int i = 0; i < 6; i++) {
            lruCache1.put(i+"", i * i + "");
        }
        System.out.println(lruCache1.toString());
        lruCache1.put("s", "s");
        System.out.println(lruCache1.toString());
        lruCache1.put("2", "2222");
        System.out.println(lruCache1.toString());
        lruCache1.get(1+"");
        System.out.println(lruCache1.toString());
    }
}

运行结果：

1
2
3
4
0:0 1:1 2:4 3:9 4:16 5:25
1:1 2:4 3:9 4:16 5:25 s:s
1:1 3:9 4:16 5:25 s:s 2:2222
3:9 4:16 5:25 s:s 2:2222 1:1
  • 继承实现方式，由于继承了Map接口，在多线程环境中使用时可以使用Collections.synchronizedMap()方法来实现线程安全操作。

LinkedHashMap的委托实现

不采用继承，而是采用委托的机制，需要自己进行线程同步来适应多线程场景。

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
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/3
 * LinkedHashMap的委托方法
 */
public class LRUCache2<K, V> {
    //缓存大小
    private final int CACHE_SIZE;
    //默认加载因子
    private final float DEFAULT_LOAD_FACTOR = 0.75f;
    //缓存容器
    private LinkedHashMap<K, V> map;
    //初始化过程中,传入缓存的大小，根据缓存大小和默认factor来计算
    // LinkedHashMap的初始容量，确保其不会产生扩容操作。
    // 从而完成了map容器的初始化内容。
    public LRUCache2(int cacheSize) {
        this.CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
        map = new LinkedHashMap<K,V>(capacity, DEFAULT_LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CACHE_SIZE;
            }
        };
    }
    /**
     * 多线程put方法，需要加锁
     * @param key
     * @param value
     */
    public synchronized void put (K key, V value) {
        map.put(key, value);
    }
    /**
     * 多线程get方法，需要加锁
     * @param key
     * @return
     */
    public synchronized V get(K key) {
        return map.get(key);
    }
    /**
     * 多线程remove方法，需要加锁
     * @param key
     */
    public synchronized void remove(K key) {
        map.remove(key);
    }
    /**
     * 多线程getAll方法，需要加锁
     * @return
     */
    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }
    /**
     * 多线程size方法，需要加锁
     * @return
     */
    public synchronized int size() {
        return map.size();
    }
    /**
     * 多线程clear方法，需要加锁
     */
    public synchronized void clear() {
        map.clear();
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry entry : map.entrySet()) {
            sb.append(String.format(" %s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        LRUCache2<Integer, String> lruCache2 = new LRUCache2<>(5);
        for (int i = 0; i < 5; i++) {
            lruCache2.put(i,"" + i);
        }
        System.out.println(lruCache2.toString());
        lruCache2.put(5,"5");
        System.out.println(lruCache2.toString());
        lruCache2.get(2);
        System.out.println(lruCache2.toString());
        lruCache2.put(6,"6");
        System.out.println(lruCache2.toString());
        lruCache2.remove(4);
        System.out.println(lruCache2.toString());
    }
}

运行结果

1
2
3
4
1:1  2:2  3:3  4:4  5:5
1:1  3:3  4:4  5:5  2:2
3:3  4:4  5:5  2:2  6:6
3:3  5:5  2:2  6:6

LRU Cache的链表+HashMap实现

该方法可以理解为手动实现一个LinkedHashMap，同时需要自己处理所线程的问题。

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
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/3
 * 链表+HashMap实现
 */
public class LRUCache3<K, V> {
    //缓存容量
    private final int CACHE_SIZE;
    //链表头
    private Entry head;
    //链表尾
    private Entry tail;
    //HashMap容器
    private HashMap<K, Entry<K, V>> hashMap;
    /**
     * 初始化HashMap容器和cacheSize
     * @param cacheSize 容量
     */
    public LRUCache3(int cacheSize) {
        this.CACHE_SIZE = cacheSize;
        hashMap = new HashMap<>();
    }
    /**
     * put方法，加锁
     * @param key
     * @param value
     */
    public synchronized void put (K key, V value) {
        Entry entry = getEntry(key);
        //hashmap中不存在key对应的entry时，新增
        if (entry == null) {
            //判断是否需要删除最老的节点
            if (hashMap.size() >= CACHE_SIZE) {
                hashMap.remove(tail.key);
                removeLast();
            }
            entry = new Entry();
            entry.key = key;
        }
        //修改
        entry.value = value;
        moveToFirst(entry);
        hashMap.put(key, entry);
    }
    /**
     * get方法，多线程加锁
     * @param key
     * @return
     */
    public synchronized V get(K key) {
        Entry<K, V> entry = hashMap.get(key);
        if (entry == null)
            return null;
        moveToFirst(entry);
        return entry.value;
    }
    /**
     * 删除
     * @param key
     */
    public synchronized void remove(K key) {
        Entry entry = getEntry(key);
        //从链表中删除
        if (entry != null) {
            if (entry.pre != null)
                entry.pre.next = entry.next;
            if (entry.next != null)
                entry.next.pre = entry.pre;
            if (entry == head)
                head = entry.next;
            if (entry == tail)
                tail = entry.pre;
        }
        //从HashMap中删除
        hashMap.remove(key);
    }
    //调整entry到链表头
    private void moveToFirst(Entry entry) {
        if (entry == head)
            return;
        if (entry.pre!= null)
            entry.pre.next = entry.next;
        if (entry.next != null)
            entry.next.pre = entry.pre;
        if (head == null || tail == null) {
            head = tail = entry;
            return;
        }
        entry.next = head;
        head.pre = entry;
        head = entry;
        entry.pre = null;
    }
    //移除链表尾的元素
    private void removeLast() {
        if (tail != null) {
            tail = tail.pre;
            if (tail == null)
                head = null;
            else
                tail.next = null;
        }
    }
    //从hashmap中获取key对应的Entry
    private Entry<K, V> getEntry(K key) {
        return hashMap.get(key);
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Entry entry = head;
        while (entry != null) {
            sb.append("").append(entry.key).append(":").append(entry.value).append("  ");
            entry = entry.next;
        }
        return sb.toString();
    }
    /**
     * Entry内部类，双链表实现
     * @param <K>
     * @param <V>
     */
    class Entry<K,V> {
        public Entry pre;
        public Entry next;
        public K key;
        public V value;
    }
    public static void main(String[] args) {
        LRUCache3<Integer, String> lruCache3 = new LRUCache3<>(5);
        for (int i = 0; i < 5; i++) {
            lruCache3.put(i,"" + i);
        }
        System.out.println(lruCache3.toString());
        lruCache3.put(5,"5");
        System.out.println(lruCache3.toString());
        lruCache3.get(2);
        System.out.println(lruCache3.toString());
        lruCache3.put(6,"6");
        System.out.println(lruCache3.toString());
        lruCache3.remove(4);
        System.out.println(lruCache3.toString());
    }
}

运行结果：

1
2
3
4
5
4:4  3:3  2:2  1:1  0:0  
5:5  4:4  3:3  2:2  1:1  
2:2  5:5  4:4  3:3  1:1  
6:6  2:2  5:5  4:4  3:3  
6:6  2:2  5:5  3:3

继承LinkedHashMap实现FIFO缓存

FIFO缓存只需要继承LinkedHashMap采用其默认的输出顺序就可以。

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
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * Created by cdx0312
 * 2018/4/3
 * 继承实现FIFO缓存
 */
public class FIFOCache<K, V> extends LinkedHashMap<K, V>{
    //缓存的大小
    private int cacheSize;
    //初始化时保证LinkedHashMap的初始大小要大于CacheSize+1，否则会发生扩容
    public FIFOCache(int cacheSize) {
        super(16, 0.75f);
        this.cacheSize = cacheSize;
    }
    /**
     * 重写该方法，当连表的size大于CacheSize时删除最新插入的元素
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<K, V> entry : entrySet()) {
            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        FIFOCache<String, String> f = new FIFOCache<>(6);
        for (int i = 0; i < 6; i++) {
            f.put(i+"", i * i + "");
        }
        System.out.println(f.toString());
        f.put("s", "s");
        System.out.println(f.toString());
        f.put("5", "2222");
        System.out.println(f.toString());
        f.get(1 + "");
        System.out.println(f.toString());
    }
}

输出结果：

1
2
3
4
0:0 1:1 2:4 3:9 4:16 5:25
1:1 2:4 3:9 4:16 5:25 s:s
1:1 2:4 3:9 4:16 5:2222 s:s
1:1 2:4 3:9 4:16 5:2222 s:s
Donate comment here