集合概述

• 集合、數組都是用來儲存多個數據(在記憶體中)的結構，簡稱Java容器
• 數組在聲明時長度跟數據類型就定死了，還強制是有序的，增刪改查都不變
• Java集合分成兩種體系，有各種接口與實現類:
  • Collection接口:單列數據，用來存一個一個的物件
    • List接口:元素有序、可重複，又稱為"動態數組"
      • ArrayList
      • LinkedList
      • Vector
    • Set接口:元素無序、不可重複
      • HashSet
      • LinkedHashSet
      • TreeSet
  • Map接口:雙列數據，保存具有映射關係(key-value)成對的物件
    • HashMap
      • LinkedHashMap
    • TreeMap
    • Hashtable
      • Properties

Collection

Collection接口本身沒有直接的實現類，而是要通過其子類List與Set各自的實現類來完成物件的實例化

方法

用一個實現Collection接口的實例物件調用，例如:Collection coll = new ArrayList();

• add(Object e):將Object e加入集合中

• size():返回元素個數

• addAll(Collection c):將集合c的內容全加進來

• clear():清空元素，注意不是刪除集合本身，只是清掉其中的元素

• isEmpty():判定是否為空

• contains(Object obj):判斷集合中是否存在obj物件，注意這邊調用的是該類的equals()方法，也就是說預設類型他是比內容；而若自訂的類沒有重寫equals()方法，則會是比地址值(相當於"==")，一般來說在集合用到自訂類我們都要求該類必須重寫equals()方法，不然太搞

• containsAll(Collection c):判斷當前集合是否包含整個集合c，與順序無關，每個元素都有就算

• boolean remove(Object obj):判斷集合中是否存在obj物件，有則移除一個並返回true

• containsAll(Collection c):只要當前集合跟集合c有共通的項目，就全部移除(相當於數學上的差集)，並返回true

• retainAll(Collection c):判斷當前集合與集合c的交集，只保留相同部分(重複的他不會去修改數量)

• equals():判斷兩個集合所有元素是否相等，注意順序有差

• toArray():將集合轉成並返回數組

  • Arrays.asList():Arrays的靜態方法，將數組轉為List，使用時注意可能將數組形參視為"一整個引用類型物件"，前後類別要特別寫清楚，有懷疑就用size方法看看元素個數是否吻合

• iterator():返回Iterator接口的疊代器實例，用於遍歷集合元素

疊代器Iterator

專門用來遍歷Collection集合的接口

• Collection繼承自Iterable接口，表明該類可以用於疊代器

• 當某個類實現Iterable接口時，我們就能稱這個類是一個"可數"的類，也就是可以使用iterator()方法獲取一個疊代器Iterator，然後使用這個Iterator實例去遍歷這個類

• Iterator接口:如果某個類實現了Iterable接口，那麼他也需要創建一個內部類去實現一個Iterator類，讓調用Iterable接口中的iterator()時，能夠獲取到一個iterator實例

• 調用時創建一個疊代器物件，此時疊代器的游標指向在第一元素之前，並且有幾個常用的方法:

  • .next():顯示下一個元素內容，並將指針後移一位

  • .hasNext():判斷是否存在下一個元素內容，返回布林，可以用while配合循環遍歷集合，舉例:

    Iterator iterator = col.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
    // 純遍歷用foreach更快，foreach相較之下的特性是失去了索引
    

  • .remove():只能用在next()之後且一對一，用於刪除剛剛返回的元素；注意跟Collection本身的remove(Object obj)方法不一樣

• 疊代器本身不作為容器，只是看門幫忙數數的，不要搞錯主體

