黑马程序员技术交流社区

标题: 这两天刚学完map集合，一点小心得分享给大家 [打印本页]

作者: gracefulwind 时间: 2015-11-24 22:05
标题: 这两天刚学完map集合，一点小心得分享给大家
我是上海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, 下载次数: 17)

TreeMap变量图

作者: gracefulwind 时间: 2015-11-24 22:09
第一次发帖子。求鼓励

作者: yubail 时间: 2015-11-24 22:17
我是来顶你的

作者: wunaihaoye 时间: 2015-11-24 22:18
前面的还能看懂，后面涉及到原码我也就晕了

作者: 狙击超超 时间: 2015-11-24 22:18
不错,王导,顶你一个

作者: bobo大王 时间: 2015-11-24 22:21
王导，顶一个，完美

作者: gracefulwind 时间: 2015-11-24 22:21

wunaihaoye 发表于 2015-11-24 22:18
前面的还能看懂，后面涉及到原码我也就晕了

前面的几句源码就是转跳方法。关键的实现方法那段我每句都加注释了。有问题我们可以交流下

作者: gracefulwind 时间: 2015-11-24 22:35
可能我说的不是很清楚。
简单的说就是当你重写了比较器Comparator的时候，你的put方法和get方法都会调用该比较器了。
当你put键值的时候，比较器恒不为0自然是方便你加元素。
但是当你使用get函数时，java认为你get(key)里的key和集合里的键都不相同(比较器无法得到0),所以输出null
解决该问题的方法就是在写比较器时，千万不要图方便返回常量(如-1,1之类)，只要你返回了常量，那么get(key)方法获得的就永远是null！

作者: 袁有福123 时间: 2015-11-24 22:39
写的真详细看完我也学习到了谢谢分享必须鼓励很棒！！！

作者: wunaihaoye 时间: 2015-11-24 22:46

gracefulwind 发表于 2015-11-24 22:35
可能我说的不是很清楚。
简单的说就是当你重写了比较器Comparator的时候，你的put方法和get方法都会调用该 ...

这样说就明白了

作者: gracefulwind 时间: 2015-11-24 22:55

wunaihaoye 发表于 2015-11-24 22:46
这样说就明白了

之前是想通过解释源码来说明的。可能是没组织好语言，给大家造成困扰了T.T
不过观察源码能直观的了解到二叉树的实现原理，感觉看下还是挺有意义的。

作者: cuiyaqian 时间: 2015-11-24 23:01
我来顶贴啦,加油吧

作者: litoper 时间: 2015-11-24 23:01
厉害啊,看你一帖,顶得上自学三十天了

作者: oup 时间: 2015-11-24 23:05
感觉好难

作者: 阳光小小桃 时间: 2015-11-24 23:49

gracefulwind 发表于 2015-11-24 22:35
可能我说的不是很清楚。
简单的说就是当你重写了比较器Comparator的时候，你的put方法和get方法都会调用该 ...

因为冯佳的视频里做案例演示的时候要求可以保留重复的元素..所以比较器都是返回的1,然后就顺着写习惯了...

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2