JAVA集合框架
一、集合框架概況類圖
List、Set、Map的區別:
- List:存儲的元素是有序的，可重復的。
- Set:存儲的元素是無序的，不可重復的。
- Map:使用鍵值對（key-value）存儲。key是無序、不可重復的，value是無序、可重復的。每個鍵最多映射一個值。
二、List集合
1.ArrayList和Vector的區別:
- ArrayList是List的主要實現類，底層使用Object[](數組)存儲，適用于頻繁的查找工作，現成不安全。
- Vector是List的古老實現類，底層使用Object[](數組)存儲，線程安全。
2.ArrayList和LinkedList的區別:
- (1)是否保證線程安全：兩者都是線程不安全的。
- (2)底層數據結構：ArrayList底層使用的是Object[]數組的數據結構;LinkedList底層使用的雙向鏈表的數據結構（JDK1.6之前為循環鏈表，JDK1.7采用雙向鏈表）。
- (3)插入和刪除是否受元素位置的影響:
#ArrayList采用數組存儲，所以插入和刪除的時間復雜度受元素位置的影響。在執行add(E e)方法的時候， ArrayList默認會將元素插入到數組的末尾，這種情況的時間復雜度是O(1)。但如果要指定位置i進行插入元素，時間 復雜度則是O(n-i)。
#LinkedList采用鏈表存儲，所以add(E e)插入和刪除的時間復雜度不受元素位置影響,近似O(1)。而制定位置i進行 插入元素，時間復雜度近似為O(n)。
- (4)是否支持快速隨機訪問:ArrayList支持，LinkedList不支持，這都是由底層數據結構決定。ArrayList實現了Randomacces的接口，而LinkedList 沒有實現該接口，但這并不是真正決定它是否具有隨機訪問元素的能力，這只是一個標識而已。
- (5)內存空間占用:ArrayList的空間占用體現在其初始化的時候就會先分配固定的內存空間，大部分情況下都會有剩余的空間沒有被使用；LinedList的空間占用體現在每個Node(元素)的大小，因為每個Node既要存儲相應的業務數據，還要存儲鏈表的前驅和鏈表的后繼。
3.ArrayList的擴容機制:
三、Set集合
- HashSet:無序，唯一，基于HashMap實現的，底層采用HashMap來保存元素，線程不安全，可以存儲null值.底層基于HashMap實現的，使用對象來計算hashcode值，因為hashcode可能相同，所以還需要equals()方法來判斷對象的相等性。
- LinkedHashSet:LinkedHashSet是HashSet的子類，其內部是基于LinkedHashMap來實現的，能夠按照添加的順序遍歷。
- TreeSet:有序，唯一，底層使用紅黑樹實現，能夠按照添加元素的順序進行遍歷
#HashSet如何檢查重復
- 當把對象加入到HashSet時，會先計算對象的hashCode值來判斷對象加入的位置，同時也會與其他加入的對象的hashCode值進行比較，如果沒有相同的，則視為沒有重復。如果有相同的，則會調用equals()方法檢查兩個對象是否相同，如果相同，則視為重復，加入失敗。
四、Map集合
- HashMap:JDK1.8之前HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（拉鏈法解決沖突）。JDK1.8之后在解決哈希沖突有了變化，當鏈表長度大于閾值（默認8）時，將會把鏈表轉為紅黑樹，以減少搜索時間。將鏈表轉為紅黑樹前會進行判斷，如果當前數組的長度小于64，那么會選擇進行數組擴容，而不是轉為紅黑樹。線程不安全。其可以存儲null的key和value。HashMap默認的大小為16，每次擴容后，容量會變為原來的2倍。如果創建時給定容量的初始值，其會將其擴充為2的冪次方大小(tableSizeFor()方法進行保證)。
- LinkedHashMap:LinkedHashMap繼承自HashMap，所以它的底層仍然是基于拉鏈式散列結構（數組+鏈表或紅黑樹）組成。另外，LinkedHashMap在上面的基礎上增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。
- Hashtable:數組+鏈表組成。線程安全的，因為其內部的方法基本都經過synchronized修飾，性能不高。其不允許null為key或者value,否則會拋出NullPointException。Hashtable默認的大小為11，每次擴容后，容量會變為原來的2n+1。如果創建時給定容量的初始值，其會直接使用給定的大小。并且其沒有將鏈表轉為紅黑樹的機制。
- TreeMap:紅黑樹。實現了NavigableMap和SortedMap接口。這讓其具備對集合中的元素根據key進行排序的能力。默認是按key的升序排序，不過我們也可以指定排序的比較器。
- ConcurrentHashMap:底層數據結構jdk1.7以前采用 分段數組+鏈表，jdk1.8以后使用數組+鏈表/紅黑二叉樹。在實現線程安全方面，jdk1.7以前使用分段鎖對容器中一部分的數據加鎖；jdk1.8以后使用synchronized和CAS來實現，只鎖定當前鏈表或紅黑二叉樹的首結點，只要hash不沖突，就不會產生并發。
#HashMap長度為什么是2的冪次方
- 主要是為了盡可能的減少碰撞，為了減少碰撞，其使用的算法是<（n-1）& hash>,即對hash值用數組長度取模。
五、Collections工具類
void reverse(List list) ===========> 反轉
void shuffle(List list) ============> 隨機排序
void sort(List list) ===============> 按自然排序的升序排序
void sort(List list,Comparator c) ==> 定制排序，由Comparator控制排序邏輯
void swap(List list,int i,int j) ===> 交換兩個索引位置的元素
void rotate(List list,int distance) => 旋轉。當distance為正數時，將list后distance個元素整體移到前面。當為負數時，將list前disntance個元素整體移到后面
int binarySearch(List list,Object key) ==>對List進行二分查找，返回索引，注意List必須是有序的
int max(Collection coll) =============> 根據元素的自然順序，返回最大的元素。類比int min(Collection coll)
int max(Collection coll,Comparator c) ===> 根據定制排序，返回最大元素
void fill(List list,Object obj) =========> 用指定的元素代替指定list中的所有元素。
int frequency(Collection c,Object o) =====> 統計元素出現次數
int indexOfSubList(List list,List target) ===>統計target在list中第一次出現的索引，找不到則返回-1
boolean replaceAll(List list,Object oldVaule,Object newValue) ===>用新元素替換舊元素
