Collection集合體系

1，Collection集合分為兩大類List集合和Set集合

List系列集合特點: 有序，可重複，有索引

　　ArrayList：有序，可重複，有索引。

　　LinkedList：有序，可重複，有索引。

（1）List集合

　　List集合因為支援索引，所以多了很多與索引相關的方法，當然，Collection的功能List也都繼承了

List集合的基本操作：

package com.itheima.yaoyao;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;

public class ListDemo1 {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("張小花");
        arrayList.add("牛愛花");
        arrayList.add("李大花");

        //list的remove方法·根據索引下標來刪除元素
        arrayList.remove(0);
        System.out.println("===============");

        //set方法修改(同樣根據索引下標)；
        arrayList.set(0,"王小花");
        System.out.println("===============");
        //get方法獲取指定索引下標元素
        arrayList.get(0);
        System.out.println("===============");

        //遍歷List集合中的元素

        //1,for迴圈遍歷
        for (int i = 0; i < arrayList.size(); i++) {
            String s = arrayList.get(i);
            System.out.println(s);
        }

        System.out.println("===============");
        //2，增強for
        for (String s : arrayList) {
            System.out.println(s);
        }


        System.out.println("===============");
        //3,迭代器
        Iterator<String> iterator = arrayList.iterator();
        while (iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }
        System.out.println("===============");
        //4,迭代器【List列表版list特有】
        ListIterator<String> stringListIterator = arrayList.listIterator();
        while (stringListIterator.hasNext()){
            String next = stringListIterator.next();
            System.out.println(next);
        }
        //5，lambda(forEach)表示式迴圈
        arrayList.forEach(System.out::println);

    }
}

1，ArrayList集合的底層原理

基於陣列實現的

（1）ArrayList的特點

　　查詢速度快（注意：是根據索引查詢資料快）:查詢資料通過地址值和索引定位，查詢任意資料耗時相同。

　　刪除效率低：可能需要把後面很多的資料進行前移。

　　新增效率極低：可能需要把後面很多的資料後移，再新增元素；或者也可能需要進行陣列的擴容。

（2）底層原理

　　①利用無參構造器建立的集合，會在底層建立一個預設長度為0的陣列

　　②新增第一個元素時，底層會建立一個新的長度為10的陣列

　　③存滿時，會擴容1.5倍

　　④如果一次新增多個元素，1.5倍還放不下，則新建立陣列的長度以實際為準

（3）適用場景

ArrayList適合：根據索引查詢資料，比如根據隨機索引取資料（高效）！或者資料量不是很大時！
ArrayList不適合：資料量大的同時又要頻繁的經行增刪操作

2，LinkedList集合的底層原理

基於雙連結串列實現的

（1）LinkedList新增了很多首位元運算的特有方法

（2）適用場景

　　LinkedList集合適合需要頻繁操作首尾元素的場景，比如棧和佇列

（2）Set集合

　　set系列的集合特點：不重複，無索引；

HashSet：無序，不重複，無索引。
LinkedHashSet：有序，不重複，無索引。
TreeSet：可排序，不重複，無索引。

1，HashSet集合

注意：在正式瞭解HashSet集合的底層原理前，我們需要先搞清楚一個前置知識：雜湊值！

就是一個int型別的數值，Java中每個物件都有一個雜湊值。
Java中的所有物件，都可以呼叫Obejct類提供的hashCode方法，返回該物件自己的雜湊值。

物件雜湊值的特點

同一個物件多次呼叫hashCode()方法返回的雜湊值是相同的。
不同的物件，它們的雜湊值一般不相同，但也有可能會相同(雜湊碰撞)。

HashSet集合的底層原理

基於雜湊表實現。
雜湊表是一種增刪改查資料，效能都較好的資料結構

雜湊表

lJDK8之前，雜湊表 = 陣列+連結串列
lJDK8開始，雜湊表 = *陣列+連結串列+紅黑樹

雜湊表擴容問題

JDK8開始，當連結串列長度超過8，且陣列長度>=64時，自動將連結串列轉成紅黑樹

紅黑樹

HashSet集合去重

HashSet集合預設不能對內容一樣的兩個不同物件去重複

如果希望Set集合認為2個內容相同的物件是重複的應該怎麼辦？

重寫物件的**hashCode和equals方法。**

2，LinkedHashSet集合

LinkedHashSet集合的特點和原理是怎麼樣的？

有序，不重複，無索引。
底層基於雜湊表，使用雙連結串列記錄新增資料。

3，TreeSet集合

TreeSet集合的特點：

可排序，不重複，無索引
底層基於紅黑樹實現排序，增刪改查效能較好

TreeSet集合對自定義的物件的排序：

類實現Comparable介面，重寫比較規則。
集合構造器中定義Comparator比較器物件，重寫比較規則

任務

請為TreeSet提供一個比較器，使得TreeSet的元素能夠按照如下規則進行排序。

優先按照物件的年齡age進行排序（由小到大）。
如果年齡相同，則按照物件的分數score進行排序（由大到小）。

建立一個Student物件類

Set<Student> students = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student t0, Student t1) {
       int result = t0.getAge() - t1.getAge();
       int result1 =  ((int) (t1.getScore() - t0.getScore()));
        if (result == 0 ) {
            if (result1 == 0) {
                result1 = t0.equals(t1)?0:1;
            }
            return result1;
        }
        return result;
    }
});

students.add(new Student("張三", 18, 80));
students.add(new Student("李四", 20, 90));
students.add(new Student("王五", 20, 100));
students.add(new Student("王五", 20, 100));
students.add(new Student("趙六", 22, 70));
students.add(new Student("孫七", 22, 60));

students.forEach(System.out::println);

集合條目的刪除

邊迴圈邊刪除集合中的元素，會導致迴圈出錯ConcurrentModificationException。我們可以通過迭代器或是倒序迴圈的方式來解決這個問題。

任務

請在removeByIterator使用迭代器方式刪除集合中包含key的元素。
請在removeByReverseFor使用倒序for迴圈刪除集合中包含key的元素

public static void main(String[] args) {

    List<String> names = new ArrayList<>();
    
    names.add("張順");
    names.add("公孫勝");
    names.add("張清");
    names.add("張橫");
    names.add("阮小二");
    names.add("阮小七");
    names.add("盧俊義");
    names.add("阮小五");
    names.add("宋江");
    names.add("宋萬");
    
    removeByIterator(names, "張");
    System.out.println(names);
    
    removeByReverseFor(names, "阮");
    System.out.println(names);
    
    // Collection還提供了removeIf方法，可以使用Lambda表示式來刪除元素
    // 內部使用了Iterator實現
    names.removeIf(name -> name.contains("宋"));
    System.out.println(names);
}

// 通過迭代器刪除集合中包含key的元素
public static void removeByIterator(List<String> names, String key) {
    Iterator <String>iterator = names.iterator();
    while (iterator.hasNext()){
        if (iterator.next().contains(key)){
            iterator.remove();
        }

}


}

// 通過倒序for迴圈刪除集合中包含key的元素
public static void removeByReverseFor(List<String> names, String key) {
    for (int i = names.size() - 1; i >= 0; i--) {
        if (names.contains(key)) {
            names.remove(i);
        }
    }
}