Java集合09

18.TreeSet

• 元素無序：插入順序和輸出順序不一致
• 可以按照一定的規則進行排序，具體排序方式取決于構造方法：
  • TreeSet () ：根據其元素的自然排序進行排序
  • TreeSet (Comparator comparator) ：根據指定的比較器進行排序
• 沒有帶索引的方法，所以不能使用普通for回圈遍歷
• 由于是Set集合，不包含重復元素

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

例子：

package li.collection.set.treeset;

import java.util.Comparator;
import java.util.TreeSet;

@SuppressWarnings("all")
public class TreeSet_ {
    public static void main(String[] args) {

        //TreeSet treeSet = new TreeSet();
        TreeSet treeSet = new TreeSet(new Comparator() {//匿名內部類
            @Override
            public int compare(Object o1, Object o2) {
                //下面呼叫String的compareTo方法進行字串的小的比較
                return ((String)o2).compareTo((String)o1);//從大到小
            }
        });
        //添加資料
        treeSet.add("lucy");
        treeSet.add("bob");
        treeSet.add("smith");
        treeSet.add("join");
        treeSet.add("mary");
        treeSet.add("q");
        System.out.println(treeSet);//[smith, q, mary, lucy, join, bob]

    }
}

1. 當我們使用無參構造器 創建TreeSet時，會有一個默認的比較器

   TreeSet可以對集合中的元素進行排序,在添加元素的時候會自動去呼叫Comparable介面的compareTo方法

   有些泛型類已經寫好了排序規則，比如String 和 Integer 都已經實作了Comparable介面，也重寫了compareTo方法

2. 現在希望添加的元素按照字串大小來排序

3. 使用TreeSet提供的一個構造器，可以傳入一個比較器（匿名內部類），并指定排序規則

   TreeSet treeSet = new TreeSet(new Comparator() {//匿名內部類
               @Override
               public int compare(Object o1, Object o2) {
                   //下面呼叫String的compareTo方法進行字串的小的比較
                   return ((String)o2).compareTo((String)o1);//從大到小
               }
           });
   

4. 簡單看看原始碼
   4.1 構造器把傳入的比較器物件付賦給了TreeSet底層TreeMap的屬性this.comparator

   

   ---

   

   4.2在呼叫treeSet.add("lucy")時，在底層會執行到：

   if (cpr != null) {//cpr就是我們的匿名內部類（物件）
       do {
           parent = t;
           cmp = cpr.compare(key, t.key);//動態系結到我們的匿名內部類（物件）的compareTo方法
           if (cmp < 0)
               t = t.left;
           else if (cmp > 0)
               t = t.right;
           else//如果相等，即回傳0，這個key就沒有加入
               return t.setValue(value);
       } while (t != null);
   }
   

思考：如果要求加入的元素按照長度大小排序該怎么寫？

package li.collection.set.treeset;

import java.util.Comparator;
import java.util.TreeSet;

@SuppressWarnings("all")
public class TreeSet_ {
    public static void main(String[] args) {

        TreeSet treeSet = new TreeSet(new Comparator() {//匿名內部類
            @Override
            public int compare(Object o1, Object o2) {
                //按照長度大小排序
                return ((String)o2).length()-((String)o1).length();//長度從大到小
            }
        });

        treeSet.add("lucy");
        treeSet.add("bob");
        treeSet.add("q");
        System.out.println(treeSet);//[lucy, bob, q]

    }
}

問：如果此時再使用add（）方法添加一個"jack"字串，這個字串可以添加進treeSet嗎？

如上圖，答案是不能，之前已經說過，在使用add（）方法時，底層會呼叫：

if (cpr != null) {//cpr就是我們的匿名內部類（物件）
    do {
        parent = t;
        cmp = cpr.compare(key, t.key);//動態系結到我們的匿名內部類（物件）的compareTo方法
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else//如果相等，即回傳0，這個key就沒有加入
            return t.setValue(value);
    } while (t != null);
}

由于我們重寫了compareTo方法，方法此時回傳的是兩個元素長度之差，

在do...while回圈比較時，因為在加入“jack”之前已經有一個相同長度為4的字串“lucy”，所以compareTo回傳的值為0，即cmp=0，執行陳述句return t.setValue(value);

即 認為是同一個key，因此“jack”無法加入集合treeSet

19.TreeMap

例子：

package li.map.treemap;
import java.util.Comparator;
import java.util.TreeMap;

@SuppressWarnings("all")
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默認的構造器穿件TreeMap,是無序的（也沒有排序）
        //要求：按照傳入的字串（key）的大小進行排序
        //TreeMap treeMap = new TreeMap();
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //按照傳入的字串（key）的大小進行排序
                //return ((String)o2).compareTo((String)o1);

                //按照key的字串長度大小排序
                return ((String)o2).length()-((String)o1).length();
            }
        });
        treeMap.put("jack","杰克");
        treeMap.put("tom","湯姆");
        treeMap.put("kristina","克里斯提諾");
        treeMap.put("smith","史密斯");
        
        System.out.println(treeMap);//按照key的長度排序
        // {kristina=克里斯提諾, smith=史密斯, jack=杰克, tom=湯姆}
    }
}

