我是上海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, 下载次数: 16)
TreeMap变量图
|