关于java:TreeMap底层

明天尝试刨一下 TreeMap 的祖坟。

底层构造比照

先来看一下与 HashMap、LinkedHashMap 的比照，同时就当是温习一下：

1. HashMap 应用数组存储数据，并应用单向链表构造存储 hash 抵触数据，同一个抵触桶中数据量大的时候（默认超过 8）则应用红黑树存储抵触数据。
2. LinkedHashMap 应用数组 + 双向链表存储数据，抵触数据存储形式同 HashMap。
3. TreeMap 应用红黑树存储数据，留神是间接应用红黑树，不应用 table 数组。

对于排序个性

1. HashMap 无程序，不能放弃程序。
2. LinkedHashMap 能放弃写入的程序，遍历的时候能够依照写入程序获取数据。
3. TreeMap 是有序的 Map，主动依照 key 值排序存储，遍历时获取到的是有序数据。

须要留神 LinkedHashMap 和 TreeMap 在程序方面的区别，LinkedHashMap 只能放弃写入程序，从“排序”的角度讲，他理论是无序的。

只有 TreeMap 是能够实现主动排序的。

TreeMap 依照什么排序？

TreeMap 底层反对两种排序形式：

1. TreeMap 对象实例化时传入 comparator 对象。
2. 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 的时候，到底该应用哪一个的问题：

1. 我只须要一个存储数据的容器，没有具体要求的话，用 HashMap。
2. 存储数据后，有依照存储程序获取数据的需要，采纳 LinkedHashMap。
3. 心愿存储数据的同时，帮忙实现主动排序，采纳 TreeMap。

性能的问题，其实简直不须要思考，不过咱们还是须要晓得：

1. HashMap 和 LinkedHashMap 查问速度快，现实状况下工夫复杂度简直是 O(1)。
2. HashMap 写入速度最快，LinkedHashMap 写入速度与 HashMap 简直雷同，TreeMap 写入速度最慢（实践上，理论数据量小的状况下未必慢）。
3. 遍历速度相差无几，实践上 HashMap 会慢一点，因为须要遍历空桶。

并发问题尚待钻研，然而咱们分明地晓得，以上三种均不具备线程安全性。

好梦！