如下圖：打上斷點，點擊debug，點擊force step into進入到構造器中

1. 把傳入的實作了Comparator介面的匿名內部類（物件），傳給 了TreeMap的comparator屬性

2. 接下來呼叫put方法：

   public V put(K key, V value) 
   { 
       // 先以 t 保存鏈表的 root 節點
       Entry<K,V> t = root; 
       // 如果 t==null，表明是一個空鏈表，即該 TreeMap 里沒有任何 Entry 
       if (t == null) 
       { 
           // 將新的 key-value 創建一個 Entry，并將該 Entry 作為 root 
           root = new Entry<K,V>(key, value, null); 
           // 設定該 Map 集合的 size 為 1，代表包含一個 Entry 
           size = 1; 
           // 記錄修改次數為 1 
           modCount++; 
           return null; 
       } 
       int cmp; 
       Entry<K,V> parent; 
       Comparator<? super K> cpr = comparator; 
       // 如果比較器 cpr 不為 null，即表明采用定制排序
       if (cpr != null) 
       { 
           do { 
               // 使用 parent 上次回圈后的 t 所參考的 Entry 
               parent = t; 
               // 拿新插入 key 和 t 的 key 進行比較
               cmp = cpr.compare(key, t.key); 
               // 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點
               if (cmp < 0) 
                   t = t.left; 
               // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點
               else if (cmp > 0) 
                   t = t.right; 
               // 如果兩個 key 相等，新的 value 覆寫原有的 value，
               // 并回傳原有的 value 
               else 
                   return t.setValue(value); 
           } while (t != null); 
       } 
       else 
       { 
           if (key == null) 
               throw new NullPointerException(); 
           Comparable<? super K> k = (Comparable<? super K>) key; 
           do { 
               // 使用 parent 上次回圈后的 t 所參考的 Entry 
               parent = t; 
               // 拿新插入 key 和 t 的 key 進行比較
               cmp = k.compareTo(t.key); 
               // 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點
               if (cmp < 0) 
                   t = t.left; 
               // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點
               else if (cmp > 0) 
                   t = t.right; 
               // 如果兩個 key 相等，新的 value 覆寫原有的 value，
               // 并回傳原有的 value 
               else 
                   return t.setValue(value); 
           } while (t != null); 
       } 
       // 將新插入的節點作為 parent 節點的子節點
       Entry<K,V> e = new Entry<K,V>(key, value, parent); 
       // 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的左子節點
       if (cmp < 0) 
           parent.left = e; 
       // 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的右子節點
       else 
           parent.right = e; 
       // 修復紅黑樹
       fixAfterInsertion(e);                              
       size++; 
       modCount++; 
       return null; 
   }
   

   ? 2.1第一次添加時，把 k-v 封裝到Entry物件中，并放入root

   // 先以 t 保存鏈表的 root 節點
       Entry<K,V> t = root; 
       // 如果 t==null，表明是一個空鏈表，即該 TreeMap 里沒有任何 Entry 
       if (t == null) 
       { 
           // 將新的 key-value 創建一個 Entry，并將該 Entry 作為 root 
           root = new Entry<K,V>(key, value, null); 
           // 設定該 Map 集合的 size 為 1，代表包含一個 Entry 
           size = 1; 
           // 記錄修改次數為 1 
           modCount++; 
           return null; 
       } 
   

   ? 2.2 之后的添加：

     Comparator<? super K> cpr = comparator; 
       // 如果比較器 cpr 不為 null，即表明采用定制排序
       if (cpr != null) 
       { 
           do { 
               // 使用 parent 上次回圈后的 t 所參考的 Entry 
               parent = t; 
               // 拿新插入 key 和 t 的 key 進行比較
               cmp = cpr.compare(key, t.key); 
               // 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點
               if (cmp < 0) 
                   t = t.left; 
               // 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點
               else if (cmp > 0) 
                   t = t.right; 
               // 如果兩個 key 相等，新的 value 覆寫原有的 value，
               // 并回傳原有的 value 
               else 
                   return t.setValue(value); 
           } while (t != null); 
       } 
   

   思考：重寫了compareTo方法之后，現在比較的是key的長度，如果在treeMap集合中加入K-V，該key與集合中的某個key長度相同，結果會如何？

   答案：key不會被替換，但是value值會被最新的替換

   

20.Collections工具類

20.1排序

1. Collections是一個提供操作Set、List和Map等集合的工具類
2. Collections中提供了一系列靜態的方法，對集合元素進行排序、查詢和修改等操作

