原文链接:HashMap和LinkedHashMap遍历机制
对 HashMap
和 LinkedHashMap
遍历的几种方法
以 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>
的接口:
Set<Map.Entry<K,V>> entrySet()
:返回此映射所包含的映射关系的Set
视图。Set<K> keySet()
:返回此映射中所包含的键的Set
视图。
实际上,第二个接口表示的 Key
的顺序,和第一个接口返回的 Entry
顺序是对应的,也就是说:这两种接口对 HashMap
的元素遍历的顺序相相同的。 那么,HashMap
遍历内部 Entry<K,V>
的顺序是什么呢? 搞清楚这个问题,先要知道其内部结构是怎样的。
HashMap
在存储 Entry
对象的时候,是根据 Key
的 hash
值判定存储到Entry[] table
数组的哪一个索引值表示的链表上。
对 HashMap
遍历 Entry
对象的顺序和 Entry
对象的存储顺序之间没有任何关系。
HashMap
散列图、Hashtable
散列表是按“有利于随机查找的散列 (hash)
的顺序”。并非按输入顺序。 遍历时只能全部输出,而没有顺序。甚至可以 rehash()
重新散列,来获得更利于随机存取的内部顺序。
所以对 HashMap
的遍历,由内部的机制决定的,这个机制是只考虑利于快速存取,不考虑输入等顺序。
LinkedHashMap 的遍历机制
LinkedHashMap
是 HashMap
的子类,它可以实现对容器内 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
在双向链表中的位置移动到双向链表的最后。
遍历机制的总结
-
HashMap
对元素的遍历顺序跟Entry
插入的顺序无关,而LinkedHashMap
对元素的遍历顺序可以跟Entry<K,V>
插入的顺序保持一致:从双向。 -
当
LinkedHashMap
处于Get
获取顺序遍历模式下,当执行get()
操作时,会将对应的Entry<k,v>
移到遍历的最后位置。 -
LinkedHashMap
处于按插入顺序遍历的模式下,如果新插入的<key,value>
对应的key
已经存在,对应的Entry
在遍历顺序中的位置并不会改变。 -
除了遍历顺序外,其他特性
HashMap
和LinkedHashMap
基本相同。