黑马程序员技术交流社区

标题: 如何修改TreeMap集合的root？ [打印本页]
作者: Tking    时间: 2014-4-5 21:35
标题: 如何修改TreeMap集合的root？
如何修改TreeMap集合的root？
所谓root，就是根。
根：每次新建一个二叉树集合，存放的第一个元素，该集合默认该元素为根，也称root，以后每次进来的元素都有先和root比较后才决定向大（右）的方向存，还是向小（左）的方向走
  1. import java.lang.reflect.Constructor;
  2. import java.lang.reflect.Field;
  3. import java.util.*;
  4. import java.util.Map.Entry;
  5. public class Demo11 {
  6. public static void main(String[] args)throws Exception
  7. {
  8. TreeMap tm=new TreeMap();
  9. tm.put(new Test(10), 10);//这里的tm集合的root为new Test(10);
  10. tm.put(new Test(5), 5);
  11. tm.put(new Test(20), 20);
  12. tm.put(new Test(1), 1);
  13. System.out.println(tm);
  14. }
  15. }

  17. class Test implements Comparable<Test>
  18. {
  19. public int num;
  20. int i=1;
  21. Test(int num)
  22. {
  23. this.num=num;
  24. }
  25. public int compareTo(Test test)
  26. {
  27. System.out.println(this.num+"对象-第【"+(i++)+"】次和"+test.num+"对象-比较");
  28. return test.num-this.num;
  29. }
  30. Public boolean equals(Object obj)
  31. {
  32. Return this.num==((Test)obj).num?true:false;
  33. }
  34. public String toString()
  35. {
  36. return ""+num;
  37. }
  38. }
复制代码
运行结果为：
  1. 10对象-第【1】次和10对象-比较
  2. 5对象-第【1】次和10对象-比较
  3. 20对象-第【1】次和10对象-比较
  4. 1对象-第【1】次和10对象-比较
  5. 1对象-第【2】次和5对象-比较
  6. {20=20, 10=10, 5=5, 1=1}
复制代码
自从10进来后，每次进来一个元素，都必须和10比较一次，再和其他比较。
现在的要求：
在不删除原有根的前提下，添加一个元素，代替原有根的位置，让以后进来的元素第一次先和新root比较。
这里先简介下TreeMap内部负责存储的成员。
  1. TreeMap
  2. |——Entry<K,V> root
  3. |——K key
  4. |——V value
  5. |——Entry<K,V> left  //比root的key小的元素对将存放在left
  6. |——Entry<K，V> reght //比root的key大的元素将存放在reght
  7. |——Entry<K,V>  parent //指向null
复制代码
了解了这些后，只需要拿到TreeMap.Entry的构造方法和parent 与left(或reght)成员变量就可以完成，但是TreeMap集合拒绝外界创建他内部类的对象~~~~~~
没办法只好用反射来完成了!!.

1.首先拿到TreeMap内所有内部类的的字节码。
  1. Class[] clazz=tm.getClass().getDeclaredClasses();
  2. for(Class i:clazz)
  3. System.out.println(i);
复制代码
运行结果：
  1. class java.util.TreeMap$AscendingSubMap            0
  2. class java.util.TreeMap$DescendingKeyIterator       1
  3. class java.util.TreeMap$DescendingSubMap         2
  4. class java.util.TreeMap$Entry             3
  5. class java.util.TreeMap$EntryIterator         4
  6. ........           .....<span style="color: rgb(0, 0, 0); font-family: 宋体; font-size: 10.5pt; text-indent: 21pt; line-height: 1.5;"> </span>
复制代码
发现第三个是要找的内部类.
然后
  1. //拿到TreeMap的root
  2. Field rootfield=tm.getClass().getDeclaredField("root");
  3. //拿到TreeMap.Entry的parent和left成员
  4. Field parentfield=clazz[3].getDeclaredField("parent");
  5. Field leftfield =clazz[3].getDeclaredField("left");
  6. //获得TreeMap.Entry的构造方法
  7. Constructor[] con=clazz[3].getDeclaredConstructors();
复制代码
有了这些就好办了。
2.实施暴力访问（名字好恐怖，好暴力）.因为这些都是不对外界提供访问，所以要这么做。
  1. parentfield.setAccessible(true);
  2. rootfield.setAccessible(true);
  3. con[0].setAccessible(true);
  4. leftfield.setAccessible(true);
