云计算服务
服务器租用
DDOS 防护
虚拟主机
域名服务
基础设施
关于我们
今天尝试刨一下TreeMap的祖坟。
底层结构对比先来看一下与HashMap、LinkedHashMap的对比，同时就当是复习一下：
HashMap使用数组存储数据，并使用单向链表结构存储hash冲突数据，同一个冲突桶中数据量大的时候（默认超过8）则使用红黑树存储冲突数据。LinkedHashMap使用数组+双向链表存储数据，冲突数据存储方式同HashMap。TreeMap使用红黑树存储数据，注意是直接使用红黑树，不使用table数组。关于排序特性HashMap无顺序，不能保持顺序。LinkedHashMap能保持写入的顺序，遍历的时候可以按照写入顺序获取数据。TreeMap是有序的Map，自动按照key值排序存储，遍历时获取到的是有序数据。需要注意LinkedHashMap和TreeMap在顺序方面的区别，LinkedHashMap只能保持写入顺序，从“排序”的角度讲，他实际是无序的。
只有TreeMap是可以实现自动排序的。
TreeMap按照什么排序？TreeMap底层支持两种排序方式：
TreeMap对象实例化时传入comparator对象。key值对象实现Comparable接口。如果以上两点都不能满足的话，向TreeMap对象put数据的时候会抛出运行时异常。
比如TreeMap<String,Object>，由于String实现了Comparable接口，所以是没有问题的。
但是如果自定义的对象，没有实现Comparable接口，同时在TreeMap实例化的时候没有设置comparator对象，则该TreeMap对象实际是不可用的。
TreeMap是否可以存储null？指的是，是否可以存储key为空的数据？我们知道HashMap是可以支持唯一一个null对象的。
很多人都说不可以，但是我觉得有条件可以，虽然还没有测试。
条件是实例化TreeMap对象的时候指定comparator对象，同时，该comparator对象的compare方法可以支持null。
研究TreeMap的put源码，也可以发现对以上说法的支持：
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
...省略若干代码可以发现如果有comparator的话，put方法不会立即抛出异常。但是如果comparator对象的compare方法不能支持null的话，一样会抛出异常。
put方法由于TreeMap支持自动排序，所以put方法会检查是否满足规则。
不满足排序规则，抛出异常。
否则，按照红黑树算法规则要求，创建红黑树，存储数据。
get方法根据红黑树查找算法查找并返回数据，红黑树是平衡二叉树，查询时间复杂度为O(log(n))。
key遍历比如调用TreeMap.keySet方法，采用遍历二叉树算法，按照从小到大的顺序返回所有key值组成的循环器。
我该使用哪一个？需要用到Map的时候，到底该使用哪一个的问题：
我只需要一个存储数据的容器，没有具体要求的话，用HashMap。存储数据后，有按照存储顺序获取数据的需求，采用LinkedHashMap。希望存储数据的同时，帮助实现自动排序，采用TreeMap。性能的问题，其实几乎不需要考虑，不过我们还是需要知道：
HashMap和LinkedHashMap查询速度快，理想情况下时间复杂度几乎是O(1)。HashMap写入速度最快，LinkedHashMap写入速度与HashMap几乎相同，TreeMap写入速度最慢（理论上，实际数据量小的情况下未必慢）。遍历速度相差无几，理论上HashMap会慢一点，因为需要遍历空桶。并发问题尚待研究，但是我们清楚地知道，以上三种均不具备线程安全性。
好梦！
.png)
.png)
