第 12 章集合

12.1 集合的理解和好處 12.2 集合的框架體系 12.3 Collection 接口和常用方法 12.4 List 接口和常用方法 12.5 ArrayList 底層結構和源碼分析 12.6 Vector 底層結構和源碼剖析 12.7 LinkedList 底層結構 12.8 ArrayList 和 LinkedList 比較 12.9 Set 接口和常用方法 12.10 Set 接口實現類 - HashSet 12.11 Set 接口實現類 - LinkedHashSet

第 12 章集合

12.1 集合的理解和好處

前面我們保存多個數據使用的是數組，那么數組有不足的地方，我們分析一下

12.1.1 數組

長度開始時必須指定，而且一旦指定，不能更改
保存的必須為同一類型的元素
使用數組進行增加/刪除元素的示意代碼 – 比較麻煩

寫出Person數組擴容示意代碼。

Person[] pers = new Person[1]; //大小是1  
pers[0]=new Person();  

//增加新的Person對象?  
Person[] pers2 = new Person[pers.length+1]; //新創建數組  
for(int i = 0; i < pers.length; i++){ //拷貝pers數組的元素到pers2  
    pers2[i] = pers[i];  
}  
pers2[pers2.length-1] = new Person();//添加新的對象

12.1.2 集合

可以動態保存任意多個對象，使用比較方便！
提供了一系列方便的操作對象的方法：add、remove、set、get等
使用集合添加,刪除新元素的示意代碼- 簡潔了

12.2 集合的框架體系

Java 的集合類很多，主要分為兩大類，如圖：

public class Collection_ {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        //解讀
        //1. 集合主要是兩組(單列集合 , 雙列集合)
        //2. Collection 接口有兩個重要的子接口 List Set , 他們的實現子類都是單列集合
        //3. Map 接口的實現子類 是雙列集合，存放的 K-V
        //4. 把老師梳理的兩張圖記住
        //Collection
        //Map
        ArrayList arrayList = new ArrayList();
        arrayList.add("jack");
        arrayList.add("tom");

        HashMap hashMap = new HashMap();
        hashMap.put("NO1", "北京");
        hashMap.put("NO2", "上海");
    }
}

12.3 Collection 接口和常用方法

12.3.1 Collection 接口實現類的特點

public interface Collection<E> extends Iterable<E>

collection實現子類可以存放多個元素，每個元素可以是Object
有些Collection的實現類，可以存放重復的元素，有些不可以
有些Collection的實現類，有些是有序的(List)，有些不是有序(Set)
Collection接口沒有直接的實現子類，是通過它的子接口Set 和 List 來實現的
Collection 接口常用方法,以實現子類 ArrayList 來演示. CollectionMethod.java

public class CollectionMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
//        add:添加單個元素
        list.add("jack");
        list.add(10);//list.add(new Integer(10))
        list.add(true);
        System.out.println("list=" + list);
//        remove:刪除指定元素
        //list.remove(0);//刪除第一個元素
        list.remove(true);//指定刪除某個元素
        System.out.println("list=" + list);
//        contains:查找元素是否存在
        System.out.println(list.contains("jack"));//T
//        size:獲取元素個數
        System.out.println(list.size());//2
//        isEmpty:判斷是否為空
        System.out.println(list.isEmpty());//F
//        clear:清空
        list.clear();
        System.out.println("list=" + list);
//        addAll:添加多個元素
        ArrayList list2 = new ArrayList();
        list2.add("紅樓夢");
        list2.add("三國演義");
        list.addAll(list2);
        System.out.println("list=" + list);
//        containsAll:查找多個元素是否都存在
        System.out.println(list.containsAll(list2));//T
//        removeAll：刪除多個元素
        list.add("聊齋");
        list.removeAll(list2);
        System.out.println("list=" + list);//[聊齋]
//        說明：以ArrayList實現類來演示.

    }
}

12.3.2 Collection 接口遍歷元素方式 1-使用 Iterator(迭代器)

基本介紹

java.util  
接口 Iterator<E>  
所有已知子接口:  
    ListIterator<E>, XMLStreamReader  
所有已知實現類:  
    BeanContextSupport.BCSIterator, EventReaderDelegate, Scanner

Iterator對象稱為迭代器，主要用于遍歷 Collection 集合中的元素。
所有實現了Collection接口的集合類都有一個iterator()方法，用以返回一個實現了Iterator接口的對象，即可以返回一個迭代器。
Iterator 的結構.[看一張圖]
Iterator 僅用于遍歷集合，Iterator 本身并不存放對象。

