image.png
HashMap不保证数据有序
LinkedHashMap保证数据插入有序，
要保证map的key可以大小排序，使用TreeMap集合

使用红黑树实现key按大小排序。
红黑树是一颗自平衡的排序二叉树。是一个有着着色性质的二叉查找树：

  1. 每一个节点为黑色或红色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，那么它的子节点是黑色的
  4. 从一个节点到一个Null引用的每一条路径（如果有多条的话），必须包含相同数目的黑色节点。

TreeMap数据结构

定义

  1. public class TreeMap<K,V>
  2.     extends AbstractMap<K,V>
  3.     implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap中同时也包含了如下几个重要的属性：

  1. //比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
  2. private final Comparator<? super K> comparator;
  3. //TreeMap红-黑节点，为TreeMap的内部类
  4. private transient Entry<K,V> root = null;
  5. //容器大小
  6. private transient int size = 0;
  7. //TreeMap修改次数
  8. private transient int modCount = 0;
  9. //红黑树的节点颜色--红色
  10. private static final boolean RED = false;
  11. //红黑树的节点颜色--黑色
  12. private static final boolean BLACK = true;

Entry是TreeMap的内部类

  1. //键
  2. K key;
  3. //值
  4. V value;
  5. //左孩子
  6. Entry<K,V> left = null;
  7. //右孩子
  8. Entry<K,V> right = null;
  9. //父亲
  10. Entry<K,V> parent;
  11. //颜色
  12. boolean color = BLACK;

TreeMap put()方法

对于新节点的插入有如下三个关键地方：
1、插入新节点总是红色节点 。
2、如果插入节点的父节点是黑色, 能维持性质 。
3、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。

TreeSet

image.png
都是用TreeMap实现的

  1. //构造函数
  2.     public TreeSet() {
  3.         this(new TreeMap<E,Object>());
  4.     }