在之前讲LinkedHashMap的时候,我们说起可以用来实现LRU(least recent used)算法,接下来我看一下其中的一个具体实现-----android sdk 中的LruCache.
关于Lru算法,请参考漫画:什么是LRU算法?
talk is cheap, I am gonna show you something really expensive.
1package android.util;// 该类是从Android sdk 中摘录 2 3public class LruCache<K, V> { 4 5 private final LinkedHashMap<K, V> map;// 这里的 LinkedHashMap 为 android.jar 中的类,与jdk中的有所区别,这里不做区分 6 private int size;// 当前 cache 的大小 7 private int maxSize;// cache 最大容量 8 private int putCount;// put() 调用的次数 9 private int createCount;// get()未命中,成功构建新 key:value 的次数 10 private int evictionCount;// 因cache大小超过容量限制,将 key:value 从 cache 中驱逐的次数 11 private int hitCount;// get()命中的次数 12 private int missCount;// get()未命中的次数 13 14 // 构造时设置最大容量 15 public LruCache(int maxSize) { 16 if (maxSize <= 0) { 17 throw new IllegalArgumentException("maxSize <= 0"); 18 } 19 this.maxSize = maxSize; 20 // 这里传入的 LinkedHashMap 的 accessOrder 为true,表示 其中的链表中的结点顺序为 "按访问顺序" 21 this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 22 } 23 24 // 重新设置 cache 最大容量 25 public void resize(int maxSize) { 26 if (maxSize <= 0) { 27 throw new IllegalArgumentException("maxSize <= 0"); 28 } 29 synchronized (this) { 30 this.maxSize = maxSize; 31 } 32 trimToSize(maxSize); 33 } 34 35 public final V get(K key) { 36 if (key == null) { 37 throw new NullPointerException("key == null"); 38 } 39 V mapValue; 40 synchronized (this) {// 同步访问 41 mapValue = map.get(key); 42 if (mapValue != null) { 43 hitCount++;// 命中次数 + 1 44 return mapValue; 45 } 46 missCount++;// 未命中次数 + 1 47 } 48 V createdValue = create(key);// 通过 key 构建一个value(比如从文件中读入value) 49 if (createdValue == null) {// 创建失败 50 return null; 51 } 52 synchronized (this) { 53 createCount++;// 构建 value 成功次数 + 1 54 mapValue = map.put(key, createdValue);// 添加到 LinkedHashMap 中 55 if (mapValue != null) { 56 // LinkedHashMap 原来有该key的值(在构建value的时候,被其他线程添加进去的),这里重新把原来的值放进去,cache大小没有增加 57 map.put(key, mapValue); 58 } else { 59 size += safeSizeOf(key, createdValue);// cache 大小增加 60 } 61 } 62 if (mapValue != null) { 63 entryRemoved(false, key, createdValue, mapValue); 64 return mapValue; 65 } else { 66 trimToSize(maxSize);// 大小增加了,保证在最大容量范围内 67 return createdValue; 68 } 69 } 70 71 public final V put(K key, V value) { 72 if (key == null || value == null) { 73 throw new NullPointerException("key == null || value == null"); 74 } 75 V previous; 76 synchronized (this) { 77 putCount++;// put 次数 78 size += safeSizeOf(key, value); 79 previous = map.put(key, value); 80 if (previous != null) { 81 size -= safeSizeOf(key, previous);// 替换已有的value 82 } 83 } 84 if (previous != null) { 85 entryRemoved(false, key, previous, value); 86 } 87 trimToSize(maxSize); 88 return previous; 89 } 90 91 // 移除LRU键值对,保证 cache 的大小在 maxSize 范围内 92 public void trimToSize(int maxSize) { 93 while (true) { 94 K key; 95 V value; 96 synchronized (this) { 97 if (size < 0 || (map.isEmpty() && size != 0)) { 98 throw new IllegalStateException(getClass().getName() 99 + ".sizeOf() is reporting inconsistent results!"); 100 } 101 if (size <= maxSize) { 102 break; 103 } 104 Map.Entry<K, V> toEvict = map.eldest();// 最老的结点,返回head结点,也即 LRU结点 105 if (toEvict == null) {// 没有可以删除的key:value了 106 break; 107 } 108 key = toEvict.getKey(); 109 value = toEvict.getValue(); 110 map.remove(key); 111 size -= safeSizeOf(key, value);// 大小降低 112 evictionCount++;// 驱逐次数 + 1 113 } 114 entryRemoved(true, key, value, null); 115 } 116 } 117 118 public final V remove(K key) { 119 if (key == null) { 120 throw new NullPointerException("key == null"); 121 } 122 V previous; 123 synchronized (this) { 124 previous = map.remove(key);// 通过 LinkedHashMap 移除 125 if (previous != null) { 126 size -= safeSizeOf(key, previous);// cache总大小降低 127 } 128 } 129 if (previous != null) { 130 entryRemoved(false, key, previous, null); 131 } 132 return previous; 133 } 134 135 // key:oldValue 被 移除 或 驱逐 时回调 136 protected void entryRemoved(boolean evicted/*是否是被驱逐(因cache大小超过容量限制被删除)*/, 137 K key, V oldValue, V newValue) { 138 } 139 140 // 根据指定 key,构建 value 141 protected V create(K key) { 142 return null; 143 } 144 145 private int safeSizeOf(K key, V value) { 146 int result = sizeOf(key, value); 147 if (result < 0) { 148 throw new IllegalStateException("Negative size: " + key + "=" + value); 149 } 150 return result; 151 } 152 153 // key:value 键值对大小,用于计算cache大小 154 // 可根据情况自定义,默认为 1 155 // 该 key:value 在 cache 中时大小不应该变化 156 protected int sizeOf(K key, V value) { 157 return 1; 158 } 159 160 public final void evictAll() { 161 trimToSize(-1); // -1 will evict 0-sized elements 162 } 163 164 // 各种方法,返回成员变量,省略 165 public synchronized final Map<K, V> snapshot() { 166 return new LinkedHashMap<K, V>(map); 167 } 168 169 @Override 170 public synchronized final String toString() { 171 int accesses = hitCount + missCount; 172 int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0; 173 return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 174 maxSize, hitCount, missCount, hitPercent); 175 } 176 177}