在調用 iterator.next() 方法之前必須要調用 iterator.hasNext() 進行檢測。若不調用，且下一條記錄無效，直接調用 it.next() 會拋出 NoSuchElementException 異常。迭代器的使用案例
看案例演示 CollectionIterator.java

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

        Collection col = new ArrayList();

        col.add(new Book("三國演義", "羅貫中", 10.1));
        col.add(new Book("小李飛刀", "古龍", 5.1));
        col.add(new Book("紅樓夢", "曹雪芹", 34.6));


        //System.out.println("col=" + col);
        //現在希望能夠遍歷 col集合
        //1. 先得到 col 對應的 迭代器
        Iterator iterator = col.iterator();
        //2. 使用while循環遍歷
//        while (iterator.hasNext()) {//判斷是否還有數據
//            //返回下一個元素，類型是Object
//            Object obj = iterator.next();
//            System.out.println("obj=" + obj);
//        }
        //一個快捷鍵，快速生成 while => itit
        //顯示所有的快捷鍵的的快捷鍵 ctrl + j
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            System.out.println("obj=" + obj);

        }
        //3. 當退出while循環后 , 這時iterator迭代器，指向最后的元素
        //   iterator.next();//NoSuchElementException
        //4. 如果希望再次遍歷，需要重置我們的迭代器
        iterator = col.iterator();
        System.out.println("===第二次遍歷===");
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            System.out.println("obj=" + obj);

        }

    }
}

class Book {
    private String name;
    private String author;
    private double price;

    public Book(String name, String author, double price) {
        this.name = name;
        this.author = author;
        this.price = price;
    }

    public String getName() {
        return name;
    }

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

    public String getAuthor() {
        return author;
    }

    public void setAuthor(String author) {
        this.author = author;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", author='" + author + '\'' +
                ", price=" + price +
                '}';
    }
}

12.3.3 Collection 接口遍歷對象方式 2 - for 循環增強

增強 for 循環，可以代替 iterator 迭代器，特點：增強 for 就是簡化版的 iterator，本質一樣。只能用于遍歷集合或數組。
基本語法

for(元素類型 元素名 : 集合名或數組名) {  
    訪問元素  
}

案例演示
CollectionFor.java

for (Object object : col) {  
    System.out.println(object);  
}

public class CollectionFor {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Collection col = new ArrayList();

        col.add(new Book("三國演義", "羅貫中", 10.1));
        col.add(new Book("小李飛刀", "古龍", 5.1));
        col.add(new Book("紅樓夢", "曹雪芹", 34.6));

        //解讀
        //1. 使用增強for, 在Collection集合
        //2. 增強for， 底層仍然是迭代器
        //3. 增強for可以理解成就是簡化版本的 迭代器遍歷
        //4. 快捷鍵方式 I
//        for (Object book : col) {
//            System.out.println("book=" + book);
//        }
        for (Object o : col) {
            System.out.println("book=" + o);
        }

        //增強for，也可以直接在數組使用
//        int[] nums = {1, 8, 10, 90};
//        for (int i : nums) {
//            System.out.println("i=" + i);
//        }


    }
}

12.4 List 接口和常用方法

12.4.1 List 接口基本介紹

List 接口是 Collection 接口的子接口 List.java

List 集合類中元素有序（即添加順序和取出順序一致）、且可重復 [案例]
List 集合中的每個元素都有其對應的順序索引，即支持索引。 [案例]
List 容器中的元素都對應一個整數型的序號記載其在容器中的位置，可以根據序號存取容器中的元素。

JDK API 中 List 接口的實現類有：

List list = new ArrayList();  
list.add("tom");  
list.add("jack");  
list.add("mary");  
list.add("smith");  
list.add("smith2");  
list.add("kristina");  
System.out.println(list);  
// 3的案例  
System.out.println(list.get(4));//smith2

常用的有：ArrayList、LinkedList 和 Vector。

public class List_ {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        //1. List集合類中元素有序(即添加順序和取出順序一致)、且可重復 [案例]
        List list = new ArrayList();
        list.add("jack");
        list.add("tom");
        list.add("mary");
        list.add("hsp");
        list.add("tom");
        System.out.println("list=" + list);
        //2. List集合中的每個元素都有其對應的順序索引，即支持索引
        //   索引是從0開始的
        System.out.println(list.get(3));//hsp
        //3.
    }
}

12.4.2 List接口的常用方法

public class ListMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("張三豐");
        list.add("賈寶玉");
//        void add(int index, Object ele):在index位置插入ele元素
        //在index = 1的位置插入一個對象
        list.add(1, "拉里");
        System.out.println("list=" + list);
//        boolean addAll(int index, Collection eles):從index位置開始將eles中的所有元素添加進來
        List list2 = new ArrayList();
        list2.add("jack");
        list2.add("tom");
        list.addAll(1, list2);
        System.out.println("list=" + list);
