LRU缓存机制

发表于

算法：LRU缓存机制-最近最少使用



题目—— LRU缓存机制

url：https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

分析

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

实现方式：

一个k-v字典存储 数据，同时存储每个item的上次访问时间lru_time，当容量满时，淘汰最lru_time最早的；


Java解法

使用HashMap存储数据，使用优先级队列PriorityQueue存储最近访问时间

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
class LruObj {
	Integer key;
	Long time;
	public LruObj(Integer key, Long time) {
		this.key = key; this.time=time;
	}
	@Override
	public int hashCode() {
		int result = key.hashCode();
		return result;
	}
	@Override
	public boolean equals(Object o) {
		if(this==o) return true;
		if(null==o || getClass() != o.getClass()) return false;
		LruObj lruObj = (LruObj) o;
		return key.equals(lruObj.key);
	}
}
class LRUCache {
	private int capacity = 0;
	PriorityQueue<LruObj> queue =
			new PriorityQueue<LruObj>((a,b)->(a.time-b.time>0) ? 1 : -1);
	HashMap<Integer, Integer> map = new HashMap<>();
	public LRUCache(int capacity) {
		this.capacity = capacity;
	}
	public int get(int key) {
		if(map.containsKey(key)) {
			LruObj obj = new LruObj(key, System.nanoTime());
			queue.remove(obj); queue.offer(obj);
			return map.get(key);
		}
		return -1;
	}
	public void put(int key, int value) {
		LruObj obj = new LruObj(key, System.nanoTime());
		if(map.containsKey(key)) {
			queue.remove(obj); queue.offer(obj);
			map.put(key, value);
		} else {
			if(queue.size() >= this.capacity && queue.size() > 0) {
				LruObj tmp = queue.poll();
				map.remove(tmp.key);
			}
			queue.offer(obj);
			map.put(key, value);
		}
	}
}
public class App {
	public static void main(String[] agrs) {
		LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
		cache.put(1, 1);
		cache.put(2, 2);
		System.out.println(cache.get(1));       // 返回  1
		cache.put(3, 3);    // 该操作会使得密钥 2 作废
		System.out.println(cache.get(2));       // 返回 -1 (未找到)
		cache.put(4, 4);    // 该操作会使得密钥 1 作废
		System.out.println(cache.get(1));       // 返回 -1 (未找到)
		System.out.println(cache.get(3));       // 返回  3
		System.out.println(cache.get(4));       // 返回  4
	}
}

官方答案：

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
class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}
public class App {
	public static void main(String[] agrs) {
		LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
		cache.put(1, 1);
		cache.put(2, 2);
		System.out.println(cache.get(1));       // 返回  1
		cache.put(3, 3);    // 该操作会使得密钥 2 作废
		System.out.println(cache.get(2));       // 返回 -1 (未找到)
		cache.put(4, 4);    // 该操作会使得密钥 1 作废
		System.out.println(cache.get(1));       // 返回 -1 (未找到)
		System.out.println(cache.get(3));       // 返回  3
		System.out.println(cache.get(4));       // 返回  4
	}
}

LinkedHashMap内部实现方式 是 LinkedList + HashMap