LinkedHashMap源码解析

原创
2018/11/14 00:26
阅读数 97

前言

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的:

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部