526互联

HashMap和LinkedHashMap遍历机制

发布时间 2023-03-27 15:40:39作者: Frodo1124

原文链接：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> 的接口：

  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 串起来。

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 基本相同。