• 排序操作：

  • reverse（List）：反轉List中元素的順序

  • shuffle（List）：對List集合元素進行隨機排序

  • sort（List）：根據元素的自然順序對指定List集合元素進行升序排序

  • sort（List，Comparator）：根據指定的Comparator產生的順序對List集合元素進行排序

  • swap（List，int，int）：將制定List集合中的 i 處元素和 j 處元素進行交換

排序操作例子：

package li.collection.collectionskit;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

@SuppressWarnings("all")
public class Collections_ {
    public static void main(String[] args) {

        //創建一個ArrayList集合用于測驗
        List list = new ArrayList();
        list.add("tom");
        list.add("smith");
        list.add("king");
        list.add("milan");

        //- reverse（List）：反轉List中元素的順序
        Collections.reverse(list);
        System.out.println("reverse:" + list);//[milan, king, smith, tom]

        
        //- shuffle（List）：對List集合元素進行隨機排序
        Collections.shuffle(list);
        System.out.println("shuffle:" + list);//每一次輸出的順序都不一樣

        
        //- sort（List）：根據元素的自然順序對指定List集合元素進行升序排序
        Collections.sort(list);
        System.out.println("自然排序后" + list);//自然排序是按照字串的大小來排的
        
        
        //- sort（List,Comparator）：根據指定的Comparator產生的順序對List集合元素進行排序
        //指定排序規，例如希望按照字串的長度大小來排序
        Collections.sort(list, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String) o1).length() - ((String) o2).length();
            }
        });
        //注意這里可以輸出字串長度相同的字符，因為是list，允許重復，不用比較key
        System.out.println("按字串長度大小排序：" + list);//按照字串長度大小排序：[tom, king, milan, smith]
        
        
        //- swap（List,int,int）：將制定List集合中的 i 處元素和 j 處元素進行交換
        Collections.swap(list,1,3 );
        System.out.println("交換后的排序："+list);

    }
}

20.2查找、替換

1. Object max（Collection）：根據元素的自然順序，回傳給定集合中的最大元素
2. Object max（Collection，Comparator）：根據Comparator指定的順序，回傳給定集合中的最大元素
3. Object min（Collection）：根據元素的自然順序，回傳給定集合中的最小元素
4. Object min（Collection，Comparator）：根據Comparator指定的順序，回傳給定集合中的最小元素
5. int frequency（Collection，Object）：回傳指定集合中指定元素的出現次數
6. void copy（List dest，List src）：將src中的內容復制到dest中
7. boolean replaceAll（List list，Object oldVal，Object oldVal，Object newVal）：使用新值替換List物件的所有舊值

例子：

package li.collection.collectionskit;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

@SuppressWarnings("all")
public class Collections_ {
    public static void main(String[] args) {

        //創建一個ArrayList集合用于測驗
        List list = new ArrayList();
        list.add("tom");
        list.add("smith");
        list.add("king");
        list.add("milan");


        //1. Object max（Collection）：根據元素的自然順序，回傳給定集合中的最大元素
        System.out.println("自然順序最大元素：" + Collections.max(list));//自然順序最大元素：tom


        //2. Object max（Collection，Comparator）：根據Comparator指定的順序，回傳給定集合中的最大元素
        //比如回傳長度最大的元素
        Object maxObject = Collections.max(list, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String) o1).length() - ((String) o2).length();
            }
        });
        System.out.println("長度最大的元素："+maxObject);//長度最大的元素：smith


        //3. Object min（Collection）：根據元素的自然順序，回傳給定集合中的最小元素
        System.out.println("自然順序最小元素：" + Collections.min(list));//自然順序最小元素：king


        //4. Object min（Collection，Comparator）：根據Comparator指定的順序，回傳給定集合中的最小元素
        //比如回傳長度最大的元素
        Object minObject = Collections.min(list, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String) o1).length() - ((String) o2).length();
            }
        });
        System.out.println("長度最小的元素："+minObject);//長度最小的元素：tom


        //5. int frequency（Collection，Object）：回傳指定集合中指定元素的出現次數
        System.out.println(""+Collections.frequency(list,"tom"));// 1


        //6. void copy（List dest，List src）：將src中的內容復制到dest中
        //拷貝:注意如果要拷貝的集合大于新的集合，就會拋出例外--Source does not fit in dest
        //因此我們需要先給dest賦值，使元素個數和 list.suze()一樣
        ArrayList dest = new ArrayList();
        for (int i = 0; i < list.size(); i++) {
            dest.add("");
        }
        Collections.copy(dest,list);
        System.out.println("dest:"+dest);//dest:[tom, smith, king, milan]


        //7. boolean replaceAll（List list，Object oldVal，Object oldVal，Object newVal）：使用新值替換List物件的所有舊值
        //例如，如果集合中有tom，就替換成 湯姆
        Collections.replaceAll(list,"tom","湯姆");
        System.out.println("替換后："+list);//替換后：替換后：[湯姆, smith, king, milan]

    }
}

標籤：Java

上一篇：Spring(一)- 初始 + DI+scope

下一篇：redis簡述