设为首页 加入收藏

TOP

LinkedHashMap如何保证顺序性
2019-08-14 00:08:25 】 浏览:64
Tags:LinkedHashMap 如何 保证 顺序

先看一个例子,我们想在页面展示一周内的消费变化情况,用echarts面积图进行展示。如下:


我们在后台将数据构造完成


然而页面上一展示,发现并非如此,我们打印出来看,发现顺序并非我们所想,先put进去的先get出来


那么如何保证预期展示结果如我们所想呢,这个时候就需要用到LinkedHashMap实体。


首先我们把上述代码用LinkedHashMap进行重构


这个时候,结果正如我们所预期


LinkedHashMap继承了HashMap类,是HashMap的子类,LinkedHashMap的大多数方法的实现直接使用了父类HashMap的方法,关于HashMap在前面的章节已经讲过了,《HashMap原理(一) 概念和底层架构》《HashMap原理(二) 扩容机制及存取原理》


LinkedHashMap可以说是HashMap和LinkedList的集合体,既使用了HashMap的数据结构,又借用了LinkedList双向链表的结构(关于LinkedList可参考Java集合 LinkedList的原理及使用),那么这样的结构如何实现的呢,我们看一下LinkedHashMap的类结构


我们看到LinkedHashMap中定义了一个Entry静态内部类,定义了5个构造器,一些成员变量,如head,tail,accessOrder,并继承了HashMap的方法,同时实现了一些迭代器方法。我们先看一下Entry类


我们看到这个静态内部类很简单,继承了HashMap的Node内部类,我们知道Node类是HashMap的底层数据结构,实现了数组+链表/红黑树的结构,而Entry类保留了HashMap的数据结构,同时通过before,after实现了双向链表结构(HashMap中Node类只有next属性,并不具备双向链表结构)。那么before,after和next到底什么关系呢。


看上面的结构图,定义了头结点head,当我们调用迭代器进行遍历时,通过head开始遍历,通过before属性可以不断找到下一个,直到tail尾结点,从而实现顺序性。而在同一个hash(在上图中表现了同一行)链表内部after和next效果是一样的。不同点在于before和after可以连接不同hash之间的链表。


前面我们发现数据结构已经完全支持其顺序性了,接下来我们再看一下构造方法,看一下比起HashMap的构造方法是否有不同。


我们发现除了多了一个变量accessOrder之外,并无不同,此变量到底起了什么作用?


通过注释发现该变量为true时access-order,即按访问顺序遍历,如果为false,则表示按插入顺序遍历。默认为false,在哪些地方使用到该变量了,同时怎么理解?我们可以看下面的方法介绍


前面我们提到LinkedHashMap的put方法沿用了父类HashMap的put方法,但我们也提到了像LinkedHashMap的Entry类就是继承了HashMap的Node类,同样的,HashMap的put方法中调用的其他方法在LinkedHashMap中已经被重写。我们先看一下HashMap的put方法,这个在《HashMap原理(二) 扩容机制及存取原理》中已经有说明,我们主要关注于其中的不同点


首先:LinkedHashMap重写了newNode()方法,通过此方法保证了插入的顺序性。


其次:关于afterNodeAccess()方法,在HashMap中没给具体实现,而在LinkedHashMap重写了,目的是保证操作过的Node节点永远在最后,从而保证读取的顺序性,在调用put方法和get方法时都会用到。


我们前面说到的linkNodeLast(Entry e)方法和现在的afterNodeAccess(Node e)都是将传入的Node节点放到最后,那么它们的使用场景如何呢?


在前面讲解HashMap时,提到了HashMap的put流程,如果在对应的hash位置上还没有元素,那么直接new Node()放到数组table中,这个时候对应到LinkedHashMap中,调用了newNode()方法,就会用到linkNodeLast(),将新node放到最后,而如果对应的hash位置上有元素,进行元素值的覆盖时,就会调用afterNodeAccess(),将原本可能不是最后的node节点拿到了最后。如


结果如下:


而如果是执行下面这段代码,将accessOrder改为false


结果如下:


大家看到区别了吗,accessOrder为false时,你访问的顺序就是按照你第一次插入的顺序;而accessOrder为true时,你任何一次的操作,包括put、get操作,都会改变map中已有的存储顺序。


我们看到在LinkedHashMap中还重写了afterNodeInsertion(boolean evict)方法,它的目的是移除链表中最老的节点对象,也就是当前在头部的节点对象,但实际上在JDK8中不会执行,因为removeEldestEntry方法始终返回false。看源码:


LinkedHashMap的get方法与HashMap中get方法的不同点也在于多了afterNodeAccess()方法


在这里就不再多讲了,getNode()方法在HashMap章节已经讲过,而前面刚把afterNodeAccess讲了。


remove方法也直接使用了HashMap中的remove,在HashMap章节并没有讲解,因为remove的原理很简单,通过传递的参数key计算出hash,据此可找到对应的Node节点,接下来如果该Node节点是直接在数组中的Node,则将table数组该位置的元素设置为node.next;如果是链表中的,则遍历链表,直到找到对应的node节点,然后建立该节点的上一个节点的next设置为该节点的next。


LinkedHashMap重写了其中的afterNodeRemoval(Node e),该方法在HashMap中没有具体实现,通过此方法在删除节点的时候调整了双链表的结构。


LinkedHashMap使用的也较为频繁,它基于HashMap,用于HashMap的特点,又增加了双链表的结构,从而保证了顺序性,本文主要从源码的角度分析其如何保证顺序性,accessOrder的解释,以及常用方法的阐释,若有不对之处,请批评指正,望共同进步,谢谢!


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Java集合 HashSet的原理及常用方法 下一篇TreeMap原理实现及常用方法

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目