Java-Map

TreeMap

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序。

HashMap， ConcurrentHashMap 1.8版本，当链表长度大于8时，优化成红黑树实现

@see

http://www.cnblogs.com/skywang12345/p/3310928.html

http://yikun.github.io/2015/04/06/Java-TreeMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

红黑树：

http://www.cnblogs.com/skywang12345/p/3245399.html

https://www.ibm.com/developerworks/cn/java/j-lo-tree/

http://dongxicheng.org/structure/red-black-tree/

使用场景：

TreeMap通常比HashMap、Hashtable要慢(尤其是在插入、删除key-value对时更慢)，因为TreeMap底层采用红黑树来管理键值对。

但是TreeMap有一个好处就是：TreeMap中的key-value对总是处于有序状态，无须专门进行排序操作。

虽然TreeMap在插入和删除方面性能比较差，但是在分类处理的时候作用很大，遍历的速度很快。

B-树：

多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键

字范围的子结点；

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：

在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；

B+树总是到叶子结点才命中；

红黑树：

平衡二叉树，通过左右旋达到平衡

性质1. 节点是红色或黑色

性质2. 根是黑色

性质3. 所有叶子都是黑色（叶子是NIL节点）

性质4. 如果一个节点是红的，则它的两个儿子都是黑的

性质5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。

LinkedHashMap

继承于HashMap，是 Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用 get 方法)的链表。默认是按插入顺序排序（accessOrder=false），如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。按访问顺序排序模式 ，该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建 LRU 缓存。

总结

其实 LinkedHashMap 几乎和 HashMap 一样：从技术上来说，不同的是它定义了一个 Entryheader，这个 header 不是放在 Table 里，它是额外独立出来的。LinkedHashMap 通过继承 hashMap 中的 Entry,并添加两个属性 Entry before,after,和 header 结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。

@see

http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html

http://yikun.github.io/2015/04/02/Java-LinkedHashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/