手写最近很少使用算法 lru
这道题在很多公司面试的时候都可能被问到, 主要考察面试者对缓存算法的原理的了解.
先来了解一下什么是最近很少使用算法?
最近很少使用算法: 就是根据最近访问的记录, 对缓存的数据进行淘汰. 也就是说, 如果一个数据最近被访问, 或经常被访问, 则把数据放到列表的前面. 而数据很久未访问, 或者访问率较低, 就会被放在对位, 在队列内存不足的时候将其移除缓存队列, 过程如图:
image
Android 中就带有 LruCache 的类, 这个类被广泛使用, 比如 glide 缓存图片就用到这个算法. 但是这个算法其实也没有那么复杂, 读过 LruCache 源码的同学都知道, 这个算法的底层实际上就是用了一个 LinkedHashMap. 我们需要了解的其实 LinkedHashMap 的原理.
LinkedHashMap:
大家都知道 HashMap 的原理, HashMap 内部维护单链表, 存储数据是无序的, 而我们 Lru 算法则有访问顺序的需求, 所以不能使用 HashMap, 这一点 LinkedHashMap 恰好能满足, LinkedHashMap 内部维护的是双向链表, 而且逻辑上实现了可以保证访问的顺序, 即: 每次访问或者插入数据的时候会被放到双向链表的尾部, 这个属性被激活需要设置 accessOrder 为 true 即可.
我们已经可以保证队列里面存储的值按照我们访问的顺序调整, 那我们实现 Lru 算法就可以很简单了.
但是还有一点, 因为我们的队列满了以后, 再存放数据的时候需要删除最少使用的值, 也就是链表首位的值 (每次访问或者插入数据的时候会被放到双向链表的尾部)
好, 总结一下如何实现 lru 算法:
accessOrder
上面两点中, 第一点 LinkedHashMap 已经实现我们只需要设置 accessOrder` 属性为 true 即可. 第二点需要我们去实现.
开始写代码:
初始化一个 LinkedHashMap, 设置 accessOrder` 属性为 true, 让它按照访问顺序排序, 并设置队列的最大容量 maxSize.
- public Lru(int maxSize) {
- if (maxSize <= 0) {
- throw new IllegalArgumentException("maxSize <= 0");
- }
- this.maxSize = maxSize;
- this.map = new LinkedHashMap(0, 0.75f, true);
- }
实现存储数据的逻辑. 每次存储一个数据, size 应该加 1. 这里面有个小技巧: HashMap 的 put 方法在添加一个之前已经存在的 key 的值的时候, 会覆盖以前的 key 对应 value, 并返回以前的 value, 如: V previous = map.put(key, value) 之后 previous 不为 null, 则说明这个 key 之前就已经有值, 再次添加值只是覆盖以前的值, 所以这时候 size 不应该加 1.
- public V put(K key, V value) {
- if (key == null || value == null) {
- throw new NullPointerException("key == null || value == null");
- }
- V previous;
- synchronized (this) {
- // 这是 HashMap 的属性: 如果 key 之前已经存有值, 则这里会返回之前的值.
- previous = map.put(key, value);
- // 如果之前已经存在值, 则我们添加的值会把以前的值覆盖, 所以 size 就不会增加, 如果之前不存在值, 这里添加数据就会增加一个 size
- if (previous == null) {
- size += 1;
- }
- }
- // 存放数据, 删除多余数据
- trimToSize(maxSize);
- return previous;
- }
添加数据的时候应该注意数据是否超出容量了, 如果超出了, 就应该删除最少使用的数据. 这里使用循环删除最少使用的数据, 直到 size<=maxSize.
- // 如果 size>maxSize, 则删除多余的数据
- private void trimToSize(int maxSize) {
- while (true) {
- K key;
- synchronized (this) {
- if (size < 0 || (map.isEmpty() && size != 0)) {
- return;
- }
- if (size <= maxSize || map.isEmpty()) {
- break;
- }
- Map.Entry toEvict = map.entrySet().iterator().next();
- key = toEvict.getKey();
- map.remove(key);
- size -= 1;
- }
- }
- }
获取一个数据, 也就是访问数据, LinkedHashMap 会自动把访问的数据放到链表的尾部, 所以这里我们不用太操心
- // 获取一个数据
- public V get(K key) {
- if (key == null) {
- throw new NullPointerException("key == null");
- }
- V mapValue;
- synchronized (this) {
- mapValue = map.get(key);
- if (mapValue != null) {
- return mapValue;
- }
- }
- return null;
- }
清空数据就更简单了, 我们既可以直接调用 linkedhashmap 的 clear 方法清空队列, 也可以利用我们上面写的循环删除的方法, 只要把 maxSize 参数设置为 - 1, 就可以清空队列里面的数据:
- // 清除空数据
- public void evictAll() {
- //map.clear();
- trimToSize(-1);
- }
以上 我们已经实现了 lru 的基本操作. 只要同学知道 LruCache 的原理, 这个代码不难写出来.
一下是完整代码:(总体思想来自 LruCache)
- public class Lru {
- private final LinkedHashMap map;
- private int size;
- private int maxSize;
- public Lru(int maxSize) {
- if (maxSize <= 0) {
- throw new IllegalArgumentException("maxSize <= 0");
- }
- this.maxSize = maxSize;
- this.map = new LinkedHashMap(0, 0.75f, true);
- }
- public V get(K key) {
- if (key == null) {
- throw new NullPointerException("key == null");
- }
- V mapValue;
- synchronized (this) {
- mapValue = map.get(key);
- if (mapValue != null) {
- return mapValue;
- }
- }
- return null;
- }
- public V put(K key, V value) {
- if (key == null || value == null) {
- throw new NullPointerException("key == null || value == null");
- }
- V previous;
- synchronized (this) {
- size += 1;
- previous = map.put(key, value);
- if (previous != null) {
- size -= 1;
- }
- }
- trimToSize(maxSize);
- return previous;
- }
- private void trimToSize(int maxSize) {
- while (true) {
- K key;
- synchronized (this) {
- if (size < 0 || (map.isEmpty() && size != 0)) {
- return;
- }
- if (size <= maxSize || map.isEmpty()) {
- break;
- }
- Map.Entry toEvict = map.entrySet().iterator().next();
- key = toEvict.getKey();
- map.remove(key);
- size -= 1;
- }
- }
- }
- public V remove(K key) {
- if (key == null) {
- throw new NullPointerException("key == null");
- }
- V previous;
- synchronized (this) {
- previous = map.remove(key);
- if (previous != null) {
- size -= 1;
- }
- }
- return previous;
- }
- public void evictAll() {
- trimToSize(-1);
- }
- public synchronized int size() {
- return size;
- }
- public synchronized int maxSize() {
- return maxSize;
- }
- }
来源: http://www.jianshu.com/p/d1641ded989f