面试题：Java中TreeMap如何实现有序存储

Question

请简述在Java中TreeMap是依据什么原理实现数据有序存储的？如果存储自定义对象，需要满足什么条件才能保证其在TreeMap中有序存储？

Answer 1

TreeMap数据有序存储原理

TreeMap是基于红黑树（Red - Black Tree）实现的。红黑树是一种自平衡的二叉查找树，具有以下特性：

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点：根节点是黑色的。
3. 叶子节点：每个叶子节点（NIL节点，空节点）是黑色的。
4. 红色节点：如果一个节点是红色的，那么它的子节点必须是黑色的。
5. 黑色高度：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

在TreeMap中，当插入新元素时，会按照红黑树的规则进行插入操作，插入后通过旋转和颜色调整来保持红黑树的平衡。同时，由于二叉查找树的特性，左子树的所有节点的值小于根节点的值，右子树的所有节点的值大于根节点的值，这就保证了TreeMap中的元素是有序存储的（默认按照键的自然顺序排序）。

存储自定义对象的条件

如果要在TreeMap中存储自定义对象作为键并保证有序存储，自定义对象必须实现Comparable接口，并重写compareTo方法。compareTo方法定义了自定义对象之间的比较逻辑，通过这个方法TreeMap可以确定对象之间的顺序关系。例如：

class CustomObject implements Comparable<CustomObject> {
    private int value;

    public CustomObject(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(CustomObject other) {
        return Integer.compare(this.value, other.value);
    }
}

或者也可以在创建TreeMap时提供一个Comparator接口的实现类，通过Comparator来定义自定义对象的比较逻辑，而不需要自定义对象本身实现Comparable接口。例如：

class CustomComparator implements Comparator<CustomObject> {
    @Override
    public int compare(CustomObject o1, CustomObject o2) {
        return Integer.compare(o1.value, o2.value);
    }
}
TreeMap<CustomObject, String> treeMap = new TreeMap<>(new CustomComparator());