//        Object get(int index):獲取指定index位置的元素
        //說過
//        int indexOf(Object obj):返回obj在集合中首次出現的位置
        System.out.println(list.indexOf("tom"));//2
//        int lastIndexOf(Object obj):返回obj在當前集合中末次出現的位置
        list.add("拉里");
        System.out.println("list=" + list);
        System.out.println(list.lastIndexOf("拉里"));
//        Object remove(int index):移除指定index位置的元素，并返回此元素
        list.remove(0);
        System.out.println("list=" + list);
//        Object set(int index, Object ele):設置指定index位置的元素為ele , 相當于是替換.
        list.set(1, "瑪麗");
        System.out.println("list=" + list);
//        List subList(int fromIndex, int toIndex):返回從fromIndex到toIndex位置的子集合
        // 注意返回的子集合 fromIndex <= subList < toIndex
        List returnlist = list.subList(0, 2);
        System.out.println("returnlist=" + returnlist);
    }
}

12 .4.3 List接口課堂練習

public class ListExercise {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        /*
        添加10個以上的元素(比如String "hello" )，在2號位插入一個元素"教育"，
        獲得第5個元素，刪除第6個元素，修改第7個元素，在使用迭代器遍歷集合，
        要求:使用List的實現類ArrayList完成。
         */
        List list = new ArrayList();
        for (int i = 0; i < 12; i++) {
            list.add("hello" + i);
        }
        System.out.println("list=" + list);

        //在2號位插入一個元素"教育"
        list.add(1, "教育");
        System.out.println("list=" + list);
        //獲得第5個元素
        System.out.println("第五個元素=" + list.get(4));
        //刪除第6個元素
        list.remove(5);
        System.out.println("list=" + list);
        //修改第7個元素
        list.set(6, "三國演義");
        System.out.println("list=" + list);

        //在使用迭代器遍歷集合
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Object obj =  iterator.next();
            System.out.println("obj=" + obj);
        }
    }
}

12.4.4 List的三種遍歷方式[ArrayList,LinkedList,Vector]

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

        //List 接口的實現子類 Vector LinkedList
        //List list = new ArrayList();
        //List list = new Vector();
        List list = new LinkedList();

        list.add("jack");
        list.add("tom");
        list.add("魚香肉絲");
        list.add("北京烤鴨子");

        //遍歷
        //1. 迭代器
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Object obj =  iterator.next();
            System.out.println(obj);

        }

        System.out.println("=====增強for=====");
        //2. 增強for
        for (Object o : list) {
            System.out.println("o=" + o);
        }

        System.out.println("=====普通for====");
        //3. 使用普通for
        for (int i = 0; i < list.size(); i++) {
            System.out.println("對象=" + list.get(i));
        }
    }
}

12.5 ArrayList 底層結構和源碼分析

12.5.1 ArrayList 的注意事項

ArrayListDetail.java

permits all elements, including null，ArrayList 可以加入 null，并且多個
ArrayList 是由數組來實現數據存儲的 [后面老師解讀源碼]
ArrayList 基本等同于 Vector，除了 ArrayList 是線程不安全（執行效率高）看源碼。在多線程情況下，不建議使用 ArrayList

12.5.2 ArrayList 的底層操作機制源碼分析(重點，難點.)

ArrayListSource.java ，先說結論，在分析源碼(示意圖)

ArrayList 中維護了一個 Object 類型的數組 elementData。[debug 看源碼]

transient Object[] elementData; // transient 表示瞬間,短暫的,表示該屬性不會被序列號

當創建 ArrayList 對象時，如果使用的是無參構造器，則初始 elementData 容量為 0，第 1 次添加，則擴容 elementData 為 10，如需要再次擴容，則擴容 elementData 為 1.5 倍。
如果使用的是指定大小的構造器，則初始 elementData 容量為指定大小，如果需要擴容，則直接擴容 elementData 為 1.5 倍。

12.6 Vector 底層結構和源碼剖析

12.6.1 Vector 的基本介紹

Vector 類的定義說明

public class Vector<E>  
    extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, Serializable

Vector 底層也是一個對象數組
```
protected Object[] elementData;  
```

Vector 是線程同步的（即線程安全），Vector 類的操作方法帶有 synchronized

public synchronized E get(int index) {  
    if (index >= elementCount)  
        throw new ArrayIndexOutOfBoundsException(index);  
    return elementData(index);  
}

在開發中，需要線程同步安全時，考慮使用 Vector

