明天尝试刨一下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会慢一点，因为须要遍历空桶。
并发问题尚待钻研，然而咱们分明地晓得，以上三种均不具备线程安全性。
好梦！