Java中treemap原理

一、TreeMap介绍

TreeMap是一个有序的key-value集合，它是通过红黑树实现的。

TreeMap继承于AbstractMap，所以它是一个Map，即一个key-value集合。

TreeMap实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。

TreeMap实现了Cloneable接口，意味着它能被克隆。

TreeMap实现了java.io.Serializable接口，意味着它支持序列化。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。

TreeMap的基本操作containsKey、get、put和remove的时间复杂度是log(n)。

另外，TreeMap是非同步的。它的iterator方法返回的迭代器是fail-fastl的。

二、红黑树（Red Black Tree）

是一种自平衡二叉查找树

（1）检索效率O(log n)

（2）红黑树的五点规定：

a每个节点都只能是红色或者黑色

b根节点是黑色

c每个叶节点（NIL节点，空节点）是黑色的。

d从每个叶子到根的所有路径上不能有两个连续的红色节点。

e从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

三、TreeMap使用举例

TreeMap默认按照key递增排序

public class Main {
 public static void main(String[] args) {
 TreeMap treeMap = new TreeMap<>();
 TreeMap treeMap1 = new TreeMap<>();
 treeMap.put(7, "h");
 treeMap.put(8, "g");
 treeMap.put(9, "f");
 treeMap.put(10, "e");
 treeMap.put(14, "a");
 treeMap.put(1, "w");
 treeMap.put(2, "v");
 treeMap.put(3, "u");
 treeMap.put(11, "d");
 treeMap.put(12, "c");
 treeMap.put(13, "b");
 treeMap.put(4, "k");
 treeMap.put(5, "j");
 treeMap.put(6, "i");
 System.out.println("----------------------*------------------------------");
 while (treeMap.size() != 0) {
 //treemap自动按照key进行递增排序
 System.out.println(treeMap.firstEntry().getKey() + " - " + treeMap.firstEntry().getValue());
 treeMap1.put(treeMap.firstEntry().getValue(), treeMap.firstEntry().getKey());
 treeMap.remove(treeMap.firstKey());
 }
 System.out.println("----------------------*------------------------------");
 while (treeMap1.size() != 0) {
 //treemap自动按照key进行递增排序
 System.out.println(treeMap1.firstEntry().getKey() + " - " + treeMap1.firstEntry().getValue());
 treeMap1.remove(treeMap1.firstKey());
 }
 System.out.println("----------------------*------------------------------");
 }
}


得到结果：

----------------------*------------------------------
1 - w
2 - v
3 - u
4 - k
5 - j
6 - i
7 - h
8 - g
9 - f
10 - e
11 - d
12 - c
13 - b
14 - a
----------------------*------------------------------
a - 14
b - 13
c - 12
d - 11
e - 10
f - 9
g - 8
h - 7
i - 6
j - 5
k - 4
u - 3
v - 2
w - 1

广州北大青鸟依托北京大学雄厚资源,是北大青鸟华南地区就业示范校区,学校提供学历+技能+就业服务,主要开设热门课程java培训,UI设计培训,PHP培训,Web前端培训,软件开发编程培训等全程项目实战,免费就业推荐等，详情请点击右边的咨讯框咨询在线的老师，同时还可以获取免费的试听课程，欢迎咨询哦！！！