public class Vector_ {
    public static void main(String[] args) {
        //無參構造器
        //有參數的構造
        Vector vector = new Vector(8);
        for (int i = 0; i < 10; i++) {
            vector.add(i);
        }
        vector.add(100);
        System.out.println("vector=" + vector);
        //解讀源碼
        //1. new Vector() 底層
        /*
            public Vector() {
                this(10);
            }
         補充：如果是  Vector vector = new Vector(8);
            走的方法:
            public Vector(int initialCapacity) {
                this(initialCapacity, 0);
            }
         2. vector.add(i)
         2.1  //下面這個方法就添加數據到vector集合
            public synchronized boolean add(E e) {
                modCount++;
                ensureCapacityHelper(elementCount + 1);
                elementData[elementCount++] = e;
                return true;
            }
          2.2  //確定是否需要擴容 條件 ： minCapacity - elementData.length>0
            private void ensureCapacityHelper(int minCapacity) {
                // overflow-conscious code
                if (minCapacity - elementData.length > 0)
                    grow(minCapacity);
            }
          2.3 //如果 需要的數組大小 不夠用，就擴容 , 擴容的算法
              //newCapacity = oldCapacity + ((capacityIncrement > 0) ?
              //                             capacityIncrement : oldCapacity);
              //就是擴容兩倍.
            private void grow(int minCapacity) {
                // overflow-conscious code
                int oldCapacity = elementData.length;
                int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                                 capacityIncrement : oldCapacity);
                if (newCapacity - minCapacity < 0)
                    newCapacity = minCapacity;
                if (newCapacity - MAX_ARRAY_SIZE > 0)
                    newCapacity = hugeCapacity(minCapacity);
                elementData = Arrays.copyOf(elementData, newCapacity);
            }
         */

    }
}

12.6.2 Vector 和 ArrayList 的比較

	底層結構	版本	線程安全（同步）效率	擴容倍數
ArrayList	可變數組	jdk1.2	不安全，效率高	如果有參構造1.5倍如果是無參 1.第一次10 2.從第二次開始1.5擴
Vector	可變數組 Object[]	jdk1.0	安全，效率不高	如果是無參，默認10 ，滿后，就按2倍擴容如果指定大小，則每次直接按2倍擴容。

12.7 LinkedList 底層結構

12.7.1 LinkedList 的全面說明

LinkedList 底層實現了雙向鏈表和雙端隊列特點
可以添加任意元素（元素可以重復），包括 null
線程不安全，沒有實現同步

12.7.2 LinkedList 的底層操作機制

public class LinkedList01 {
    public static void main(String[] args) {
        //模擬一個簡單的雙向鏈表

        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node lili = new Node("lili");

        //連接三個結點，形成雙向鏈表
        //jack -> tom -> lili
        jack.next = tom;
        tom.next = lili;
        //lili -> tom -> jack
        lili.pre = tom;
        tom.pre = jack;

        Node first = jack;//讓first引用指向jack,就是雙向鏈表的頭結點
        Node last = lili; //lili,就是雙向鏈表的尾結點


        //演示，從頭到尾進行遍歷
        System.out.println("===從頭到尾進行遍歷===");
        while (true) {
            if(first == null) {
                break;
            }
            //輸出first 信息
            System.out.println(first);
            first = first.next;
        }

        //演示，從尾到頭的遍歷
        System.out.println("====從尾到頭的遍歷====");
        while (true) {
            if(last == null) {
                break;
            }
            //輸出last 信息
            System.out.println(last);
            last = last.pre;
        }

        //演示鏈表的添加對象/數據，是多么的方便
        //要求，是在 tom --------- lili直接，插入一個對象 smith

        //1. 先創建一個 Node 結點，name 就是 smith
        Node smith = new Node("smith");
        //下面就把 smith 加入到雙向鏈表了
        smith.next = lili;
        smith.pre = tom;
        lili.pre = smith;
        tom.next = smith;

        //讓first 再次指向jack
        first = jack;//讓first引用指向jack,就是雙向鏈表的頭結點

        System.out.println("===從頭到尾進行遍歷===");
        while (true) {
            if(first == null) {
                break;
            }
            //輸出first 信息
            System.out.println(first);
            first = first.next;
        }

        last = lili; //讓last 重新指向最后一個結點
        //演示，從尾到頭的遍歷
        System.out.println("====從尾到頭的遍歷====");
        while (true) {
            if(last == null) {
                break;
            }
            //輸出last 信息
            System.out.println(last);
            last = last.pre;
        }


    }
}

//定義一個Node 類，Node 對象 表示雙向鏈表的一個結點
class Node {
    public Object item; //真正存放數據
    public Node next; //指向后一個結點
    public Node pre; //指向前一個結點
    public Node(Object name) {
        this.item = name;
    }
    public String toString() {
        return "Node name=" + item;
    }
}

12.7.3 LinkedList的增刪改查案例

public class LinkedListCRUD {
    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("linkedList=" + linkedList);

