红黑树与map原理（TreeMap和红黑树）

既然有了HashMap，为什么JDK还提供了TreeMap呢？

通过TreeMap的源码，我们可以发现：

1. TreeMap内部是基于红黑树实现的
2. TreeMap实现了NavigableMap

下面我们通过代码看下TreeMap实际是怎么运作的

// 代码段一，初始化treeMap，组成内部红黑树 TreeMap<Integer, Integer> treeMap = new TreeMap<>(); for (int i = 0; i < 10; i ) { treeMap.put(i, i); } // 代码段二，keyset是正向有序的 for(Integer key:treeMap.keySet()) { System.out.print(key); } System.out.println(); // 代码段三，keyset是反向有序的 for(Integer key:treeMap.descendingKeySet()) { System.out.print(key); }

首先我们往数组里面插入10条键值对，通过下图我们可以看到TreeMap内部红黑树的变化过程：

TreeMap红黑树变化过程

红黑树是一个自平衡二叉树，它的查询时间复杂度为Olog(n)，插入删除操作引发的树旋转操作不超过三次，因此复杂度也是Olog(n)，关于红黑树的原理由于篇幅原因大家可以搜索下百度百科等知识平台。

那么既然有了HashMap，它的查询复杂度是一个常量，为什么还需要TreeMap这类性能更低效的数据结构呢？

因为它实现了NavigableMap，而NavigableMap实现了SortedMap，因此我们可以推断出以下结论：

1. TreeMap里面是根据key值排序的（因此又推导出key必须继承Comparable接口)
2. TreeMap具有了NavigableMap的功能（根据给定的key值查找其相关联的节点）

我们再返回去看下上面的代码，当运行代码段二时，会打印出有序的key值0123456789；当运行上代码段三时，会打印出反向有序的key值9876543210;

所以，当你需要Map集合内的键值对是有序的时候，以及根据某个特点key值查找其相关节点时（例如：查找比给定key值大并且最接近该key值的键值对时），TreeMap是一个不错的选择，而这是HashMap无法满足的。

https://gitee.com/xiaoxijava/java-learning/blob/master/src/main/java/net/weichitech/collection/TreeMapDemo.java