A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

我是上海1030期的。这两天我们刚学完集合,感觉比起之前的东西难了不少。所以和大家交流下学习的心得。
昨天有同学在使用TreeMap嵌套创建集合,并添加比较器Comparator的时候,发现自己能正确获得内层集合的值,但获取不了外层集合的值,怀疑是不是java语言有bug了。我先把示例代码贴上来:

        TreeMap<Student, String> hm1 = new TreeMap<>();
        TreeMap<Student, String> hm2 = new TreeMap<>();
        hm1.put(new Student("波多野结衣",28), "日本");
        hm1.put(new Student("泷泽萝拉",18), "日本");
        hm1.put(new Student("早川濑里奈",20), "日本");
        hm1.put(new Student("瑠川丽娜",22), "日本");
        hm2.put(new Student("王祖贤",40), "香港");
        hm2.put(new Student("邱淑贞",38), "香港");
        hm2.put(new Student("李若彤",42), "香港");
        hm2.put(new Student("林熙蕾",30), "香港");
        TreeMap<TreeMap<Student, String>,String> sm1 = new TreeMap<>(new Comparator<TreeMap<Student, String>>(){
                @Override
                public int compare(TreeMap<Student, String> o1,
                                TreeMap<Student, String> o2){       
                        return 1;
                }
        });
        sm1.put(hm1, "Japan");
        sm1.put(hm2,"HongKong");
        for (TreeMap<Student, String> tm: sm1.keySet()) {       
                for(Student stu:tm.keySet()){
                        System.out.println(stu + "..." + tm.get(stu) + "..." + sm1.get(tm));
                }
        }

//--------------------------------------------------------------------------
这样子输出的结果如下:
Person [name=早川濑里奈, age=20]...日本...null
Person [name=波多野结衣, age=28]...日本...null
Person [name=泷泽萝拉, age=18]...日本...null
Person [name=瑠川丽娜, age=22]...日本...null
Person [name=李若彤, age=42]...香港...null
Person [name=林熙蕾, age=30]...香港...null
Person [name=王祖贤, age=40]...香港...null
Person [name=邱淑贞, age=38]...香港...null
然而用Entry的方式获取,却能够正确获取外层键对应的值。
第一眼看过去我也觉得奇怪。怎么外层获取不了Japan和HongKong了呢?是不是语言有bug了?
后来仔细研究发现不是这么回事。
//----------------------------------------
首先,这个问题不是出在增强for循环上。
因为把增强for循坏拆开,单独用sm1.get(key)的方式,发现结果也是null
同时这也说明,问题是出在了sm集合的get方法上,那么具体是哪里出了问题呢?之前张俊贤老师在教我们eclipse的时候讲到过debug调试,要简化问题,找出问题,我们就需要单独写一句sm1.get(hm1);然后“哪里不会点哪里”,在这句上设置断点。
//---------------------------------------------
设置断点跳入后,我们发现程序进入了TreeMap的源码:
   public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

在Entry<K,V> p = getEntry(key);语句上再设置断点,我们会发现程序跳入了:
final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
          ……
下面的我就不打了,因为到这里我们设置了自己的比较器,所以comparator != null成立,进入
return getEntryUsingComparator(key);
该方法余下的代码就不用看了,因为执行不到。
不过深入研究后我们可以发现这个问题的关键,就是当我们调用了集合的有参构造生成了比较器comparator后,TreeMap用comparator进行比较。
当comparator不存在(=null)时,程序会调用对象内部的比较器Comparable。
这个就是问题的关键了!
因为当我们用get(key)进行查找时,程序会判断两个键是否相等,若是相等,则返回该键的值。而这个相等的与否,就是用我们写的比较器进行判断的!
在这个代码中,我们为了方便存储,将比较器的返回值设恒为1,这就导致了当两个我们看来相等的键进行比较时,java认为他们不相等!当遍历完整个TreeMap后,依然找不到(java通过比较器比较认为)相同的键,所以返回null!此问题终结。重写比较器后程序正常!
//--------------------------------------------------
进而深入得研究TreeMap和二叉树的实现原理:
进入getEntryUsingComparator(key);后,我们可以很直观的了解到TreeMap底层的二叉树究竟是如何实现的,现在讲代码贴出:
final Entry<K,V> getEntryUsingComparator(Object key) {
        K k = (K) key;//将输入的键以泛型对应的具体类型进行强转
        Comparator<? super K> cpr = comparator;//创建比较器对象cpr
        if (cpr != null) {//如果比较器存在
            Entry<K,V> p = root;//映射p的初始位置为二叉树的根部,即你存入二叉树的第一个元素的地址
            while (p != null) {//如果该映射不为空,进入二叉树的遍历查询,直到映射为空为止
                int cmp = cpr.compare(k, p.key);//用比较器比较    输入的键和当前映射   是否相等
                if (cmp < 0)//若是我们输入的键小了
                    p = p.left;//则映射转移到到二叉树图中当前映射左下的元素
                else if (cmp > 0)//若是我们输入的键大了
                    p = p.right;//则映射转移到到二叉树图中当前映射右下的元素
                else//如果相等
                    return p;//则当前映射即为我们输入的键对应的那个映射,结束并返回该映射
            }
        }
        return null;//如果while遍历到二叉树的底部还找不到相同的键,则说明该二叉树中没有该键,返回null
    }

