LinkedHashMap与HashMap底层存储结构的区别：
LinkedHashMap存储结构和HashMap相同，依然是数组+链表+红黑树LinkedHashMap额外持有一个双向链表，维护插入节点的顺序- 最终的数据结构如下图
- 实际的元素存储与HashMap一致，依然是数组+链表+红黑树的形式
- 区别在于：
- 除了维护数组+链表的结构之外，还根据插入Map先后顺序维护了一个双向链表的头尾head,tail
- Node基本结构，相比较HashMap而言，还增加了 before,after 两个分别指向双向链表中前后节点的属性
- 即下图中的双向链表中的节点，其实值依然是下面的数组+链表结构中的元素
TreeMap：
- TreeMap存储K-V键值对，通过红黑树（R-B tree）实现；
- TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要TreeMap自己去实现；
- TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；
- TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；
红黑树：
性质1：每个节点是红的或者黑色
性质2：根是黑色
性质3：所有叶子都是黑色（叶子是NIL节点）
性质4：如果一个节点是红的，则它的两个儿子都是黑的
性质5：从任意一个节点到其叶子的所有简单路径都包含相同数目的黑色节点。
【如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为
,其查找效率为
，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在
到O(n)之间。
二叉查找树方便查找，但随着插入可能效率会变低，比如往一个值都比较小的查找树插入10001，10002，10003...最右边的一条分支很长，查找效率变低。所以就需要平衡查找树，但是AVL（二叉查找树）高度差不能超过1，插入经常需要旋转来维持平衡，性能开销非常大，还不如别平衡了。所以就有了红黑树，这种局部平衡的结构。】