TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？
1. TreeMap底层数据结构TreeMap 是 Java 集合框架中基于 红黑树（Red‑Black Tree）实现的一个 有序映射。
它的数据结构非常简单，只使用了红黑树一种数据结构，不像HashMap和LinkedHashMap 那么复杂。
Entry内部类字段：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left; //左子节点
Entry<K,V> right; //右子节点
Entry<K,V> parent; //父节点
boolean color = BLACK; //节点颜色：BLACK=true, RED=false
}key、value和color为当前对象的值，其它字段为构成红黑树所需的节点对象。数据结构如图：
在Java中所有集合都是保存引用对象的引用，而非对象的值。TreeMap也是如此，在Entry对象中的Entry left、Entry right、Entry parent 都只是保存着对象的引用（可以理解为地址指向），而非具体的值。
Map集合的共性，只要知道key如何计算，便可知道value所在位置。在TreeMap中也是如此，最需要关注的是key在红黑树中的处理。
例如下图key在TreeMap中的存储：
2. TreeMap 的特点
TreeMap 是 基于 红黑树（Red‑Black Tree）实现的一个 有序映射，特点是有序。这是由底层数据结构所带来的有序特性。
红黑树是一种自平衡二叉查找树，是一种有序的二叉树，按照左中右从小到大排序。
HashMap 同样也使用了红黑树，那是不是HashMap关于红黑树的那部分元素是有序的？没错，在HashMap中红黑树部分的元素是有序的，但是，它的有序性是根据key的hash值进行的排序，并且hash值在计算的过程中进行了扰动，就算没有扰动，hash值的有序对于使用者来说也没有意义，这种有序性仅用于维持红黑树。
而TreeMap集合的有序性是key值的有序，是根据key值进行的排序，这种有序性对于使用者来说才有实际性的价值。
哪么如何根据key值进行的排序呢？
2.1. TreeMap如何比较key值大小？
默认情况的比较，又称为自然顺序比较。TreeMap内部假定所有键类型都实现了 Comparable 接口，会直接调用key对象的中比较方法进行比较。
在插入、查找或删除时，会执行强制类型转换并调用：
((Comparable
页:
[1]