我是上海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, 下载次数: 19)
TreeMap变量图
|
收藏
淘帖
踩
