前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Java基础要义]HashMap、LinkedHashMap元素遍历机制探讨

[Java基础要义]HashMap、LinkedHashMap元素遍历机制探讨

作者头像
亦山
发布2019-05-25 09:40:39
1.2K0
发布2019-05-25 09:40:39
举报
文章被收录于专栏:Spring Cloud设计原理

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1432186

      Map作为键值对Entry<K,V>的的容器,对其内部 键值对Entry<K,V> 的遍历总归是要有一个顺序的。

      本文重点讨论HashMap及其子类LinkedHashMap的遍历机制,总结出两者的特点和适用情况。

CSDN-2014博客之星投票啦

CSDN-2014博客之星   评选开始啦,如果您觉得我的文章对您有所帮助,请您点击左边栏的图片投我一票,您的支持是我分享知识的强大动力!

1.HashMap的遍历机制

HashMap 提供了两个遍历访问其内部元素Entry<k,v>的接口:

              1.       Set<Map.Entry<K,V>> entrySet()    返回此映射所包含的映射关系的 Set 视图。

             2.      Set<K> keySet()            返回此映射中所包含的键的 Set 视图。

     实际上,第二个借口表示的Key的顺序,和第一个接口返回的Entry顺序是对应的,也就是说:这两种接口对HashMap的元素遍历的顺序相相同的。  那么,HashMap遍历内部Entry<K,V> 的顺序是什么呢? 搞清楚这个问题,先要知道其内部结构是怎样的。          

           HashMap内部对键值对的存储结构使用的是数组+链表的形式。其结构如下图所示:

HashMap内部Entry<K,V>的遍历顺序:

对Entry[] table 数组,从index=0开始,依次遍历tablei 上的链表上的Entry对象。

由于HashMap在存储Entry对象的时候,是根据Key的hash值判定存储到Entry[] table数组的哪一个索引值表示的链表上,所以笼统地说就是:使用hashMap.put(Key key,Value value)会将 对应的Entry<Key,Value>对象随机地分配到某个Entry[] table数组的元素表示的链表上。换一句话说就是:

对HashMap遍历Entry对象的顺序和Entry对象的存储顺序之间没有任何关系。

但是,我们有时候想要遍历HashMap的元素Entry的顺序和其存储的顺序一致,HashMap显然不能满足条件了。而LinkedHashMap则可以满足这个需要。

2. LinkedHashMap 的遍历机制

LinkedHashMap 是HashMap的子类,它可以实现对容器内Entry的存储顺序和对Entry的遍历顺序保持一致。

       为了实现这个功能,LinkedHashMap内部使用了一个Entry类型的双向链表用这个双向链表记录Entry的存储顺序。当需要对该Map进行遍历的时候,实际上是遍历的是这个双向链表。

        LinkedHashMap内部使用的LinkedHashMap.Entry类继承自 Map.Ent ry类,在其基础上增加了LinkedHashMap.Entry类型的两个字段,用来引用该Entry在双向链表中的前面的Entry对象和后面的Entry对象。

       它的内部会在 Map.Entry 类的基础上,增加两个Entry类型的引用:before,after。LinkedHashMap使用一个双向连表,将其内部所有的Entry串起来。

我们将通过以下例子,来了解内部双向链表是怎样构造的:

LinkedHashMap linkedHashMap = new LinkedHashMap(); linkedHashMap.put("name","louis"); linkedHashMap.put("age","24"); linkedHashMap.put("sex","male"); 上述的代码除了会将对应的Entry对象放置到在Entry[] table 表示的数组链表中外,还会将该Entry对象添加到其内部维护的双向链表中。对应的LinkedHashMap内部的双向链表变化如下:

对LinkedHashMap进行遍历的策略:

代码语言:txt
复制
_**从 header.after 指向的Entry对象开始,然后一直沿着此链表 遍历下去,直到某个entry.after == header 为止,完成遍历。**_

由此,就可以保证遍历LinkedHashMap内元素的顺序,就是Entry插入到LinkedHashMap中的顺序。

将上面代码中定义的linkedHashMap 遍历输出,会发现遍历的顺序跟插入的顺序完全一致:

代码语言:txt
复制
     Iterator<Map.Entry> iterator= linkedHashMap.entrySet().iterator();          while(iterator.hasNext())         {             Map.Entry entry = iterator.next();             System.out.println(entry.getKey()+":"+entry.getValue());         }

结果输出:

根据Entry<K,V>插入LinkedHashMap的顺序进行遍历的方式叫做:按插入顺序遍历

另外,LinkedHashMap还支持一种遍历顺序,叫做:Get读取顺序

如果LinkedHashMap的这个Get读取遍历顺序开启,那么,当我们在LinkedHashMap上调用get(key) 方法时,会导致内部 key对应的Entry在双向链表中的位置移动到双向链表的最后。

比如,如果当前LinkedHashMap内部的双向链表的情况如下:

相关代码如下:

代码语言:txt
复制
     //默认情况下LinkedHashMap的遍历模式是插入模式,如果想显式地指定为get读取模式,那么要将         //其构造方法的参数置为true,(false 表示的是插入模式)         LinkedHashMap linkedHashMap = new LinkedHashMap(16, (float) 0.75,true);          linkedHashMap.put("name","louis");         linkedHashMap.put("age","24");         linkedHashMap.put("sex","male");         linkedHashMap.get("name");//get()方法调用,导致对应的entry移动到双向链表的最后位置          Iterator<Map.Entry> iterator= linkedHashMap.entrySet().iterator();          while(iterator.hasNext())         {             Map.Entry entry = iterator.next();             System.out.println(entry.getKey()+":"+entry.getValue());         }
3. 总结

1.HashMap对元素的遍历顺序跟Entry插入的顺序无关,而LinkedHashMap对元素的遍历顺序可以跟Entry<K,V>插入的顺序保持一致。 2.当LinkedHashMap处于Get获取顺序遍历模式下,当执行get() 操作时,会将对应的Entry<k,v>移到遍历的最后位置。 3.LinkedHashMap处于按插入顺序遍历的模式下,如果新插入的<key,value> 对应的key已经存在,对应的Entry在遍历顺序中的位置并不会改变。 4. 除了遍历顺序外,其他特性HashMap和LinkedHashMap基本相同。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015年01月22日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.HashMap的遍历机制
  • 2. LinkedHashMap 的遍历机制
  • 3. 总结
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档