复制代码
3.利用反射过来的构造方法创建一个将要代替原root的Entry对象。这个对象要什么类申明呢？？TreeMap.Entry??还是Collection?或者Map？？
  1. Entry newroot=(Entry)con[0].newInstance(new Test(100),100,null);
复制代码
没错就用它接收吧！！
TreeMap集合中所有Entry对象的parent都是有指定指向，除了root的指向始终null，所以这里这里要null(也可以指向其他的Entry对象,不过会偷偷跑进集合里去，又取不出来）。
4.进行修改指向（这里有点复杂，每一句都不能少）
  1. 1>（谋权）让原root的parentfield指向了newroot，虽然已经存在集合里，但是集合是不能访问root的parent属性，所以去取的时候是个null。
  2. parentfield.set(rootfield.get(tm), newroot);

  4. 2>（造反）设置newroot的left（或regth）指向，既然是根的话左右两边的叉至少要有一个有指向，除非只有根存在。
  5. leftfield.set(newroot, rootfield.get(tm));

  7. 3>（篡位）将原root的指向改成newroot，也就是篡位，正式宣布newroot已经是新的root了。
  8. rootfield.set(tm, newroot);
复制代码
接下来在打印一下就会发现
System.out.println(tm);
运行结果：
  1. 10对象-第【1】次和10对象-比较
  2. 5对象-第【1】次和10对象-比较
  3. 20对象-第【1】次和10对象-比较
  4. 1对象-第【1】次和10对象-比较
  5. 1对象-第【2】次和5对象-比较
  6. {20=20, 10=10, 5=5, 1=1}
  7. {20=20, 10=10, 5=5, 1=1, 100=100}
复制代码
这个键值对已经成功加入了集合，而且以后再进来键值对，都会先和newroot的键值对比较。
  1. tm.put(new Test(10), 10);以后再次添加的时候第一次比较的就是100了
  2. tm.put(new Test(5), 5);
  3. tm.put(new Test(20), 20);
  4. tm.put(new Test(1), 1);
复制代码
运行结果：
  1. 10对象-第【1】次和10对象-比较
  2. 5对象-第【1】次和10对象-比较
  3. 20对象-第【1】次和10对象-比较         没篡位之前的比较数据
  4. 1对象-第【1】次和10对象-比较
  5. 1对象-第【2】次和5对象-比较
  6. {20=20, 10=10, 5=5, 1=1}
  7. {20=20, 10=10, 5=5, 1=1, 100=100}
  8. 10对象-第【1】次和100对象-比较
  9. 5对象-第【1】次和100对象-比较
  10. 5对象-第【2】次和10对象-比较         篡位之后再添加的比较数据
  11. 20对象-第【1】次和10对象-比较
  12. 20对象-第【2】次和100对象-比较
  13. 1对象-第【1】次和10对象-比较
  14. 1对象-第【2】次和5对象-比较
复制代码
而且这样还可以跳过TreeMap集合key唯一的特性，存放相同key在集合里，不过那样取出来的话，都是取距离根最近的key所对应Value。（没意义····）
用Map.Entry取出键值对关系的话，应该可以有意义~！~~
总结：
（谋权）让原root的parent指向新root。
只写了（谋权）或者（谋权和造反）时，原root没变，以后进来的元素还是要和原root比较，而且用常规的Key索引不到，隐藏起来了。但会在集合中出现。用关系迭代器可以取出。
（造反）让新root的分叉指向原root。
只写了（造反）时，虽然集合存在指向，但是无法访问到，无法取出新root，只能取出其他元素。
只写了（造反和篡位）时，集合内无法显示，迭代关系也无法显示，但是可以取出，却新root，其他元素虽然在集合显示出来，但是无法取出。（好像病毒一样，看的见，干不掉）
（篡位）让集合接受新root。
只写了（篡位）或者（谋权和篡位）时，就等于把集合里所有元素都删掉，只留下一个新的root在里面。（这招很绝··慎用！！）
搞的好像在当皇帝第一样·~~~~~~~~~~~~~~~~~~
作者: Tking    时间: 2014-4-5 21:36
求能够支持work文档或者wps，不然写过一次的东西又写一次，还要考虑字数，好难！！~~~:'(



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