Sunwc's Blog

JDK 1.8 Collection 框架 - interface List, interface Set 架構

interface Collection：單列集合，用來儲存一個一個的物件

interface List：儲存有序的、可重複的資料 => “動態"陣列，替換原有的陣列
- ArrayList：作為 interface List 的主要實現類；執行緒不安全的，效率高；底層使用Object[] elementData儲存資料
- LinkedList：對於頻繁地插入、刪除操作，使用此類效率比ArrayList高；底層使用雙向鏈結串列儲存資料
- Vector：作為 interface List 的古老實現類；執行緒安全，效率低；底層使用Object[] elementData儲存資料

interface Set：儲存無序的、不可重複的資料

無序性：儲存的資料在底層陣列中並非按照陣列索引的順序新增，而是根據資料的 hash code 決定的
不可重複性

HashSet：作為 interface Set 的主要實現類別；執行緒不安全的；可以儲存null值

HashSet 新增元素的過程：我們向 HashSet 中新增元素a，首先調用元素a的 hashCode()，計算元素a的哈希值，以此哈希值計算出在 HashSet 底層陣列中的存放位置(即為：索引位置)，判斷陣列此索引位置上是否有元素：

若此位置上沒有其他元素，則元素a新增成功 => 情況1
若此位置上有其他元素b(或以鏈結串列形式存在多個元素)，則比較元素a與元素b的哈希值

    若哈希值不相同，則元素a新增成功 => 情況2
    若哈希值相同，進而需要調用元素a所在類別的 equals()

        equals() 回傳true，元素a新增失敗
        equals() 回傳false，元素a新增成功  => 情況3

HashSet 底層結構：陣列 + 鏈結串列

要求向 Set 新增元素時，其元素所在的類別一定要 override hashCode() 與 equals()
要求 override 的 hashCode() 與 equals() 盡可能保持一致性：相同物件元素必須具有相同的散列碼
- LinkedHashSet：作為 HashSet 的子類；遍歷其內部資料時，可以按照新增元素的順序進行遍歷
  - LinkedHashSet 在新增元素時，每個元素還維護了兩個reference，紀錄資料的前一個與後一個元素的位置；對於頻繁的遍歷操作，LinkedHashSet 效率高於 HashSet

TreeSet：可以按照新增元素的指定屬性進行排序

要求向 TreeSet 新增元素時，必須是相同類別的物件
兩種排序方式：自然排序(實現 interface Comparable) 和定制排序(實現 interface Comparator)
自然排序中，比較兩個物件是否想同的標準為：compareTo()回傳0
定制排序中，比較兩個物件是否想同的標準為：compareTo()回傳0
底層結構是紅黑樹

/**
* @author sunwc
* @create 2023-03-28 下午 09:31
*/
public class TreeSetTest {

    /**
    * 自然排序
    */
    @Test
    public void treeSetTest() {

        TreeSet treeSet = new TreeSet();

        treeSet.add(new User("Flask", 33));
        treeSet.add(new User("Ice", 18));
        treeSet.add(new User("Gary", 54));
        treeSet.add(new User("Tim", 26));
        treeSet.add(new User("Daniel", 40));
        treeSet.add(new User("Daniel", 37));

        System.out.println(treeSet.size());

        // 在建立多個User物件、放入TreeSet中後，卻拋出以下例外
        // java.lang.ClassCastException: com.atguigu.java.User cannot be cast to java.lang.Comparable
        // 因為TreeSet的特性會針對指定元素屬性進行比較，而自定義類別要有比較的功能就必須實現 interface Comparable - compareTo()
        // 另外，若比較User的姓名若有重複，就要在compareTo()中定義要如何比較另一個屬性，
        // 否則TreeSet就會認定只要新增的元素去調用compareTo()回傳的值為0時，就代表該元素是重複的而造成新增失敗；反之，就可以新增成功

        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    /**
    * 定制排序
    */
    @Test
    public void treeSetTest2() {

        Comparator comparator = new Comparator<User>() {

            /**
            * 只比較年齡從小到大
            * @param o1
            * @param o2
            * @return
            */
            @Override
            public int compare(User o1, User o2) {
                return Integer.compare(o1.getAge(), o2.getAge());
            }
        };

        TreeSet treeSet = new TreeSet(comparator);

        treeSet.add(new User("Flask", 33));
        treeSet.add(new User("Ice", 18));
        treeSet.add(new User("Gary", 54));
        treeSet.add(new User("Tim", 26));
        treeSet.add(new User("Daniel", 26));
        treeSet.add(new User("Daniel", 37));

        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

class User implements Comparable<User> {

    private String name;
    private int age;

    public User() {
    }

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("User{");
        sb.append("name='").append(name).append('\'');
        sb.append(", age=").append(age);
        sb.append('}');
        return sb.toString();
    }

    /**
    * 排序規則
    * 姓名從大到小排
    * 年齡從小到大排
    * @param o
    * @return
    */
    @Override
    public int compareTo(User o) {

        int compareNameVal = -this.name.compareTo(o.name);
        // 姓名不一樣就直接回傳compareNameVal
        if (compareNameVal != 0) {
            return compareNameVal;
        } else {
            // 姓名一樣就還要再比較年齡
            return Integer.compare(this.age, o.age);
        }
    }
}

TreeSet 自然排序輸出結果：

6
User{name='Tim', age=26}
User{name='Ice', age=18}
User{name='Gary', age=54}
User{name='Flask', age=33}
User{name='Daniel', age=37}
User{name='Daniel', age=40}

TreeSet 定制排序輸出結果：

User{name='Ice', age=18}
User{name='Tim', age=26}
User{name='Flask', age=33}
User{name='Daniel', age=37}
User{name='Gary', age=54}

練習

面試題：ArrayList, LinkedList, Vector 三者有何不同？見上
- 相同點：三個類都是實現了 interface List，儲存資料的特點相同：儲存有序的、可重複的資料

練習一、在list中去除重複的數字值，要求盡量簡單

@Test
public void test3() {

    List list = new ArrayList();
    list.add(new Integer(1));
    list.add(new Integer(2));
    list.add(new Integer(2));
    list.add(new Integer(4));
    list.add(new Integer(4));

    List list1 = removeDuplicate(list);

    for (Object o : list1) {
        System.out.println(o);
    }
}

private List removeDuplicate(List list) {
    Set set = new HashSet();
    set.addAll(list);

    return new ArrayList(set);
}

練習二、有點難度


public class HashSetTest {
    @Test
    public void test4() {

        HashSet set = new HashSet();
        Person2 p1 = new Person2(1001, "AA");
        Person2 p2 = new Person2(1002, "BB");
        
        set.add(p1);
        set.add(p2);
        System.out.println(set);
        
        p1.name = "CC";
        set.remove(p1); // 以1001, CC 換算hashcode找到的索引位置 沒有值
        System.out.println(set);
        set.add(new Person2(1001, "CC")); // 同上，1001, CC 換算hashcode找到的索引位置 沒有值，所以這個元素新增成功
        System.out.println(set);
        set.add(new Person2(1001, "AA")); // 以1001, AA 換算hashcode找到的索引位置 有值 但是 !"CC".equals("AA")，所以這個元素也新增成功
        System.out.println(set); // 最後這個set實際會輸出4個元素
    }
}

class Person2 {
    int id;
    String name;

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

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Person2{");
        sb.append("id=").append(id);
        sb.append(", name='").append(name).append('\'');
        sb.append('}');
        return sb.toString();
    }

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

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

Java - Collection(一)

JDK 1.8 Collection 框架 - interface List, interface Set 架構

練習