自制一个指定容量缓存，并实现最近使用的最后删除

需求

• 实现一个缓存key-value结构，并设定容量最大值，
• 当put进去的时候，如果超过最大容量，则将最早放进去的删除
• 当get的时候，返回key值，并将key放到后面（表示最近使用过，最后删除）

上代码

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 实现一个缓存key-value结构，并设定容量最大值，
 * 当put进去的时候，如果超过最大容量，则将最早放进去的删除
 * 当get的时候，返回key值，并将key放到后面（表示最近使用过，最后删除）
 */
public class LRUCache {
        private Map<String, Object> cache;
	    private Deque<String> deque;
	    private int capacity;

        public LRUCache(int capacity) {
	        this.capacity = capacity;
	        this.cache = new HashMap<>();
	        this.deque = new LinkedList<>();
	    }

        public Object get(String key) {
	        if (!cache.containsKey(key)) {
	            return -1;
	        }
	        deque.remove(key); // 删掉原key，将其移到队列尾
	        deque.offerLast(key);
	        return cache.get(key);
	    }

        public void put(String key, Object value) {
	        if (cache.containsKey(key)) {
	            deque.remove(key); // 删掉原key，将其移到队列尾
	        } else if (cache.size() >= capacity) {
	            String removed = deque.pollFirst(); // 移除队首（最久未使用）
	            cache.remove(removed);
	        }
	        cache.put(key, value);
	        deque.offerLast(key);
	    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "cache=" + cache +
                ", deque=" + deque +
                ", capacity=" + capacity +
                '}';
    }
}

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

测试效果

public class LRUCacheTest {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put("aa", "aa");
        lruCache.put("bb", "bb");
        lruCache.put("cc", "cc");
        lruCache.put("dd", "dd");
        lruCache.put("ee", "ee");
        System.out.println(lruCache);
        lruCache.get("aa");
        System.out.println(lruCache);
        lruCache.put("ff", "ff");
        System.out.println(lruCache);
        
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结果：