今天尝试挖TreeMap的祖坟。底层结构对比先来看看与HashMap和LinkedHashMap的对比，同时回顾一下：HashMap使用数组存储数据，使用单向链表结构存储哈希冲突数据。当同一个冲突桶中的数据量较大时（默认大于8个）使用红黑树存储冲突数据。LinkedHashMap采用数组+双向链表存储数据，冲突数据存储方式与HashMap相同。TreeMap使用红黑树来存储数据。注意这里直接使用了红黑树，而不是表数组。关于排序特性，HashMap没有顺序，不能保持顺序。LinkedHashMap可以保持写的顺序，遍历的时候可以按照写的顺序获取数据。TreeMap是一个有序的Map，根据key值自动排序存储，遍历时得到有序的数据。需要注意的是LinkedHashMap和TreeMap的顺序是不一样的。LinkedHashMap只能保持写的顺序。从“排序”的角度来看，其实是无序的。只有TreeMap可以实现自动排序。TreeMap是按什么排序的？TreeMap底层支持两种排序方式：在实例化TreeMap对象时传入比较器对象。键值对象实现了Comparable接口。如果不满足以上两点，往TreeMap对象中放入数据就会抛出运行时异常。比如TreeMap，由于String实现了Comparable接口，所以没有问题。但是，如果自定义对象没有实现Comparable接口，并且在实例化TreeMap时没有设置比较器对象，那么TreeMap对象实际上是不可用的。TreeMap可以存储null吗？指是否可以存储key为空的数据？我们知道HashMap只能支持一个空对象。很多人说不可能，但是我觉得在一定条件下是可以的，虽然还没有测试过。条件是在实例化TreeMap对象时指定一个comparator对象，同时comparator对象的compare方法可以支持null。研究TreeMap的put源码，我们也可以找到对上述语句的支持：Comparatorcpr=比较器；如果(cpr!=null){do{parent=t;cmp=cpr.compare(key,t.key);如果(cmp<0)t=t.left;elseif(cmp>0)t=t.right;否则返回t.setValue(value);}while(t!=null);}else{if(key==null)thrownewNullPointerException();...省略一些代码发现如果有比较器，put方法不会立即抛出异常。但是如果比较器对象的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会比较慢，因为需要遍历空桶。并发问题还有待研究，但是我们清楚地知道以上三者都不是线程安全的。美好的梦想！
