首页资讯 • 正文

LinkdHashSet底层怎么实现元素有序? <#21---->

发布时间:

各位大佬好,本人目前在培训,遇到个问题,list接口下元素是有序的,Arraylist集合底层是数组,linkList底层是链表有序,LinkedHashSet底层是增强型的链表,请问底层是怎么实现排序的。看源码发现是比较,请问下具体是怎么比较的?

从源码的角度来对LinkedHashSet寻根问底!

先一览LinkedHashSet类中的所有方法,发现就是一些构造方法,没什么特别的。。spliterator方法也只是个迭代器!

从构造器中的super方法点过去可得见端倪,原来构造器中的父级构造器使用的是LinkedHashMap进行实例化,那么LinkedHashSet的特性势必跟LinkedHashMap息息相关,换句话说LinkedHashSet的输出有序来自于LinkedHashMap;

下面对LinkedHashMap进行详细分析:

LinkedHashMap继承HashMap,实现了Map,很明显LinkedHashMap也算是HashMap,还保存了数组+链表的结构,至于有序的原因肯定不会是因为Map接口和继承HashMap,也就是说LinkedHashMap的有序,肯定就是在LinkedHashMap类中实现的;

HashMap的底层数据结构是使用数组中的位置作为桶,每个桶中放置一份链表(或者红黑树),而hashCode落在哪一个桶是不确定的,没有关联关系,所以HashMap不能做到有序输出,而LinkedHashMap使用的是双重链表形式,保存在map中的数据不仅在每一个桶里使用链表维护有序,还在每个值上维护链表来维护有序;

借用图一张,如下:

不仅如此,LinkedHashMap的迭代方式有两种,一种是按照插入顺序排序(迭代时就像队列一样),一种是访问排序(像栈一样,后访问的放在栈头,可作为LRU实现)

下面分析下主要源码:

1,先看LinkedHashMap中的内部类Entry:

Entry继承于HashMap.Node,Node对象中有hash,key,value等一个key-value结构,还有next作为hashMap中同一个桶下面的entry指向,LinkedHashMap.Entry新获得了这些属性,且新定义了两个属性Entry before, after,用来对所有的entry维护一个指向,变成一个双向链表;

其余的诸如LinkedKeyIterator,LinkedEntrySet等内部类都是作为迭代器,

2,再看LinkedHashMap中的属性:

LinkedHashMap中的主要属性有是三个head,tail(维护链表的头尾,很容易理解),accessOrder:注释写的很清楚,就是true的时候就是访问顺序,false的时候是插入顺序;

3,LinkedHashMap中的方法: ①,put方法:LinkedHashMap中溜了一圈,并没发现有put方法,难道是使用的HashMap的put方法?那entry的链表是怎么做到的呢?




从HashMap中的put方法可以看到,计算了hash值之后就调用了putVal方法,而在生成新插入的元素的时候,使用的是newNode方法,LinkedHashMap确实没有重写put方法,但是重写了newNode方法,从代码中可以看到HashMap中的newNode方法,只是单纯的new了一个Node返回,而LinkedHashMap中的newNode方法不仅new了对象,还调用linkNodeLast,将对象挂在了链表的tail节点上,形成链表;(by the way,由此可见jdk中数据结构对于多态特性(重写之后调用子类方法)使用的淋漓尽致)

跟newNode方法类似的还有一个newTreeNode方法,这个也是在HashMap中的put方法里进行调用的,也就是红黑树结构;

②,get方法:

从get方法中可以看到,如果accessOrder为false,那么LinkedHashMap使用的get方法和HashMap一样,计算相应的hash值,比较key值(==,equals),匹配上则返回,如果accessOrder为true,则调用afterNodeAccess方法,判断各种情况,然后把这个值设置为tail,保证是栈头的位置,下次最先查找到; 代码如上截图!

③,remove方法:

LinkedHashMap中的remove方法和HashMap中的是一样的,但是最后的afterNodeRemoval方法在HashMap中的方法体是空的,而在LinkedHashMap中进行了重写,把这个node的后一个节点接到了前一个节点上,这个node相当于脱链了。。 代码如下截图:

总的来说LinkedHashMap相比HashMap增加了链表特性,维护了元素的有序,虽然方法大部分都是用的HashMap的方法,但是使用重写这种多态特性,在LinkedHashMap中进行了不同了实现,可以说这也是我们开发代码时应该要学习的,以后再扩展其他类型的HashMap,只用重写部分方法即可实现!

LinkedHashMap就说到这,笔者已经分享了很多java方面的技术,有很多帮助到了一些朋友!还会一直持续分享,敬请关注。。。

1.LinkedHashSet是继承HahsSet的,构造方法调用HashSet有三个参数的方法,这个构造方法底层会初始化化一个LinkedHashMap。因为LinkedHashMap是有序的,所以LinkedHashSet也是有序的。为什么这个构造方法我们不能调用,因为是包访问级别的,外部无法调用。接下来分析下LinkedHashMap是怎么实现的就明白为什么有序了。

2.可以先看下下面的图片。(手机上写的问题,不能把图片放在正文里,全部在最下面)。

LinkedHashMap的数据结构和HashMap就是Entry不一样,HashMap中的Entry有四个属性key,value,hash,next,而LinkedHashMap中的Entry添加了before和after属性,所以说LinkedHashMap是在HashMap的基础上使用了双向链表把所有节点连起来,当然还有一个头节点,所以遍历的时候可以保证有序。具体结构可以看图。

3.LinkedHashMap主要是重写了addEntry,createEntry方法来达到在创建节点的时候创建双向链表。

另外,LinkedHashMap还可以实现LRU算法的缓存。

源码是基于JDK7看的哈。如果不理解HashMap可以看我分享的另一篇文章。

希望对你有帮助,可以关注我,后续会分享更多的架构和Java知识文章。

相关文章Related

相关文章Related

返回栏目>>

首页   |   网站地图

Copyright © 2002-2019 海贼王网,精油,三菱,肾病,邮轮 版权所有