首页 > 其他分享 >HashMap和LinkedHashMap遍历机制

HashMap和LinkedHashMap遍历机制

时间:2023-03-27 15:45:30浏览次数:66  
标签:遍历 HashMap 顺序 key Entry LinkedHashMap

原文链接:HashMap和LinkedHashMap遍历机制

HashMapLinkedHashMap 遍历的几种方法

HashMap 为例,LinkedHashMap 方法一样。

一共有三种遍历方式

Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
    Map.Entry<String, Integer> next = entryIterator.next();
    System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
    String key = iterator.next();
    System.out.println("key=" + key + " value=" + map.get(key));
}
map.forEach((key,value)->{
    System.out.println("key=" + key + " value=" + value);
});

强烈建议使用第一种 EntrySet 进行遍历。

第一种可以把 key value 同时取出,第二种还得需要通过 key 取一次 value,效率较低, 第三种需要 JDK1.8 以上,通过外层遍历 table,内层遍历链表或红黑树。

我们知道,HashMap 的输出顺序与元素的输入顺序无关,LinkedHashMap 可以按照输入顺序输出,也可以根据读取元素的顺序输出。

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 在存储 Entry 对象的时候,是根据 Keyhash 值判定存储到Entry[] table 数组的哪一个索引值表示的链表上。

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

HashMap 散列图、Hashtable 散列表是按“有利于随机查找的散列 (hash) 的顺序”。并非按输入顺序。 遍历时只能全部输出,而没有顺序。甚至可以 rehash() 重新散列,来获得更利于随机存取的内部顺序。

所以对 HashMap 的遍历,由内部的机制决定的,这个机制是只考虑利于快速存取,不考虑输入等顺序。

LinkedHashMap 的遍历机制

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

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

LinkedHashMap 内部使用的 LinkedHashMap.Entry 类继承自 Map.Entry 类,在其基础上增加了 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");

LinkedHashMap 进行遍历的策略:

header.after 指向的 Entry 对象开始,然后一直沿着此链表遍历下去,直到某个 entry.after == header 为止,完成遍历。

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

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

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

遍历机制的总结

  1. HashMap 对元素的遍历顺序跟 Entry 插入的顺序无关,而 LinkedHashMap 对元素的遍历顺序可以跟 Entry<K,V> 插入的顺序保持一致:从双向。

  2. LinkedHashMap 处于 Get 获取顺序遍历模式下,当执行 get() 操作时,会将对应的 Entry<k,v> 移到遍历的最后位置。

  3. LinkedHashMap 处于按插入顺序遍历的模式下,如果新插入的 <key,value> 对应的 key 已经存在,对应的 Entry 在遍历顺序中的位置并不会改变。

  4. 除了遍历顺序外,其他特性 HashMapLinkedHashMap 基本相同。

标签:遍历,HashMap,顺序,key,Entry,LinkedHashMap
From: https://www.cnblogs.com/shixuanliu/p/17260968.html

相关文章

  • Java数据结构 HashMap 哈希表定义使用
    1.HashMapHashMap是一个散列表,它存储的内容是键值(key-value)映射。其中key和value类型可以相同也就而已不同,根据定义。2.HashMap使用1)定义HashMap<Integer,String>hashmap1......
  • C#遍历指定文件夹中所有文件的3种方法
        前段时间小编同事面试遇到了这个问题,由于同事比较菜并未很完美的完成这个问题,本文就替小编来解答一下。在C#中有多种方式类遍历指定文件夹中的文件,本文将介绍三种......
  • 实验2 目录树的遍历
    Unix实验报告实验:实验2目录树的遍历专业:计算机科学与技术班级:1班姓名:姚怀聿学号:229202022046322022年10月21日目录一......
  • 实验2 目录树的遍历
    Unix实验报告实验:实验2目录树的遍历专业:计算机科学与技术班级:1班姓名:姚怀聿学号:229202022046322022年10月21日目录一......
  • 为什么HashMap查找比List快很多?
    做两数之和这道题目时,引发了一个思考:为什么两者运行时间相差如此之大???好残忍,我List比你HashMap到底差在哪****于是我一顿查资料....战犯哈希算法登场哈希算法......
  • LeetCode. 102二叉树的层序遍历
    1.题目:给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]来源:力扣(L......
  • Java中Map类型数据使用LinkedHashMap保留数据的插入顺序
    场景Vue中JS遍历后台JAVA返回的Map数据,构造对象数组数据格式:Vue中JS遍历后台JAVA返回的Map数据,构造对象数组数据格式_BADAO_LIUMANG_QIZHI的博客在上面构造以时间为Key,以......
  • 【leetcode-数组】对角线遍历
    题目:给定一个含有MxN个元素的矩阵(M行,N列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。 示例:输入:[[1,2,3],[4,5,6],[7,8......
  • 软著帮手-遍历项目中所有的文件输出项目所有的代码以及代码行数
    packagecom.example.demo;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileReader;publicclassTest{staticintcount=0;pu......
  • vue3中如何通过遍历传入组件名称动态创建多个component 组件
    背景在vue3中,如果使用component,可以动态加载一个组件,例如<!--直接创建--><component:is="Image"/>这样会将已经定义好并导入的比如Image组件加载出来,但......