        //演示一個刪除結點的
        linkedList.remove(); // 這里默認刪除的是第一個結點
        //linkedList.remove(2);

        System.out.println("linkedList=" + linkedList);

        //修改某個結點對象
        linkedList.set(1, 999);
        System.out.println("linkedList=" + linkedList);

        //得到某個結點對象
        //get(1) 是得到雙向鏈表的第二個對象
        Object o = linkedList.get(1);
        System.out.println(o);//999

        //因為LinkedList 是 實現了List接口, 遍歷方式
        System.out.println("===LinkeList遍歷迭代器====");
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println("next=" + next);

        }

        System.out.println("===LinkeList遍歷增強for====");
        for (Object o1 : linkedList) {
            System.out.println("o1=" + o1);
        }
        System.out.println("===LinkeList遍歷普通for====");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }


        //源碼閱讀.
        /* 1. LinkedList linkedList = new LinkedList();
              public LinkedList() {}
           2. 這時 linkeList 的屬性 first = null  last = null
           3. 執行 添加
               public boolean add(E e) {
                    linkLast(e);
                    return true;
                }
            4.將新的結點，加入到雙向鏈表的最后
             void linkLast(E e) {
                final Node<E> l = last;
                final Node<E> newNode = new Node<>(l, e, null);
                last = newNode;
                if (l == null)
                    first = newNode;
                else
                    l.next = newNode;
                size++;
                modCount++;
            }

         */

        /*
          讀源碼 linkedList.remove(); // 這里默認刪除的是第一個結點
          1. 執行 removeFirst
            public E remove() {
                return removeFirst();
            }
         2. 執行
            public E removeFirst() {
                final Node<E> f = first;
                if (f == null)
                    throw new NoSuchElementException();
                return unlinkFirst(f);
            }
          3. 執行 unlinkFirst, 將 f 指向的雙向鏈表的第一個結點拿掉
            private E unlinkFirst(Node<E> f) {
                // assert f == first && f != null;
                final E element = f.item;
                final Node<E> next = f.next;
                f.item = null;
                f.next = null; // help GC
                first = next;
                if (next == null)
                    last = null;
                else
                    next.prev = null;
                size--;
                modCount++;
                return element;
            }
         */
    }
}

12.8 ArrayList 和 LinkedList 比較

12.8.1 ArrayList 和 LinkedList 的比較

	底層結構	增刪的效率	改查的效率
ArrayList	可變數組	較低數組擴容	較高
LinkedList	雙向鏈表	較高，通過鏈表追加	較低
如何選擇 ArrayList 和 LinkedList：

如果改查操作多，選擇 ArrayList
如果增刪操作多，選擇 LinkedList
一般程序中 80%-90% 是查詢，因此大部分情況選 ArrayList
項目中靈活根據業務選，可能一個模塊用 ArrayList，另一個用 LinkedList

12.9 Set 接口和常用方法

12.9.1 Set 接口基本介紹

無序（添加和取出順序不一致），沒有索引 [后面演示]
不允許重復元素，最多包含一個 null

JDK API 中 Set 接口的實現類有：

java.util  
接口 Set<E>  
類型參數:  
    E - 此 set 所維護元素的類型  
所有超級接口:  
    Collection<E>, Iterable<E>  
所有已知子接口:  
    NavigableSet<E>, SortedSet<E>  
所有已知實現類:  
    AbstractSet, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet,  
    JobStateReasons, LinkedHashSet, TreeSet

12.9.2 Set 接口的常用方法

和 List 接口一樣，Set 接口也是 Collection 的子接口，因此，常用方法和 Collection 接口一樣

12.9.3 Set 接口的遍歷方式

同 Collection 的遍歷方式一樣，因為 Set 接口是 Collection 接口的子接口。

可以使用迭代器
增強 for
不能使用索引的方式來獲取

12.9.4 Set 接口的常用方法舉例

public class SetMethod {
    public static void main(String[] args) {
        //解讀
        //1. 以Set 接口的實現類 HashSet 來講解Set 接口的方法
        //2. set 接口的實現類的對象(Set接口對象), 不能存放重復的元素, 可以添加一個null
        //3. set 接口對象存放數據是無序(即添加的順序和取出的順序不一致)
        //4. 注意：取出的順序的順序雖然不是添加的順序，但是他的固定.
        Set set = new HashSet();
        set.add("john");
        set.add("lucy");
        set.add("john");//重復
        set.add("jack");
        set.add("hsp");
        set.add("mary");
        set.add(null);//
        set.add(null);//再次添加null
        for(int i = 0; i <10;i ++) {
            System.out.println("set=" + set);
        }

        //遍歷
        //方式1： 使用迭代器
        System.out.println("=====使用迭代器====");
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object obj =  iterator.next();
            System.out.println("obj=" + obj);

        }