• foreach的代碼底層就是調用了疊代器，舉例:for (Object o : arr){...，他是創建了一個臨時的Object o，每次疊代把arr取出的元素賦給Object o，之後執行下面代碼的操作，可別傻傻的對o進行賦值之類的操作，沒用的

List接口

List特性

特性為有序、可重複，又稱為"動態數組"，此接口有三個實現類分別為:

• ArrayList:主要實現類，線程不安全、效率高，底層使用Object[]結構，他的源碼分析(基於JDK7):
  • 在new一個ArrayList時，底層創建了一個長度10的Object[]數組
    • 在JDK8的話，這邊創造的是長度為空的數組，類似於懶漢式，有真的用到才擴容
  • add時判斷元素個數，若超過了現有則擴容，預設擴為原來的1.5倍，同時整組複製過去新家
  • 啟示:開發中用到ArrayList時，最好選帶參數、指定好預估數量的構造器
• LinkedList:對於頻繁的插入、刪除操作效率高，因為底層是雙向鏈表
  • 雙向鏈表，每一節都包含前後兩個node的指向資訊
• Vector:過時的實現類，線程安全、效率低，底層使用Object[]結構
  • 底層創建了一個長度10的Object[]數組，擴容時為2倍
  • 即使他是線程安全的，實際開發中也不會用他，而是用Collections工具類中的synchronizedList方法，可以說Vector近乎廢棄了

List方法

由於list是有序的，所以有些方法不太一樣(有些重寫有些重載，注意形參)，主要是針對指定位置的操作，例如:

• void add(int index,Object obj):在index處插入元素

• blooean addAll(int index,Collection c):在index處插入集合中的每個元素，注意不要把"整個集合"當成一個元素而誤用add方法

• int indexOf(Object obj):返回指定obj首次出現位置；lastIndexOf:最末

• Object remove(int index):刪除指定位置的元素並返回刪除的元素，使用時注意形參，不要跟Collection的boolean remove(Object obj)搞錯

• Object set(int index,Object obj):用obj取代指定位置的元素並返回被取代的元素

• List sublist(int 含頭,int 不含尾):切出新的sublist

Set接口

Set特性

• 元素無序:所謂無序並不等於隨機，他底層也是數組(其實是HashMap的key部分)，但在儲存時並非依照數組索引一個一個加進去，而是先計算元素的哈希值，以這個哈希值再通過某種算法計算後決定放哪
• 不可重複:保證添加的元素按照equals()判斷時不能返回ture，即相同的元素只能存在一個
• 底層邏輯:當我添加一個元素b，先算b的哈希值，從b的哈希再算出存放位置，此時:
  • 若存放位置為空，則添加b成功
  • 若存放位置已經有元素a存在(或以鏈表形式存在的多個元素)，則比較a跟b的哈希值:
    • 若哈希值不同，則添加b成功(插到鏈表裡)
    • 若哈希值相同，則再比較equals()方法
      • 返回true表示a跟b真的是一樣的東西，添加b失敗
      • 返回false表示他們只是恰好哈希值一樣，添加b成功(插到鏈表裡)
• 所謂的"插到鏈表"，即是說這個位置換成一個鏈表去儲存多個元素，可以想像成"卜"字的樣子:
  • JDK7是頭插法，直觀的一個一個排隊接上去
  • JDK8是尾插法，新來的擠佔分支口，把舊的元素一個一個往外推
• 鏈表長度超過8則會改成紅黑樹，巨難巨複雜，暫時先知道就好
• 當set使用自訂類，必須重寫equals跟hashcode方法，不然拖出去打

Set實現類

Set的實現類底層其實都是用到對應的map

實際開發中比較少用，並且沒有額外定義的方法

• HashSet:主力，線程不安全、可以儲存null

  • LinkedHashSet:子類，遍歷時可以按照"添加的順序"排列
    • 其實就是添加元素時額外記錄了前後索引(想像成一個曲折的的雙向鏈表，類似有一群小朋友每個人都知道自己前後一號是誰，平時散裝著亂跑無所謂，但是要排隊遍歷時能夠找出順序)

• TreeSet:底層為紅黑樹結構，可以按照添加對象的指定屬性進行排序，要求添加的元素必須是同類物件

  • 自然排序:加入的類若實現了Comparable接口，此時比較兩個物件是用重寫的compareTo()方法而非equals()，要注意自己重寫時的比較邏輯，否則可能會產生兩個物件被誤認為重複元素的況狀

  • 訂製排序:用自訂的比較器，此時比較兩個物件是用重寫的compare()方法而非equals()，舉例:

    Comparator com = new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            // 想比較的屬性
        }
    };
    TreeSet set = new TreeSet(com);
    

應用

去除list內的重複項-裝到set裡，舉例:

HashSet set = new HashSet();
set.addAll(list);

Set面試題

public class Person {
    private int id;
    private String name;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    public static void main(String[] args) {
        HashSet set = new HashSet();
        Person p1 = new Person(101, "AA");
        Person p2 = new Person(102, "BB");
        set.add(p1);
        set.add(p2);
        p1.name = "CC"; // 此時放的位置是以原AA算的，但內容被改為CC
        System.out.println(set.remove(p1)); // 返回false，因為p1內容現在是101CC，而原先的位置是101AA，不同位置
        set.add(new Person(101, "CC")); // 能放進去，即使內容一樣，但哈希計算後放的位置不同
        set.add(new Person(101, "AA")); // 能放進去，即使同位置有人，但比equals不一樣
        System.out.println(set);
    }
}

小結

• Collection用到自訂類，必須重寫euqals方法，否則物件是否存在時(例如:contains、remove)會判斷錯誤

• 比較:

• List有序可重複、Set無序不可重複

上次修改於 2021-12-08