day26--Java集合09

Java集合09

18.TreeSet

• 元素无序：插入顺序和输出顺序不一致
  
• 可以按照一定的规则进行排序，具体排序方式取决于构造方法：
  
  
  
  • TreeSet () ：根据其元素的自然排序进行排序
    
  • TreeSet (Comparator comparator) ：根据指定的比较器进行排序
    
  
  
• 没有带索引的方法，所以不能使用普通for循环遍历
  
• 由于是Set集合，不包含重复元素
  

[TreeSet集合的理解（自然排序和比较器排序）-CSDN博客]

例子：

1. package li.collection.set.treeset;
3. import java.util.Comparator;
4. import java.util.TreeSet;
6. @SuppressWarnings("all")
7. public class TreeSet_ {
8.     public static void main(String[] args) {
10.         //TreeSet treeSet = new TreeSet();
11.         TreeSet treeSet = new TreeSet(new Comparator() {//匿名内部类
12.             @Override
13.             public int compare(Object o1, Object o2) {
14.                 //下面调用String的compareTo方法进行字符串的小的比较
15.                 return ((String)o2).compareTo((String)o1);//从大到小
16.             }
17.         });
18.         //添加数据
19.         treeSet.add("lucy");
20.         treeSet.add("bob");
21.         treeSet.add("smith");
22.         treeSet.add("join");
23.         treeSet.add("mary");
24.         treeSet.add("q");
25.         System.out.println(treeSet);//[smith, q, mary, lucy, join, bob]
27.     }
28. }

复制代码

• 当我们使用无参构造器 创建TreeSet时，会有一个默认的比较器
  

  TreeSet可以对集合中的元素进行排序,在添加元素的时候会自动去调用Comparable接口的compareTo方法
  有些泛型类已经写好了排序规则，比如String 和 Integer 都已经实现了Comparable接口，也重写了compareTo方法
  

  
  
• 现在希望添加的元素按照字符串大小来排序
  
• 使用TreeSet提供的一个构造器，可以传入一个比较器（匿名内部类），并指定排序规则
  1. TreeSet treeSet = new TreeSet(new Comparator() {//匿名内部类
  2.             @Override
  3.             public int compare(Object o1, Object o2) {
  4.                 //下面调用String的compareTo方法进行字符串的小的比较
  5.                 return ((String)o2).compareTo((String)o1);//从大到小
  6.             }
  7.         });

  复制代码
• 简单看看源码
  4.1 构造器把传入的比较器对象付赋给了TreeSet底层TreeMap的属性this.comparator
  4.2在调用treeSet.add("lucy")时，在底层会执行到：
  1. if (cpr != null) {//cpr就是我们的匿名内部类（对象）
  2.     do {
  3.         parent = t;
  4.         cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类（对象）的compareTo方法
  5.         if (cmp < 0)
  6.             t = t.left;
  7.         else if (cmp > 0)
  8.             t = t.right;
  9.         else//如果相等，即返回0，这个key就没有加入
  10.             return t.setValue(value);
  11.     } while (t != null);
  12. }

  复制代码

思考：如果要求加入的元素按照长度大小排序该怎么写？

1. package li.collection.set.treeset;
3. import java.util.Comparator;
4. import java.util.TreeSet;
6. @SuppressWarnings("all")
7. public class TreeSet_ {
8.     public static void main(String[] args) {
10.         TreeSet treeSet = new TreeSet(new Comparator() {//匿名内部类
11.             @Override
12.             public int compare(Object o1, Object o2) {
13.                 //按照长度大小排序
14.                 return ((String)o2).length()-((String)o1).length();//长度从大到小
15.             }
16.         });
18.         treeSet.add("lucy");
19.         treeSet.add("bob");
20.         treeSet.add("q");
21.         System.out.println(treeSet);//[lucy, bob, q]
23.     }
24. }

复制代码

问：如果此时再使用add（）方法添加一个"jack"字符串，这个字符串可以添加进treeSet吗？
如上图，答案是不能。之前已经说过，在使用add（）方法时，底层会调用：

1. if (cpr != null) {//cpr就是我们的匿名内部类（对象）
2.     do {
3.         parent = t;
4.         cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类（对象）的compareTo方法
5.         if (cmp < 0)
6.             t = t.left;
7.         else if (cmp > 0)
8.             t = t.right;
9.         else//如果相等，即返回0，这个key就没有加入
10.             return t.setValue(value);
11.     } while (t != null);
12. }

复制代码

由于我们重写了compareTo方法，方法此时返回的是两个元素长度之差。
在do...while循环比较时，因为在加入“jack”之前已经有一个相同长度为4的字符串“lucy”，所以compareTo返回的值为0，即cmp=0，执行语句return t.setValue(value);
即 认为是同一个key，因此“jack”无法加入集合treeSet
19.TreeMap

例子：

1. package li.map.treemap;
2. import java.util.Comparator;
3. import java.util.TreeMap;
5. @SuppressWarnings("all")
6. public class TreeMap_ {
7.     public static void main(String[] args) {
8.         //使用默认的构造器穿件TreeMap,是无序的（也没有排序）
9.         //要求：按照传入的字符串（key）的大小进行排序
10.         //TreeMap treeMap = new TreeMap();
11.         TreeMap treeMap = new TreeMap(new Comparator() {
12.             @Override
13.             public int compare(Object o1, Object o2) {
14.                 //按照传入的字符串（key）的大小进行排序
15.                 //return ((String)o2).compareTo((String)o1);
17.                 //按照key的字符串长度大小排序
18.                 return ((String)o2).length()-((String)o1).length();
19.             }
20.         });
21.         treeMap.put("jack","杰克");
22.         treeMap.put("tom","汤姆");
23.         treeMap.put("kristina","克里斯提诺");
24.         treeMap.put("smith","史密斯");
25.         
26.         System.out.println(treeMap);//按照key的长度排序
27.         // {kristina=克里斯提诺, smith=史密斯, jack=杰克, tom=汤姆}
28.     }
29. }

复制代码

如下图：打上断点，点击debug，点击force step into进入到构造器中

• 把传入的实现了Comparator接口的匿名内部类（对象），传给 了TreeMap的comparator属性
  

<ol start="2">接下来调用put方法：
[code]public V put(K key, V value) {     // 先以 t 保存链表的 root 节点    Entry t = root;     // 如果 t==null，表明是一个空链表，即该 TreeMap 里没有任何 Entry     if (t == null)     {         // 将新的 key-value 创建一个 Entry，并将该 Entry 作为 root         root = new Entry(key, value, null);         // 设置该 Map 集合的 size 为 1，代表包含一个 Entry         size = 1;         // 记录修改次数为 1         modCount++;         return null;     }     int cmp;     Entry parent;     Comparator