        set.remove(null);

        //方式2: 增強for
        System.out.println("=====增強for====");

        for (Object o : set) {
            System.out.println("o=" + o);
        }

        //set 接口對象，不能通過索引來獲取


    }
}

12.10 Set 接口實現類 - HashSet

12.10.1 HashSet 的全面說明

HashSet.java

HashSet 實現了 Set 接口

HashSet 實際上是 HashMap，看源碼（圖）

public HashSet() {  
    map = new HashMap<>();  
}

可以存放 null 值，但是只能有一個 null
HashSet 不保證元素是有序的，取決于 hash 后，再確定索引的結果（即，不保證存放元素的順序和取出順序一致）
不能有重復元素/對象，在前面 Set 接口使用已經講過

public class HashSet_ {
    public static void main(String[] args) {
        //解讀
        //1. 構造器走的源碼
        /*
            public HashSet() {
                map = new HashMap<>();
            }
         2. HashSet 可以存放null ,但是只能有一個null,即元素不能重復
         */
        Set hashSet = new HashSet();
        hashSet.add(null);
        hashSet.add(null);
        System.out.println("hashSet=" + hashSet);
    }
}

12.10.2HashSet案例說明

public class HashSet01 {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        //說明
        //1. 在執行add方法后，會返回一個boolean值
        //2. 如果添加成功，返回 true, 否則返回false
        //3. 可以通過 remove 指定刪除哪個對象
        System.out.println(set.add("john"));//T
        System.out.println(set.add("lucy"));//T
        System.out.println(set.add("john"));//F
        System.out.println(set.add("jack"));//T
        System.out.println(set.add("Rose"));//T


        set.remove("john");
        System.out.println("set=" + set);//3個

        //
        set  = new HashSet();
        System.out.println("set=" + set);//0
        //4 Hashset 不能添加相同的元素/數據?
        set.add("lucy");//添加成功
        set.add("lucy");//加入不了
        set.add(new Dog("tom"));//OK
        set.add(new Dog("tom"));//Ok
        System.out.println("set=" + set);

        //在加深一下. 非常經典的面試題.
        //看源碼，做分析， 先給小伙伴留一個坑，以后講完源碼，你就了然
        //去看他的源碼，即 add 到底發生了什么?=> 底層機制.
        set.add(new String("ming"));//ok
        set.add(new String("ming"));//加入不了.
        System.out.println("set=" + set);


    }
}
class Dog { //定義了Dog類
    private String name;

