前言
HashMap中的元素时无序的,也就是说遍历HashMap的时候,顺序和放入的顺序是不一样的。 如果需要有序的Map,就可以采用LinkedHashMap.
LinkedHashMap通过维护一个包含所有元素的双向链表,保证了元素迭代的顺序。该迭代顺序可以是插入顺序或者是访问顺序。
LinkedHashMap
注意: 以下的源码分析基于jdk1.7.
LinkedHashMap定义
LinkedHashMap 继承了HashMap, 也就是说LinkedHashMap的操作大部分和HashMap是相同的,只是有部分区别。
LinkedHashMap的属性相比于HashMap,多了两个属性:
header: 双端链表的头节点;(LinkedHashMap通过这个头节点来维护插入元素的先后顺序)
accessOrder: 迭代Map的顺序.true表示访问顺序,false表示插入顺序;默认是false。
LinkedHashMap.Entry
相比于hashMap.Entry多了两个属性:before,after
.
before、After是用于维护Entry在双端链表中的位置的。
LinkedHashMap的初始化
当new 一个LinkedHashMap,查看其构造方法(调用了父类HashMap的构造方法),构造方法中执行了LinkedHashMap重写的init方法:
init方法中初始化了双端链表的头节点。
LinkedHashMap的put方法
下面跟踪put方法,来看LinkedHashMap的插入逻辑。 首先执行父类HashMap的put()方法。
再看LinkedHashMap的addEntry方法:
先调用了父类HashMap的addEntry方法,进入HashMap的addEntry方法:
再进入LinkedHashMap的createEntry方法:
因此,如果连续插入三个entry,那么LinkedHashMap中的双端链表结构如下:
再看inkedHashMap的addEntry方法的后半段代码:
LinkedHashMap的get方法
查看LinkedHashMap的get方法:
这里面会调用LinkedHashMap.Entry的recordAccess方法,目的是根据acceessOrder(访问顺序) 来调整链表的位置。
调整链表的图示:
可见,最新被访问的元素,被放到了双端链表的最后面,也就是说,遍历的时候,这个元素会最后遍历。
LinkedHashMap的遍历方式
查看对应的Iterator类的nextEntry方法:
可知,LinkedHashMap遍历时是从head.after开始遍历,一直不断向后遍历after节点,来实现的。
总结
LinkedHashMap的遍历方式
1.按照插入顺序遍历;
2.按照最少访问顺序遍历。(也就是说刚被访问的元素被插入到链表最后面,最后遍历出来,而最老的元素最先遍历出来)
利用LinkedHashMap实现LRU算法
LRU算法
LRU(Least Recently Used),即最近最少使用的意思。
LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。
利用LinkedHashMap实现LRU算法
前面的源码分析中,在put元素的时候,LinkedHashMap中有一个removeEldestEntry方法,支持扩展,按照某种方式,在插入的时候,去移除最老的key, 因此根据LinkedHashMap的这个特性,可以实现LRU算法。 实现方式如下:
/**
* 实现一个简单版的LRU算法
*
* @author leiqian
*
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int CACHE_SIZE; // 缓存大小
public LRUCache(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > CACHE_SIZE; // 当map中的数据量大于指定的缓存个数的时候,就自动删除最老的数据
}
}
测试:
/**
* 测试LRUCache
*
* @author leiqian
*
*/
public class LRUCacheTest {
public static void print(Map<String, String> map) {
System.out.println("-----------------------");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + "," + entry.getValue());
}
}
public static void main(String[] args) {
LRUCache<String, String> map = new LRUCache<>(5);
map.put("k1", "v1");
map.put("k2", "v2");
map.put("k3", "v3");
map.put("k4", "v4");
map.put("k5", "v5");
map.put("k6", "v6");
print(map); // 应该移除了k1
map.get("k2");
map.put("k7", "v7");
print(map); // 应该移除了k3
map.get("k4");
map.put("k8", "v8");
print(map); // 应该移除了k5
}
}
另外,很多优秀的第三方框架都实现了LRUCache,可以看一下他们的源码中是怎么实现LRUCache的: