更多 Java 集合类方面的文章，请参见文集《Java 集合类》
共同点：
- 都是线程不安全的
- Fail-fast behavior
基本区别：
-
迭代顺序：
- HashMap ：遍历时没有特定的顺序，从前到后遍历链表散列（数组 + 链表）。
- LinkedHashMap ：遍历时按照插入的顺序或者访问的顺序。
- TreeMap ：遍历时按照 key 升序（通过 key 的 compareTo 方法进行比较）。
-
put/remove/get 时间复杂度
- HashMap ：O(1)
- LinkedHashMap ：O(1)
- TreeMap ：O(lgN)
-
是否允许空的 key 和 value
- HashMap ：允许空的 key 和 value
- LinkedHashMap ：允许空的 key 和 value
- TreeMap ：只允许空的 value，key 不能为空
-
实现方式
- HashMap ： buckets 链表散列
- LinkedHashMap ：double-linked buckets 双向链表散列
- TreeMap ：红黑树，迭代时做树的中序遍历
使用 HashMap：
Map<String, String> m = new HashMap<String, String>();
m.put("A", "AA");
m.put("C", "CC");
m.put("B", "BB");
m.forEach((k, v) -> System.out.print(k + " "));
打印：A B C
使用 LinkedHashMap：
Map<String, String> m = new LinkedHashMap<String, String>();
m.put("A", "AA");
m.put("C", "CC");
m.put("B", "BB");
m.forEach((k, v) -> System.out.print(k + " "));
打印：A C B
使用 TreeMap：
Map<String, String> m = new TreeMap<String, String>();
m.put("A", "AA");
m.put("C", "CC");
m.put("B", "BB");
m.forEach((k, v) -> System.out.print(k + " "));
打印：A B C
继承结构
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
LinkedHashMap 的实现
成员变量
LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是它重新定义了数组中保存的元素 Entry，该 Entry 除了保存当前对象的引用外，还保存了其上一个元素 before 和下一个元素 after 的引用，从而在哈希表的基础上又构成了双向链接列表。
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
初始化
在 LinkedHashMap 的构造方法中，实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组，但额外可以增加 accessOrder 这个参数，如果不设置，默认为 false，代表按照插入顺序进行迭代；当然可以显式设置为 true，代表以访问顺序进行迭代。
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
存储
LinkedHashMap 并未重写父类 HashMap 的 put 方法，而是重写了父类 HashMap 的 put 方法调用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。
读取
LinkedHashMap 重写了父类 HashMap 的 get 方法，实际在调用父类 getEntry() 方法取得查找的元素后，再判断当排序模式 accessOrder 为 true 时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
排序模式
LinkedHashMap 定义了排序模式 accessOrder。
- 该属性为 boolean 型变量，对于访问顺序，为 true；
- 对于插入顺序，则为 false；
- 一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。
该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建 LRU 缓存。参考 Java 集合 LinkedHashMap 与 LRU cache
LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。
该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回 false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
总结
其实 LinkedHashMap 几乎和 HashMap 一样：从技术上来说，不同的是它定义了一个 Entry<K,V> header，这个 header 不是放在 Table 里，它是额外独立出来的。
LinkedHashMap 通过继承 hashMap 中的 Entry<K,V>,并添加两个属性 Entry<K,V> before,after,和 header 结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。
