本篇单独讲一下HashMap和LinkedHashMap遍历方式。

一、对HashMap和LinkedHashMap遍历的几种方法

这里以HashMap为例，LinkedHashMap一样的方式。

1
2
3
4
5
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());
}
1
2
3
4
5
6
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
    String key = iterator.next();
    System.out.println("key=" + key + " value=" + map.get(key));

}
1
2
3
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对象的时候，是根据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串起来。

1
2
3
4
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. 除了遍历顺序外，其他特性HashMap和LinkedHashMap基本相同。