再附上一张当前断点下的变量表:


从图中我们可以发现,TreeMap的二叉树里每一个元素之间是通过链表的形式链接在一起的。我们存入的第一个元素的地址为root,其中包含该元素的
键、值、左下元素地址、右下元素地址、上一层节点的信息等,有兴趣的小伙伴可以自行尝试一个个点击查看其信息来了解。
将该图配合上面的getEntryUsingComparator方法,我们再回过头来看课上讲的TreeMap插值的方式,也是使用同一个原理。
首先进入root地址,取出其中的键和我们输入的键进行对比,若是大了,则指针向右下移动,若是小了则指针向左下移动,若是相等,则说明当前地址即为我们输入的键所对应的地址。说明二叉树实现的底层原理是链表结构!有兴趣的小伙伴,可以根据这个原理尝试自己写下TreeMap和TreeSet集合。
打了这么多字,谢谢大家的观看和反馈。




1.png (17.3 KB, 下载次数: 18)

TreeMap变量图

TreeMap变量图

14 个回复

倒序浏览
第一次发帖子。求鼓励
回复 使用道具 举报
yubail 来自手机 中级黑马 2015-11-24 22:17:59
藤椅
我是来顶你的
回复 使用道具 举报
前面的还能看懂,后面涉及到原码我也就晕了
回复 使用道具 举报
不错,王导,顶你一个
回复 使用道具 举报
bobo大王 来自手机 中级黑马 2015-11-24 22:21:36
地板
王导,顶一个,完美
回复 使用道具 举报
wunaihaoye 发表于 2015-11-24 22:18
前面的还能看懂,后面涉及到原码我也就晕了

前面的几句源码就是转跳方法。关键的实现方法那段我每句都加注释了。有问题我们可以交流下
回复 使用道具 举报
可能我说的不是很清楚。
简单的说就是当你重写了比较器Comparator的时候,你的put方法和get方法都会调用该比较器了。
当你put键值的时候,比较器恒不为0自然是方便你加元素。
但是当你使用get函数时,java认为你get(key)里的key和集合里的键都不相同(比较器无法得到0),所以输出null
解决该问题的方法就是在写比较器时,千万不要图方便返回常量(如-1,1之类),只要你返回了常量,那么get(key)方法获得的就永远是null!
回复 使用道具 举报
写的真详细 看完我也学习到了 谢谢分享 必须鼓励  很棒!!!
回复 使用道具 举报
wunaihaoye 来自手机 中级黑马 2015-11-24 22:46:56
10#
gracefulwind 发表于 2015-11-24 22:35
可能我说的不是很清楚。
简单的说就是当你重写了比较器Comparator的时候,你的put方法和get方法都会调用该 ...

这样说就明白了
回复 使用道具 举报

之前是想通过解释源码来说明的。可能是没组织好语言,给大家造成困扰了T.T
不过观察源码能直观的了解到二叉树的实现原理,感觉看下还是挺有意义的。
回复 使用道具 举报
我来顶贴啦,加油吧
回复 使用道具 举报
厉害啊,看你一帖,顶得上自学三十天了
回复 使用道具 举报
oup 中级黑马 2015-11-24 23:05:57
14#
感觉好难
回复 使用道具 举报
gracefulwind 发表于 2015-11-24 22:35
可能我说的不是很清楚。
简单的说就是当你重写了比较器Comparator的时候,你的put方法和get方法都会调用该 ...

因为冯佳的视频里做案例演示的时候要求可以保留重复的元素..所以比较器都是返回的1,然后就顺着写习惯了...
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马