數組本身也是容器，是一個簡單的線性序列，訪問效率非常高。但是數組本身不夠靈活，一開始就要定義數組的元素。

collection（集合/容器）

set無順序不重復（hashSet），list有順序可以重復（ArrayList，LinkedList）。

map 存放鍵值對。

泛型：貼標簽，建立類型安全的集合，本質就是數據類型的參數化，告訴編譯器在調用的時候必須傳入參數類型。

List中的方法：addAll（Collection B）：把B中所有的元素都加到A里面

removeAll(Collection B)：移除本容器中和B容器中共有的元素。

retainAll（Collection B）：移除A容器中AB容器中非交集的元素。

List：是有序的，可重復的容器。

有序：List中的每個元素都有索引標記。可以根據元素的索引標記（在List中的位置）訪問元素，從而精確控制這些元素。

可重復：List允許加入重復的元素。更確切的講，List通常允許滿足e1.equals（e2）的元素重復加入容器。

List中常用的三種實現類：ArrayList、LinkedList和Vector。

ArrayList的底層實現是數組。

ArrayList中的add方法是一個重載的方法，可以在指定的位置插入一個數據。add(index,E);

remove(index)：刪除指定位置的元素。

set(index,E)將指定位置的數據設置為E，相當于修改替換。

get(index)：獲取索引地址的數據。

indexOf（Object o） 如果查到，返回索引第一次出現的位置，如果沒有查到，返回-1。

lastIndexOf（Object o） 如果查到，返回索引最后一次出現的位置，如果沒有查到，返回-1。

ArrayList

底層是數組的方式實現存儲。特點是：查詢效率高，增刪效率低，線程不安全。我們一般使用它。

數組的長度是有限的，ArrayList是可以存放任意長度，底層自動擴容。定義一個更長的數組，老的復制到新的里面。默認長度是10，可以new ArrayList(size)來定義內部數組的長度。新長度等于老數組長度加老數組的一半

Old = Old+（Old>>1）;

add與remove底層都是數組的拷貝，remove是自己拷貝自己，報后面的所有元素向前移動一個位置。

LinkedList

底層使用雙向鏈表實現存儲，特點是查詢效率低，增刪效率高，線程不安全。

雙向鏈表也叫雙鏈表，是鏈表的一種，沒一個節點包含三部分，上一個節點、下一個節點、數據。

Vector

也是用數組實現的，但是相關方法都加了同步檢查，因此“線程安全，效率低”。

建議：

需要多線程時用Vector

不存在線程安全的時候，查找多的用ArrayList，增刪多的時候用LinkList。

Map

Map用來存儲鍵值對，Map中存儲的鍵值對是通過鍵來標識，所以鍵不能重復。如果重復，新的覆蓋舊的。判斷是否重復用的是Equals方法。

Map接口實現類有HashMap、TreeMap、HashTable、Properties等。

HashMap底層實現采用了哈希表，這是一種非常重要的數據結構。

哈希表的基本結構就是“數組+鏈表”。

數組：占用空間連續，尋址容易，查詢速度快，但是增加刪除的效率非常低。

鏈表：占用空間不連續。尋址困難，查詢速度慢。但是增加和刪除的效率非常高。

主要的存儲結構是 Node（key value next hash）,是一個單項列表。

每個節點Node 由key、value、next、hash四部分組成。

然后把節點放入Node[]數組中，數組中的每個元素都是一個鏈表。

hashMap的存儲過程

1.先計算鍵對象的hashcode()，然后通過hash（）算法計算出應該存儲的位置【將hashcode與數組大小相除取余，余數就是節點存放的數組下標，后來改成了位運算，hashcode&（length-1）也是取余，但是長度必須是2的倍數。后來又進行了兩次散列處理，是結果更加的散列。】

Jdk8中，當鏈表的長度大于8時，鏈表就轉換為紅黑樹，增加了查詢效率。

hashMap的取值過程

先計算鍵對象的hashcode，然后通過hash()算法算得hash值（node中的hash值）定位到存儲的位置，然后通過Equals方法去找對應key進行比較，然后找到value從而找到準確的內容。

java規定：相同的對象的hashcode是相同的

擴容問題：hashMap數組桶的初始值是16，當元素達到數組桶的0.75倍時，將發生擴容，變成原來的2倍。擴容的本質是定義新的更大的數組，并將就數組內容挨個拷貝到新數組中。

JDK8將鏈表在大于8，數組總容量大于64 的情況下把鏈表變為紅黑二叉樹。

除了添加，其他效率都高了。

TreeMap

排序的情況下才使用TreeMap，TreeMap的底層是典型的紅黑二叉樹，每個節點都存儲了本身數據、左節點、右節點、父節點、以及節點顏色。

遍歷時按照key遞增的方式進行排序。

Comparable接口

Comparable接口的方法中有一個compareTo方法 重寫compareTo方法定義比較對象，返回值負數對應的是小于，正數是大于，0是等于。

class Emp  implements Comparable<Emp>  {
    int id;
    String name;
    double salary;
    
    public Emp(int id, String name, double salary) {
        super();
        this.id = id;
        this.name = name;
        this.salary = salary;
    }

    @Override
    public String toString() {
        return  "id:"+id+",name:"+name+",salary:"+salary;
    }
    
    @Override
    public int compareTo(Emp o) {        //負數：小于，0：等于，正數：大于
        
        if(this.salary>o.salary){
            return 1;
        }else if(this.salary<o.salary){
            return -1;
        }else{
            if(this.id>o.id){
                return 1;
            }else if(this.id<o.id){
                return -1;
            }else{
                return 0;
            }
        }
        
    }
    
}

HashMap與HashTable的區別

1、HashMap：線程不安全，效率高。允許key或value為null。

2、HashTable：線程安全，效率低。不允許key或value為null。

set接口

沒有順序，不可重復。只能遍歷查找；不可重復指不允許加入重復的元素（新元素如果和Set中的某個元素通過equals()方法對比為true，則不能加入）。Set中只能放一個null元素，不能放入多個。

Set常見的實現類有：HashSet，TreeSet等，通產使用HashSet。

HashSet

HashSet也是采用的哈希算法實現的，底層實際用的是HashMap實現的（HashSet本質就是一個簡化版的HashMap），因此，查詢效率和增刪效率都比較高。

HashSet就是一個hashMap，存儲的值就是map的鍵，所以不能重復。

TreeSet

TreeSet的底層是TreeMap，也是用map的鍵進行set值的存儲，也是按照元素遞增的方式進行存儲。自定義排序也用實現Comparable接口實現CompareTo方法。

Iterator迭代器

可遍歷List Set Map

以hasNext和Next配合使用。

其中Map需要先用keySet獲取鍵，然后迭代器遍歷鍵的set獲取值。或者使用entrySet直接獲取Set<Entry<K,V>>然后進行遍歷。

Collections工具類

對Set、List、Map進行排序、填充、查找元素的輔助方法。

void sort（List）對List容器內的元素進行排序，排序的規則是按照升序進行排序。自定義的類使用COmparable接口。

void shuffle（List） 隨機排序 打亂順序

void reverse（List）逆序排序 12345 --> 54321 132-->231

void fill（List，Object）用一個特定的對象重寫整個List容器。

int binarySearch（List，Object）對于順序的List容器，采用折半查找（二分法）的方法查找特定的對象。