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);
        }
    }
}