    public Dog(String name) {
        this.name = name;
    }

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

12.10.3 HashSet 底層機制說明

分析HashSet底層是HashMap, HashMap底層是(數組+鏈表+紅黑樹)

public class HashSetSource {
    public static void main(String[] args) {

        HashSet hashSet = new HashSet();
        hashSet.add("java");//到此位置，第1次add分析完畢.
        hashSet.add("php");//到此位置，第2次add分析完畢
        hashSet.add("java");
        System.out.println("set=" + hashSet);

        /*
        對HashSet 的源碼解讀
        1. 執行 HashSet()
            public HashSet() {
                map = new HashMap<>();
            }
        2. 執行 add()
           public boolean add(E e) {//e = "java"
                return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
           }
         3.執行 put() , 該方法會執行 hash(key) 得到key對應的hash值 算法h = key.hashCode()) ^ (h >>> 16)
             public V put(K key, V value) {//key = "java" value = PRESENT 共享
                return putVal(hash(key), key, value, false, true);
            }
         4.執行 putVal
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i; //定義了輔助變量
                //table 就是 HashMap 的一個數組，類型是 Node[]
                //if 語句表示如果當前table 是null, 或者 大小=0
                //就是第一次擴容，到16個空間.
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;

                //(1)根據key，得到hash 去計算該key應該存放到table表的哪個索引位置
                //并把這個位置的對象，賦給 p
                //(2)判斷p 是否為null
                //(2.1) 如果p 為null, 表示還沒有存放元素, 就創建一個Node (key="java",value=PRESENT)
                //(2.2) 就放在該位置 tab[i] = newNode(hash, key, value, null)

                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    //一個開發技巧提示： 在需要局部變量(輔助變量)時候，在創建
                    Node<K,V> e; K k; //
                    //如果當前索引位置對應的鏈表的第一個元素和準備添加的key的hash值一樣
                    //并且滿足 下面兩個條件之一:
                    //(1) 準備加入的key 和 p 指向的Node 結點的 key 是同一個對象
                    //(2)  p 指向的Node 結點的 key 的equals() 和準備加入的key比較后相同
                    //就不能加入
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    //再判斷 p 是不是一顆紅黑樹,
                    //如果是一顆紅黑樹，就調用 putTreeVal , 來進行添加
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {//如果table對應索引位置，已經是一個鏈表, 就使用for循環比較
                          //(1) 依次和該鏈表的每一個元素比較后，都不相同, 則加入到該鏈表的最后
                          //    注意在把元素添加到鏈表后，立即判斷 該鏈表是否已經達到8個結點
                          //    , 就調用 treeifyBin() 對當前這個鏈表進行樹化(轉成紅黑樹)
                          //    注意，在轉成紅黑樹時，要進行判斷, 判斷條件
                          //    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
                          //            resize();
                          //    如果上面條件成立，先table擴容.
                          //    只有上面條件不成立時，才進行轉成紅黑樹
                          //(2) 依次和該鏈表的每一個元素比較過程中，如果有相同情況,就直接break

                        for (int binCount = 0; ; ++binCount) {
                            if ((e = p.next) == null) {
                                p.next = newNode(hash, key, value, null);
                                if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                //size 就是我們每加入一個結點Node(k,v,h,next), size++
                if (++size > threshold)
                    resize();//擴容
                afterNodeInsertion(evict);
                return null;
            }
         */

    }
}

public class HashSetIncrement {
    public static void main(String[] args) {
        /*
        HashSet底層是HashMap, 第一次添加時，table 數組擴容到 16，
        臨界值(threshold)是 16*加載因子(loadFactor)是0.75 = 12
        如果table 數組使用到了臨界值 12,就會擴容到 16 * 2 = 32,
        新的臨界值就是 32*0.75 = 24, 依次類推

         */
        HashSet hashSet = new HashSet();
//        for(int i = 1; i <= 100; i++) {
//            hashSet.add(i);//1,2,3,4,5...100
//        }
        /*
        在Java8中, 如果一條鏈表的元素個數到達 TREEIFY_THRESHOLD(默認是 8 )，
        并且table的大小 >= MIN_TREEIFY_CAPACITY(默認64),就會進行樹化(紅黑樹),
        否則仍然采用數組擴容機制

         */

//        for(int i = 1; i <= 12; i++) {
//            hashSet.add(new A(i));//
//        }


        /*
            當我們向hashset增加一個元素，-> Node -> 加入table , 就算是增加了一個size++

         */

        for(int i = 1; i <= 7; i++) {//在table的某一條鏈表上添加了 7個A對象
            hashSet.add(new A(i));//
        }

        for(int i = 1; i <= 7; i++) {//在table的另外一條鏈表上添加了 7個B對象
            hashSet.add(new B(i));//
        }



    }
}

class B {
    private int n;

    public B(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 200;
    }
}

class A {
    private int n;

    public A(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 100;
    }
}

12.10.4 HashSet 課堂練習 1

HashSetExercise.java 5min

定義一個 Employee 類，該類包含：private 成員屬性 name, age 要求:

創建 3 個 Employee 對象放入 HashSet 中
當 name 和 age 的值相同時，認為是相同員工，不能添加到 HashSet 集合中

實現說明

equals()：若 name 和 age 值相同，返回 true（判定為相同對象）
hashCode()：若 name 和 age 值相同，返回相同哈希碼（保證相同對象進同一哈希桶，配合 equals 去重）

操作示意：
在 IDE 中生成 equals() 和 hashCode() 時，勾選 name、age 字段，讓這兩個屬性共同決定對象是否“相同”。

public class HashSetExercise {
    public static void main(String[] args) {


        /**
         定義一個Employee類，該類包含：private成員屬性name,age 要求:
         創建3個Employee 對象放入 HashSet中
         當 name和age的值相同時，認為是相同員工, 不能添加到HashSet集合中

         */
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("milan", 18));//ok
        hashSet.add(new Employee("smith", 28));//ok
        hashSet.add(new Employee("milan", 18));//加入不成功.

        //回答,加入了幾個? 3個
        System.out.println("hashSet=" + hashSet);
    }
}

//創建Employee
class Employee {
    private String name;
    private int age;

    public Employee(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;
    }

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

