中招了,重写TreeMap的比较器引发的问题...(下)

简介: 中招了,重写TreeMap的比较器引发的问题...(下)

这种情况下,就会覆盖原来的值,这个就是我们执行 putAll 后,元素缺失的原因了。


image.png


好了既然问题找到了,那如何解决这个问题呢?


如果是你,你会怎么解决呢?可以花一分钟时间思考一下,再看后面的内容。


4、解决 TreeMap.putAll,元素缺失的问题


我当时想到最直接的方案就是,在 value 相等的情况下,不返回 0,返回1 or -1,这样就可以最简单、最快捷的解决这个问题了。


修改后的代码如下所示:


// 这里换了一种写法,是java8的特性,简化了代码(为了偷懒)
Map<Long, Integer> treeMap2 = new TreeMap<>((key1, key2) -> {
    // 1、如果v1等于v2,则值为0
    // 2、如果v1小于v2,则值为-1
    // 3、如果v1等于v2,则值为1
    Integer value1 = map.get(key1);
    Integer value2 = map.get(key2);
    int result = value1.compareTo(value2);
    if (result == 0) {
        return -1;
    }
    return result;
});
treeMap2.putAll(map);
System.out.println(treeMap2);


运行后的结果为:


{3=10, 1=10, 2=20}


我们可以发现,3个值都有了,并且是有序的,完美符合需求!好了,关机下班!


image.png


然而事情并没有结束 (大家可以想一下,这样写会有什么问题呢?)


新的问题出现


第二天,高高兴兴的写着业务代码、调试逻辑,突然一个 空指针 的报错,出现了。这也太常见了吧,3分钟内解决!


image.png


排查了半天,发现又回到了昨天的修改的那段逻辑了。


1、TreeMap.get 获取不到值


简化版代码如下所示:


// 假设,key=商品id,value=商品剩余库存
Map<Long, Integer> map = new HashMap<>();
map.put(1L, 10);
map.put(2L, 20);
map.put(3L, 10);
// 排序
Map<Long, Integer> treeMap2 = new TreeMap<>((key1, key2) -> {
    Integer value1 = map.get(key1);
    Integer value2 = map.get(key2);
    int result = value1.compareTo(value2);
    if (result == 0) {
        return -1;
    }
    return result;
});
treeMap2.putAll(map);
System.out.println(treeMap2);
// 获取商品1的剩余数量
Integer quantity = treeMap2.get(1L);
System.out.println(quantity);


运行后的结果为:


{3=10, 1=10, 2=20}
null


这个结果令我百思不得其解,只能看看源码咯。


2、分析 TreeMap.get


源码如下所示:


public V get(Object key) {
    // 根据key获取节点
    TreeMap.Entry<K,V> p = getEntry(key);
    // 节点为空则返回null,否则返回节点的 value 值
    return (p==null ? null : p.value);
}
final TreeMap.Entry<K,V> getEntry(Object key) {
    // 一、如果比较器不为空,则执行一下逻辑
    if (comparator != null)
        // 1、使用自定义比较器取出key对应的节点
        return getEntryUsingComparator(key);
    // 二、如果比较器为空,且key为null,则抛空指针异常
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    TreeMap.Entry<K,V> p = root;
    // 三、取出key对应的节点
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}


从上面的源码,我们可以发现,问题肯定就是出现在 getEntryUsingComparator 方法里了。


2、分析 TreeMap.getEntryUsingComparator


源码如下所示:


final TreeMap.Entry<K,V> getEntryUsingComparator(Object key) {
    // 一、将key转换成对应的类型
    @SuppressWarnings("unchecked")
    K k = (K) key;
    // 二、获取比较器
    Comparator<? super K> cpr = comparator;
    // 三、判断比较器是否为空
    if (cpr != null) {
        // 1、遍历map,取出key对应的节点对象
        TreeMap.Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            // 2、如果小于0,则将左节点的值赋值给p
            if (cmp < 0)
                p = p.left;
            // 3、如果大于0,则将右节点的值赋值给p
            else if (cmp > 0)
                p = p.right;
            else
                // 4、如果等于0,则返回p节点
                return p;
        }
    }
    return null;
}


结合上面的源码,和我们之前自定义的比较器,我们不难发现问题出现在哪里:


image.png


自定义比较器,没有返回0的情况


问题找到了,解决吧!

目录
打赏
0
0
0
0
23
分享
相关文章
探索Java集合的3种遍历方式
传统的集合遍历方式 在Java中,我们可以使用传统的循环和迭代器来遍历集合
246 2
【C++】红黑树的简单模拟实现
红黑树和AVL树类似,是对搜索树的优化。不同于AVL树的绝对平衡,红黑树是近似平衡,即对于每个节点的以它为根的所有路径,其中最长路径的节点数不大于最短路径节点数的2倍。
PAT乙级(简单模拟)1001、1011、1016、1026、1046、1012、1018(二)
PAT乙级(简单模拟)1001、1011、1016、1026、1046、1012、1018
165 0
PAT乙级(简单模拟)1001、1011、1016、1026、1046、1012、1018(二)
PAT乙级(简单模拟)1001、1011、1016、1026、1046、1012、1018(一)
PAT乙级(简单模拟)1001、1011、1016、1026、1046、1012、1018
125 0
【Java集合类】之Map集合的特点及使用
【Java集合类】之Map集合的特点及使用
175 0
C#(二十五)之C#对象比较
本篇内容记录了比较对象的方法、重写实例Equals方法。
154 0
C#(二十五)之C#对象比较
中招了,重写TreeMap的比较器引发的问题...(上)
中招了,重写TreeMap的比较器引发的问题...(上)
中招了,重写TreeMap的比较器引发的问题...(上)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等