概述
LinkedHashMap是Java中常用的数据结构之一，安卓中的LruCache缓存，底层使用的就是LinkedHashMap，LRU（Least Recently Used）算法，即最近最少使用算法，核心思想就是当缓存满时，会优先淘汰那些近期最少使用的缓存对象
LruCache的缓存算法
LruCache采用的缓存算法为LRU（Least Recently Used），最近最少使用算法。核心思想是当缓存满时，会首先把那些近期最少使用的缓存对象淘汰掉
LruCache的实现
LruCache底层就是用LinkedHashMap来实现的。提供 get 和 put 方法来完成对象的添加和获取
LinkedHashMap与HashMap的区别
1相同点： 21. 都是key,value进行添加和获取 32. 底层都是使用数组来存放数据 4 5不同点： 61. HashMap是无序的，LinkedHashMap是有序的（插入顺序和访问顺序） 72. LinkedHashMap内存的节点存放在数据中，但是节点内部有两个指针，来完成双向链表的操作，来保证节点插入顺序或者访问顺序
LinkedHashMap的使用
LinkedHashMap插入顺序的演示代码
1 public static void main(String[] args) { 2 3 //默认记录的就是插入顺序 4 Map<String, String> map = new LinkedHashMap<>(); 5 map.put("name", "tom"); 6 map.put("age", "34"); 7 map.put("address", "beijing"); 8 9 Iterator iterator = map.entrySet().iterator(); 10 11 //遍历 12 while (iterator.hasNext()) { 13 Map.Entry entry = (Map.Entry) iterator.next(); 14 String key = (String) entry.getKey(); 15 String value = (String) entry.getValue(); 16 System.out.println("Key = " + key + ", Value = " + value); 17 } 18 }
输出如下：
1Key = name, Value = tom 2Key = age, Value = 34 3Key = address, Value = beijing
由输出可以看到 我们往LinedHashMap中分别按顺序插入了name,age,address以及对应的value 遍历的时候，也是按顺序分别输出了 name,age,address以及对应的value 所以可以，LinkedHashMap默认记录的就是插入的顺序
作为比较，我们再看来一下 HashMap 的遍历是不是有序的。就以上面这几个值为例 代码以及输出如下：
HashMap的遍历
1 public static void main(String[] args) { 2 3 //插入和上面一样的值 4 Map<String, String> map = new HashMap<>(); 5 map.put("name", "tom"); 6 map.put("age", "34"); 7 map.put("address", "beijing"); 8 9 Iterator iterator = map.entrySet().iterator(); 10 11 //遍历 12 while (iterator.hasNext()) { 13 Map.Entry entry = (Map.Entry) iterator.next(); 14 String key = (String) entry.getKey(); 15 String value = (String) entry.getValue(); 16 System.out.println("Key = " + key + ", Value = " + value); 17 } 18 }
输出如下
1Key = address, Value = beijing 2Key = name, Value = tom 3Key = age, Value = 34
从上面可以得知:
- HashMap遍历的时候，是无序的，和插入的顺序是不相关的。
- LinkedHashMap默认的顺序是记录插入顺序
既然LinkedHashMap默认是按着插入顺序的，那么肯定也有其它的顺序。 对的，LinkedHashMap还可以记录访问的顺序。访问过的元素放在链表前面 遍历的时候最近访问的元素最后才遍历到
LinkedHashMap的访问顺序的演示代码
1 public static void main(String[] args) { 2 3 /** 4 * 第一个参数：数组的大小 5 * 第二个参数：扩容因子，和HashMap一样，添加的元素的个数达到 16 * 0.75时，开始扩容 6 * 第三个参数：true:表示记录访问顺序 7 * false:表示记录插入顺序（默认的顺序） 8 */ 9 Map<String, String> map = new LinkedHashMap<>(16,0.75f,true); 10 11 //分别插入下面几个值 12 map.put("name", "tom"); 13 map.put("age", "34"); 14 map.put("address", "beijing"); 15 16 //既然演示访问顺序，我们就访问其中一个元素，这里只是打印一下 17 System.out.println("我是被访问的元素：" + map.get("age")); 18 19 //访问完后，我们再遍历，注意输出的顺序 20 Iterator iterator = map.entrySet().iterator(); 21 //遍历 22 while (iterator.hasNext()) { 23 Map.Entry entry = (Map.Entry) iterator.next(); 24 String key = (String) entry.getKey(); 25 String value = (String) entry.getValue(); 26 System.out.println("Key = " + key + ", Value = " + value); 27 } 28 }
输出如下：
1我是被访问的元素：34 2Key = name, Value = tom 3Key = address, Value = beijing 4Key = age, Value = 34
从上面可以得知： 插入元素完成之后，我们访问了age，并打印其值 之后再遍历，因为记录的是访问顺序，LinkedHashMap会把最近使用的元素放到最后面，所以遍历的时候，本来age是第二次插入的，但是遍历的时候，却是最后一个遍历出来的。
LruCache就是利用了LinkedHashMap的这种性质，最近使用的元素都放在最后 最近不使用的元素自然就在前面，所以缓存满了的时候，删除前面的。新添加元素的时候放在最后面
LinkedHashMap的原理
LinkedHashMap，望文生义 Link + HashMap，Link就链表 所以LinkedHashMap就是底层使用数组存放元素，使用链表维护插入元素的顺序
使用一张图来说明LinkedHashMap的原理
LinkedHashMap中的节点如下图
下面我们就来手写这样一个结构QLinkedHashMap
首先定义节点的结构，我们就叫QEntry,如下
1 static class QEntry<K, V> { 2 public K key; //key 3 public V value; //value 4 public int hash; //key对应的hash值 5 public QEntry<K, V> next; //hash冲突时，构成一个单链表 6 7 public QEntry<K, V> before; //当前节点的前一个节点 8 public QEntry<K, V> after; //当前节点的后一个节点 9 10 11 QEntry(K key, V value, int hash, QEntry<K, V> next) { 12 this.key = key; 13 this.value = value; 14 this.hash = hash; 15 this.next = next; 16 } 17 18 //删除当前节点 19 private void remove() { 20 //当前节点的上一个节点的after指向当前节点的下一个节点 21 this.before.after = after; 22 //当前节点的下一个节点的before指向当前节点的上一个节点 23 this.after.before = before; 24 } 25 26 //将当前节点插入到existingEntry节点之前 27 private void addBefore(QEntry<K, V> existingEntry) { 28 29 //插入到existingEntry前，那么当前节点后一个节点指向existingEntry 30 this.after = existingEntry; 31 32 //当前节点的上一个节点也需要指向existingEntry节点的上一个节点 33 this.before = existingEntry.before; 34 35 //当前节点的下一个节点的before也得指向自己 36 this.after.before = this; 37 38 //当前节点的上一个节点的after也得指向自己 39 this.before.after = this; 40 } 41 42 //访问了当前节点时，会调用这个函数 43 //在这里面就会处理访问顺序和插入顺序 44 void recordAccess(QLinkedHashMap<K, V> m) { 45 QLinkedHashMap<K, V> lm = (QLinkedHashMap<K, V>) m; 46 47 //如果accessOrder为true，也就是访问顺序 48 if (lm.accessOrder) { 49 50 //把当前节点从链表中删除 51 remove(); 52 53 //再把当前节点插入到双向链表的尾部 54 addBefore(lm.header); 55 } 56 } 57 }
我们的QLinkedHashMap中的链表用的是双向循环链表
如图下：
由上图可以知道，图中是一个双向链表，头节点和A,B两个链表 其中 header.before指向最后一个节点 header.after 指向header节点
其中 QLinkedHashMap的大部分代码和手写Java HashMap核心源码 一样。 可以先看看手写Java HashMap核心源码一章节
QLinkedHashMap全部源码以及注释如下：
1public class QLinkedHashMap<K, V> { 2 private static int DEFAULT_INITIAL_CAPACITY = 16; //默认数组的大小 3 private static float DEFAULT_LOAD_FACTOR = 0.75f; //默认的扩容因子 4 5 private QEntry[] table; //底层的数组 6 private int size; //数量 7 8 9 //下面这两个属性是给链表用的 10 11 //true:表示按着访问的顺序保存 false:按照插入的顺序保存（默认的方式） 12 private boolean accessOrder; 13 14 //双向循环链表的表头,记住，这里只有一个头指针，没有尾指针 15 //所以需要用循环链表来实现双向链表 16 //即：从前可以往后遍历，也可以从后往前遍历 17 private QEntry<K, V> header; 18 19 20 public QLinkedHashMap() { 21 //创建DEFAULT_INITIAL_CAPACITY大小的数组 22 table = new QEntry[DEFAULT_INITIAL_CAPACITY]; 23 size = 0; 24 25 //默认按照插入的顺序保存 26 accessOrder = false; 27 28 //初始化 29 init(); 30 } 31 32 /** 33 * 34 * @param capcacity 数组的大小 35 * @param accessOrder 按照何种顺序保存 36 */ 37 public QLinkedHashMap(int capcacity, boolean accessOrder) { 38 table = new QEntry[capcacity]; 39 size = 0; 40 41 this.accessOrder = accessOrder; 42 init(); 43 } 44 45 //这里主要是初始化双向循环链表 46 private void init() { 47 //新建一个表头 48 header = new QEntry<>(null, null, -1, null); 49 50 //链表为空的时候，只有一个头节点，所以头节点的下一个指向自己，上一个节点也指向自己 51 header.after = header; 52 header.before = header; 53 } 54 55 //插入一个键值对 56 public V put(K key, V value) { 57 if (key == null) 58 throw new IllegalArgumentException("key is null"); 59 60 //拿到key的hash值 61 int hash = hash(key.hashCode()); 62 //存在数组中的哪个位置 63 int i = indexFor(hash, table.length); 64 65 //看看有没有key是一样的，如果有，替换掉旧掉，把新值保存起来 66 //如调用了两次 map.put("name","tom"); 67 // map.put("name","jim"); ，那么最新的name对应的value就是jim 68 QEntry<K, V> e = table[i]; 69 while (e != null) { 70 //查看有没有相同的key,如果有就保存新值，返回旧值 71 if (e.hash == hash && (key == e.key || key.equals(e.key))) { 72 V oldValue = e.value; 73 e.value = value; 74 75 //重点就是这一句，找到了相同的节点,也就是访问了一次 76 //如果accessOrder是true，就要把这个节点放到链表的尾部 77 e.recordAccess(this); 78 79 //返回旧值 80 return oldValue; 81 } 82 83 //继续下一个循环 84 e = e.next; 85 } 86 87 //如果没有找到与key相同的键 88 //新建一个节点，放到当前 i 位置的节点的前面 89 QEntry<K, V> next = table[i]; 90 QEntry newEntry = new QEntry(key, value, hash, next); 91 92 //保存新的节点到 i 的位置 93 table[i] = newEntry; 94 95 //把新节点添加到双向循环链表的头节点的前面， 96 //记住，添加到header的前面就是添加到链表的尾部 97 //因为这是一个双向循环链表，头节点的before指向链表的最后一个节点 98 //链表的最后一个节点的after指向header节点 99 //刚开始我也以为是添加到了链表的头部，其实不是，是添加到了链表的尾部 100 //这点可以参考图好好想想 101 newEntry.addBefore(header); 102 103 //别忘了++ 104 size++; 105 106 return null; 107 } 108 109 //根据key获取value，也就是对节点进行访问 110 public V get(K key) { 111 112 //同样为了简单，key不支持null 113 if (key == null) { 114 throw new IllegalArgumentException("key is null"); 115 } 116 117 //对key进行求hash值 118 int hash = hash(key.hashCode()); 119 120 //用hash值进行映射，得到应该去数组的哪个位置上取数据 121 int index = indexFor(hash, table.length); 122 123 //把index位置的元素保存下来进行遍历 124 //因为e是一个链表，我们要对链表进行遍历 125 //找到和key相等的那个QEntry，并返回value 126 QEntry<K, V> e = table[index]; 127 while (e != null) { 128 129 //看看数组中是否有相同的key 130 if (hash == e.hash && (key == e.key || key.equals(e.key))) { 131 132 //访问到了节点，这句很重要，如果有相同的key，就调用recordAccess() 133 e.recordAccess(this); 134 135 //返回目标节点的值 136 return e.value; 137 } 138 139 //继续下一个循环 140 e = e.next; 141 } 142 143 //没有找到 144 return null; 145 } 146 147 //返回一个迭代器类，遍历用 148 public QIterator iterator(){ 149 return new QIterator(header); 150 } 151 152 //根据 h 求key落在数组的哪个位置 153 static int indexFor(int h, int length) { 154 //或者 return h & (length-1) 性能更好 155 //这里我们用最容易理解的方式，对length取余数，范围就是[0,length - 1] 156 //正好是table数组的所有的索引的范围 157 158 h = h > 0 ? h : -h; //防止负数 159 160 return h % length; 161 } 162 163 //对hashCode进行运算，JDK中HashMap的实现，直接拷贝过来了 164 static int hash(int h) { 165 h ^= (h >>> 20) ^ (h >>> 12); 166 return h ^ (h >>> 7) ^ (h >>> 4); 167 } 168 169 //定义一个迭代器类，方便遍历用 170 public class QIterator { 171 QEntry<K,V> header; //表头 172 QEntry<K,V> p; 173 174 public QIterator(QEntry header){ 175 this.header = header; 176 this.p = header.after; 177 } 178 179 //是否还有下一个节点 180 public boolean hasNext() { 181 //当 p 不等于 header的时候，说明还有下一个节点 182 return p != header; 183 } 184 185 //如果有下一个节点，获取之 186 public QEntry next() { 187 QEntry r = p; 188 p = p.after; 189 return r; 190 } 191 } 192 193 static class QEntry<K, V> { 194 public K key; //key 195 public V value; //value 196 public int hash; //key对应的hash值 197 public QEntry<K, V> next; //hash冲突时，构成一个单链表 198 199 public QEntry<K, V> before; //当前节点的前一个节点 200 public QEntry<K, V> after; //当前节点的后一个节点 201 202 203 QEntry(K key, V value, int hash, QEntry<K, V> next) { 204 this.key = key; 205 this.value = value; 206 this.hash = hash; 207 this.next = next; 208 } 209 210 //删除当前节点 211 private void remove() { 212 //当前节点的上一个节点的after指向当前节点的下一个节点 213 this.before.after = after; 214 //当前节点的下一个节点的before指向当前节点的上一个节点 215 this.after.before = before; 216 } 217 218 //将当前节点插入到existingEntry节点之前 219 private void addBefore(QEntry<K, V> existingEntry) { 220 221 //插入到existingEntry前，那么当前节点后一个节点指向existingEntry 222 this.after = existingEntry; 223 224 //当前节点的上一个节点也需要指向existingEntry节点的上一个节点 225 this.before = existingEntry.before; 226 227 //当前节点的下一个节点的before也得指向自己 228 this.after.before = this; 229 230 //当前节点的上一个节点的after也得指向自己 231 this.before.after = this; 232 } 233 234 //访问了当前节点时，会调用这个函数 235 //在这里面就会处理访问顺序和插入顺序 236 void recordAccess(QLinkedHashMap<K, V> m) { 237 QLinkedHashMap<K, V> lm = (QLinkedHashMap<K, V>) m; 238 239 //如果accessOrder为true，也就是访问顺序 240 if (lm.accessOrder) { 241 242 //把当前节点从链表中删除 243 remove(); 244 245 //再把当前节点插入到双向链表的尾部 246 addBefore(lm.header); 247 } 248 } 249 } 250}
上面就是QLinkedHashMap的全部源码。 扩容以及删除功能我们没有写，有兴趣的读者可以自己实现一下。
我们写一段代码来测试，如下：
1 public static void main(String[] args){ 2 //新建一个默认的构造函数，默认是按照插入顺序保存 3 QLinkedHashMap<String,String> map = new QLinkedHashMap<>(); 4 map.put("name","tom"); 5 map.put("age","32"); 6 map.put("address","beijing"); 7 8 //验证是不是按照插入的顺序打印 9 QLinkedHashMap.QIterator iterator = map.iterator(); 10 while (iterator.hasNext()){ 11 QEntry e = iterator.next(); 12 System.out.println("key=" + e.key + " value=" + e.value); 13 } 14 }
输出如下：
1key=name value=tom 2key=age value=32 3key=address value=beijing
可以看到我们输出的时候，是按照插入的顺序输出的。
我们再稍微改一下代码，只需要改QLinkedHashMap的构造函数即可 代码如下：
1 public static void main(String[] args){ 2 //新建一个大小为16，顺序是访问顺序的 map 3 QLinkedHashMap<String,String> map = new QLinkedHashMap<>(16,true); 4 5 //分别插入以下键值对 6 map.put("name","tom"); 7 map.put("age","32"); 8 map.put("address","beijing"); 9 10 //访问其中一个元素，这里什么也不做 11 //访问了age,那么打印的时候，age应该是最后一个打印的 12 map.get("age"); 13 14 15 //验证是不是按照访问顺序打印，age是不是最后一个打印 16 QLinkedHashMap.QIterator iterator = map.iterator(); 17 while (iterator.hasNext()){ 18 QEntry e = iterator.next(); 19 System.out.println("key=" + e.key + " value=" + e.value); 20 } 21 }
输出如下：
1key=name value=tom 2key=address value=beijing 3key=age value=32
由上可以，我们实现了可以以插入顺序和访问顺序的HashMap。 虽然没有实现扩容机制和删除。但足以提示QLinkedHashMap的核心原理。