    public void setAge(int age) {
        this.age = age;
    }
    //如果name 和 age 值相同，則返回相同的hash值

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

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

12.11 Set 接口實現類 - LinkedHashSet

12.11.1 LinkedHashSet 的全面說明

LinkedHashSet 是 HashSet 的子類
LinkedHashSet 底層是一個 LinkedHashMap，底層維護了一個數組 + 雙向鏈表
LinkedHashSet 根據元素的 hashCode 值來決定元素的存儲位置，同時使用鏈表維護元素的次序（圖），這使得元素看起來是以插入順序保存的。
LinkedHashSet 不允許添加重復元素

public class LinkedHashSetSource {
    public static void main(String[] args) {
        //分析一下LinkedHashSet的底層機制
        Set set = new LinkedHashSet();
        set.add(new String("AA"));
        set.add(456);
        set.add(456);
        set.add(new Customer("劉", 1001));
        set.add(123);
        set.add("HSP");

        System.out.println("set=" + set);
        //解讀
        //1. LinkedHashSet 加入順序和取出元素/數據的順序一致
        //2. LinkedHashSet 底層維護的是一個LinkedHashMap(是HashMap的子類)
        //3. LinkedHashSet 底層結構 (數組table+雙向鏈表)
        //4. 添加第一次時，直接將 數組table 擴容到 16 ,存放的結點類型是 LinkedHashMap$Entry
        //5. 數組是 HashMap$Node[] 存放的元素/數據是 LinkedHashMap$Entry類型
        /*
                //繼承關系是在內部類完成.
                static class Entry<K,V> extends HashMap.Node<K,V> {
                    Entry<K,V> before, after;
                    Entry(int hash, K key, V value, Node<K,V> next) {
                        super(hash, key, value, next);
                    }
                }

         */

    }
}
class Customer {
    private String name;
    private int no;

    public Customer(String name, int no) {
        this.name = name;
        this.no = no;
    }
}

12.11.2LinkedHashSet課后練習題LinkedHashSetExercise.java

public class LinkedHashSetExercise {
    public static void main(String[] args) {

        LinkedHashSet linkedHashSet = new LinkedHashSet();
        linkedHashSet.add(new Car("奧拓", 1000));//OK
        linkedHashSet.add(new Car("奧迪", 300000));//OK
        linkedHashSet.add(new Car("法拉利", 10000000));//OK
        linkedHashSet.add(new Car("奧迪", 300000));//加入不了
        linkedHashSet.add(new Car("保時捷", 70000000));//OK
        linkedHashSet.add(new Car("奧迪", 300000));//加入不了

        System.out.println("linkedHashSet=" + linkedHashSet);

    }
}

/**
 * Car 類(屬性:name,price)，  如果 name 和 price 一樣，
 * 則認為是相同元素，就不能添加。 5min
 */

class Car {
    private String name;
    private double price;

    public Car(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

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

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

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

    //重寫equals 方法 和 hashCode
    //當 name 和 price 相同時， 就返回相同的 hashCode 值, equals返回t

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Car car = (Car) o;
        return Double.compare(car.price, price) == 0 &&
                Objects.equals(name, car.name);
    }

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

posted @ 2025-08-21 20:12 *珍惜當下* 閱讀(16) 評論(0) 收藏舉報

刷新頁面返回頂部

ming-Infinite-progress

第 12 章 集合

第 12 章 集合

12.1 集合的理解和好處

12.1.1 數組

12.1.2 集合

12.2 集合的框架體系

12.3 Collection 接口和常用方法

12.3.1 Collection 接口實現類的特點

12.3.2 Collection 接口遍歷元素方式 1-使用 Iterator(迭代器)

12.3.3 Collection 接口遍歷對象方式 2 - for 循環增強

12.4 List 接口和常用方法

12.4.1 List 接口基本介紹

12.4.2 List接口的常用方法

12 .4.3 List接口課堂練習

12.4.4 List的三種遍歷方式[ArrayList,LinkedList,Vector]

12.5 ArrayList 底層結構和源碼分析

12.5.1 ArrayList 的注意事項

12.5.2 ArrayList 的底層操作機制源碼分析(重點，難點.)

12.6 Vector 底層結構和源碼剖析

12.6.1 Vector 的基本介紹

12.6.2 Vector 和 ArrayList 的比較

12.7 LinkedList 底層結構

12.7.1 LinkedList 的全面說明

12.7.2 LinkedList 的底層操作機制

12.7.3 LinkedList的增刪改查案例

12.8 ArrayList 和 LinkedList 比較

12.8.1 ArrayList 和 LinkedList 的比較

12.9 Set 接口和常用方法

12.9.1 Set 接口基本介紹

12.9.2 Set 接口的常用方法

12.9.3 Set 接口的遍歷方式

12.9.4 Set 接口的常用方法舉例

12.10 Set 接口實現類 - HashSet

12.10.1 HashSet 的全面說明

12.10.2HashSet案例說明

12.10.3 HashSet 底層機制說明

12.10.4 HashSet 課堂練習 1

實現說明

12.11 Set 接口實現類 - LinkedHashSet

12.11.1 LinkedHashSet 的全面說明

12.11.2LinkedHashSet課后練習題LinkedHashSetExercise.java

公告

第 12 章集合

第 12 章集合