TreeMap

内部结构

TreeMap 是基于红黑树实现的，增删改查操作的平均和最坏时间复杂度都为 O(log n)，其根节点为 key 最小的 entry。

黑红树相比 AVL 树，任何不平衡都能在 3 次旋转之内完成调整，每次向上回溯的步长是 2，对于频繁插入和删除的场景，红黑树的优势非常明显。

TreeMap 的时间复杂度比 HashMap 要高一点，但是合理利用其有序性和稳定性，以及支持范围查找的特性，往往在数据排序场景中特别高效。

key 唯一性机制

TreeMap 的 key 唯一性并不是基于 **equals()** 方法实现的！而是基于 compareTo() 或 compare() 方法实现的，对此你可以查看该类的 put() 方法源码。下面通过一段示例代码进行演示：

public class InstantDemo {
    public static void main(String[] args) {
        TreeMap<Key, String> map = new TreeMap<>();
        map.put(new Key(), "value 1");
        map.put(new Key(), "value 2");
        map.size();        // return 2, but if map is an object of HashMap. return 1
    }
}
class Key implements Comparable<Key> {
    @Override
    public boolean equals(Object obj) { return true; }
    @Override
    public int compareTo(Key o) { return -1; }
}

正是因为需要使用 compareTo() 或 compare() 方法保证 key 的唯一性，所以 **TreeMap** 的 key 不允许为 **null** ，但 value 允许为 **null** 。

TreeSet 与 TreeMap

TreeSet 是基于 TreeMap 实现的， TreeSet 的底层就是一个 TreeMap 对象，所有的 value 共享一个静态 Object 对象，源码如下所示：

// TreeSet
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

相比 HashMap，TreeMap 的使用频率相对较少，这里给出一道使用了 TreeSet 结构的题目：

• LeetCode 1606. 找到处理最多请求的服务器