treemap的工作原理

treemap是一种基于红黑树实现的有序映射。它的工作原理如下[^1][^2]：

1. 插入操作：当向treemap中插入一个键值对时，treemap会根据键的大小将其插入到合适的位置。如果键已经存在，则会更新对应的值。插入操作的时间复杂度为O(logN)。

2. 删除操作：当从treemap中删除一个键值对时，treemap会根据键的大小找到对应的节点，并删除它。删除操作的时间复杂度为O(logN)。

3. 查找操作：当根据键查找对应的值时，treemap会根据键的大小在红黑树中进行查找，找到对应的节点并返回其值。查找操作的时间复杂度为O(logN)。

4. 有序性：treemap中的键值对是按照键的大小进行排序的。通过红黑树的特性，treemap可以保持键的有序性。

下面是一个treemap的示例代码，展示了treemap的工作原理：

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(4, "qd");
        treeMap.put(3, "sd");
        treeMap.put(1, "sd");
        treeMap.put(5, "sd");
        treeMap.put(7, "sd");
        treeMap.put(9, "sd");
        treeMap.put(0, "sd");

        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

输出结果为：

0 sd
1 sd
3 sd
4 qd
5 sd
7 sd
9 sd