TreeMap 实现降序原理及Key 是否可以为 null

不念不忘少年蓝@ 2022-07-16 00:37 403阅读 0赞

## 一、TreeMap 实现降序排列的原理 ##

TreeMap 底层为数据结构为红黑树，默认为升序排序方式。整个红黑树的结构为：根节点值大于所有左子树节点值，小于所有右子树节点值，由此整个红黑树以深度优先搜索方式遍历一遍为从小到大的升序排列。  
如需改为降序排列方式，则应自定义实现 Comparator 接口。

降序排列实现示例：

Map<Integer, Object> map = new TreeMap<Integer, Object>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    
    map.put(1, 111);
    map.put(2, 222);
    map.put(3, 333);
    map.put(4, 444);
    map.put(5, 555);
    
    System.out.println(map);

输出为：  
![这里写图片描述][20160925135148278]

为何会如此定义 Comparator 实现呢？查看 compare 接口注释如下：  
![compare接口注释][compare]

由 compare 接口注释可知，返回负数表示比较的两个对象 o1 小于 o2, 0 表示 o1 等于 o2, 正数表示 o1 大于 o2。

而 TreeMap put方法实现为：  
![TreeMap实现][TreeMap]

由上图可知，TreeMap put操作时，将put操作的key和此时红黑树的根节点root对应的 t.key 进行比较时：

*  小于0，则根节点往左子树节点移动；
 *  大于0，则根节点往右子树节点移动；
 *  相等时，将当前节点值设为put操作的 value；
 *  遍历到无左右子节点时，将节点插入（此处涉及到红黑树的旋转，参看红黑树插入原理）。

由此可得，当要降序排列时，则需让更大的值往左子树节点移动，即：

Map<Integer, Object> map = new TreeMap<Integer, Object>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

注：o1 表示put进TreeMap的key，o2表示已经存在于TreeMap的key。根据 compare(o1, o2) 的返回值决定o1 的位置。

## 二、TreeMap key值是否可以为null ##

先放出结论：  
  
1. 当未实现 Comparator 接口时，key 不可以为null，否则抛 NullPointerException 异常；  
2. 当实现 Comparator 接口时，若未对 null 情况进行判断，则可能抛 NullPointerException 异常。  
  
1、当未实现 Comparator 接口时，查看 put 源码：  
![TreeMap put 源码][TreeMap put]

由源码可知，当TreeMap不为空时，key 为 null，则抛 NullPointerException 异常；

当 TreeMap 为空时，put 操作，调用 compare() 方法，源码为：  
![这里写图片描述][20160925143522105]

假如此时 K 类型为Integer，将 key 强制转换时，抛 NullPointerException 异常；

2、当实现 Comparator 接口时, 若未对 null 情况作出判断，则可能抛 NullPointerException 异常：  
![这里写图片描述][20160925145616133]

对对象进行 null 判断的实现示例如下：

public static void main(String[] args) {
        Map<Integer, Object> map1 = new TreeMap<Integer, Object>(new Comparator<Integer>() {
           @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 != null && o2 != null) {
                    return o1 - o2;
                }
                if (o1 == null && o2 != null) {
                    return -1;
                }
                if (o1 != null && o2 == null) {
                    return 1;
                }
                return 0;
            }
        });
        map1.put(2, "222");
        map1.put(null, "111");
        System.out.println(map1);
    }

输出为：  
![这里写图片描述][20160925150218601]

[20160925135148278]: /images/20220716/6f7ae3f879854010a1235f053d499232.png
[compare]: /images/20220716/2218975e88e74fb1ac0d78fc6ec7b456.png
[TreeMap]: /images/20220716/268fadfbf41945139b7f134f4a816b62.png
[TreeMap put]: /images/20220716/32cdc266a97a4b0abd80995ea23f83c7.png
[20160925143522105]: /images/20220716/10b39e317ff247e9b0d45ff332563340.png
[20160925145616133]: /images/20220716/f421c1c5467446b392dbecfcd2aa74e4.png
[20160925150218601]: /images/20220716/4bd7bdc0291b4b1b9252065d201d3b5a.png