文档章节

LinkedHashMap源码解析

grace_233
 grace_233
发布于 11/14 00:26
字数 1067
阅读 8
收藏 0

前言

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

© 著作权归作者所有

共有 人打赏支持
grace_233
粉丝 5
博文 61
码字总数 25225
作品 0
浦东
程序员
私信 提问
LinkedHashMap原理分析

本文主要内容 LinkedHashMap使用 LinkedHashMap源码解析 Lru算法 今天打算看看android的图片缓存相关知识点,没想到引申到了LinkedHashMap容器了。 LinkedHashMap继承HashMap,相比于HashMap...

某昆
06/05
0
0
Java集合 --- LinkedHashMap底层实现和原理(源码解析)

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedHashMap,见...

起个名忒难
2017/09/24
0
0
Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap

这里我采用的分析方式是帖子博客加上自己翻看jdk源码。有些情况下写一些测试的算法小例子加深印象。我这里只描述一下自己的总结想法 上一篇文章我们研究了set接口下的几个容器,由于其Set集合...

贾浩v
2017/10/19
0
0
性能优化(2.3)-LruCache源码解析

主目录见:Android高级进阶知识(这是总目录索引)  今天我们来聊聊缓存策略相关的内容,LruCache应该说是三级缓存策略会使用到的内存缓存策略。今天我们就来扒一扒这里面的原理,同时也温故...

ZJ_Rocky
2017/11/16
0
0
Java中excel与对象的互相转换的通用工具类编写与使用(基于apache-poi-ooxml)

通用excel与对象相互转换的工具类 前言:最近开发需要一个Excel批量导入或者导出的功能,之前用过poi-ooxml开发过一个导入的工具类,正好蹭着这次机会,把工具类的功能进行完善。 使用说明:...

宇的季节
02/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS 官方文档

https://developer.apple.com/library/prerelease/content/navigation/#section=Platforms&topic=iOS...

walking_yxf
5分钟前
0
0
使用Mycat实现MySQL数据库的读写分离

前提准备 1.一台CentOS机器 2.Mycat安装包 (http://www.mycat.io/) 安装使用 1.解压Mycat的安装包到/user/local/下 2.设置mycat的环境变量 vi /etc/profile 3.使配置文件立即生效 source /...

吴伟祥
5分钟前
0
0
Aries数据库事务Recovery算法

背景知识 本文是一篇关于(分布式)数据库的文章,在开始阐述Aries是什么之前,需要先交代几个常识性的概念,这些概念对后文引出Aries显得尤为重要。 数据库体系结构 图1大致描述了一个(分布...

黑客画家
9分钟前
0
0
Rxjava Backpressure 32

原文:https://github.com/Froussios/Intro-To-RxJava/blob/master/Part 4 - Concurrency/4. Backpressure.md Rx将事件从管道的一端引导到另一端,在每一端发生的行动可能非常不同。当生产者...

woshixin
9分钟前
0
0
IDEA-Create Git Repository

1、概述 idea 开发完毕的项目没有及时的关联gitlab,如果整体项目关联gitlab。 2、干 2.1 gitlab 创建项目 2.2 idea 1、IDEA 点击 -> VCS -> import into version control -> create git re......

来来来来来
12分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部