JAVA集合框架

一、集合框架概況類圖

List、Set、Map的區(qū)別:

  - List:存儲的元素是有序的，可重復(fù)的。
  - Set:存儲的元素是無序的，不可重復(fù)的。
  - Map:使用鍵值對（key-value）存儲。key是無序、不可重復(fù)的，value是無序、可重復(fù)的。每個鍵最多映射一個值。

二、List集合

1.ArrayList和Vector的區(qū)別:

  - ArrayList是List的主要實現(xiàn)類，底層使用Object[](數(shù)組)存儲，適用于頻繁的查找工作，現(xiàn)成不安全。
  - Vector是List的古老實現(xiàn)類，底層使用Object[](數(shù)組)存儲，線程安全。

2.ArrayList和LinkedList的區(qū)別:

  - (1)是否保證線程安全：兩者都是線程不安全的。
  - (2)底層數(shù)據(jù)結(jié)構(gòu)：ArrayList底層使用的是Object[]數(shù)組的數(shù)據(jù)結(jié)構(gòu);LinkedList底層使用的雙向鏈表的數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表，JDK1.7采用雙向鏈表）。
  - (3)插入和刪除是否受元素位置的影響:
      #ArrayList采用數(shù)組存儲，所以插入和刪除的時間復(fù)雜度受元素位置的影響。在執(zhí)行add(E e)方法的時候，         ArrayList默認(rèn)會將元素插入到數(shù)組的末尾，這種情況的時間復(fù)雜度是O(1)。但如果要指定位置i進行插入元素，時間     復(fù)雜度則是O(n-i)。
      #LinkedList采用鏈表存儲，所以add(E e)插入和刪除的時間復(fù)雜度不受元素位置影響,近似O(1)。而制定位置i進行     插入元素，時間復(fù)雜度近似為O(n)。
   - (4)是否支持快速隨機訪問:ArrayList支持，LinkedList不支持，這都是由底層數(shù)據(jù)結(jié)構(gòu)決定。ArrayList實現(xiàn)了Randomacces的接口，而LinkedList 沒有實現(xiàn)該接口，但這并不是真正決定它是否具有隨機訪問元素的能力，這只是一個標(biāo)識而已。
   - (5)內(nèi)存空間占用:ArrayList的空間占用體現(xiàn)在其初始化的時候就會先分配固定的內(nèi)存空間，大部分情況下都會有剩余的空間沒有被使用；LinedList的空間占用體現(xiàn)在每個Node(元素)的大小，因為每個Node既要存儲相應(yīng)的業(yè)務(wù)數(shù)據(jù)，還要存儲鏈表的前驅(qū)和鏈表的后繼。

3.ArrayList的擴容機制:

三、Set集合

• HashSet:無序，唯一，基于HashMap實現(xiàn)的，底層采用HashMap來保存元素，線程不安全，可以存儲null值.底層基于HashMap實現(xiàn)的，使用對象來計算hashcode值，因為hashcode可能相同，所以還需要equals()方法來判斷對象的相等性。
• LinkedHashSet:LinkedHashSet是HashSet的子類，其內(nèi)部是基于LinkedHashMap來實現(xiàn)的，能夠按照添加的順序遍歷。
• TreeSet:有序，唯一，底層使用紅黑樹實現(xiàn)，能夠按照添加元素的順序進行遍歷

  #HashSet如何檢查重復(fù)
  - 當(dāng)把對象加入到HashSet時，會先計算對象的hashCode值來判斷對象加入的位置，同時也會與其他加入的對象的hashCode值進行比較，如果沒有相同的，則視為沒有重復(fù)。如果有相同的，則會調(diào)用equals()方法檢查兩個對象是否相同，如果相同，則視為重復(fù)，加入失敗。 

四、Map集合

• HashMap:JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（拉鏈法解決沖突）。JDK1.8之后在解決哈希沖突有了變化，當(dāng)鏈表長度大于閾值（默認(rèn)8）時，將會把鏈表轉(zhuǎn)為紅黑樹，以減少搜索時間。將鏈表轉(zhuǎn)為紅黑樹前會進行判斷，如果當(dāng)前數(shù)組的長度小于64，那么會選擇進行數(shù)組擴容，而不是轉(zhuǎn)為紅黑樹。線程不安全。其可以存儲null的key和value。HashMap默認(rèn)的大小為16，每次擴容后，容量會變?yōu)樵瓉淼?倍。如果創(chuàng)建時給定容量的初始值，其會將其擴充為2的冪次方大小(tableSizeFor()方法進行保證)。
• LinkedHashMap:LinkedHashMap繼承自HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)（數(shù)組+鏈表或紅黑樹）組成。另外，LinkedHashMap在上面的基礎(chǔ)上增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序。同時通過對鏈表進行相應(yīng)的操作，實現(xiàn)了訪問順序相關(guān)邏輯。
• Hashtable:數(shù)組+鏈表組成。線程安全的，因為其內(nèi)部的方法基本都經(jīng)過synchronized修飾，性能不高。其不允許null為key或者value,否則會拋出NullPointException。Hashtable默認(rèn)的大小為11，每次擴容后，容量會變?yōu)樵瓉淼?n+1。如果創(chuàng)建時給定容量的初始值，其會直接使用給定的大小。并且其沒有將鏈表轉(zhuǎn)為紅黑樹的機制。
• TreeMap:紅黑樹。實現(xiàn)了NavigableMap和SortedMap接口。這讓其具備對集合中的元素根據(jù)key進行排序的能力。默認(rèn)是按key的升序排序，不過我們也可以指定排序的比較器。
• ConcurrentHashMap:底層數(shù)據(jù)結(jié)構(gòu)jdk1.7以前采用 分段數(shù)組+鏈表，jdk1.8以后使用數(shù)組+鏈表/紅黑二叉樹。在實現(xiàn)線程安全方面，jdk1.7以前使用分段鎖對容器中一部分的數(shù)據(jù)加鎖；jdk1.8以后使用synchronized和CAS來實現(xiàn)，只鎖定當(dāng)前鏈表或紅黑二叉樹的首結(jié)點，只要hash不沖突，就不會產(chǎn)生并發(fā)。

  #HashMap長度為什么是2的冪次方
  - 主要是為了盡可能的減少碰撞，為了減少碰撞，其使用的算法是<（n-1）& hash>,即對hash值用數(shù)組長度取模。

五、Collections工具類

void reverse(List list) ===========> 反轉(zhuǎn)

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) => 旋轉(zhuǎn)。當(dāng)distance為正數(shù)時，將list后distance個元素整體移到前面。當(dāng)為負(fù)數(shù)時，將list前disntance個元素整體移到后面

int binarySearch(List list,Object key) ==>對List進行二分查找，返回索引，注意List必須是有序的

int max(Collection coll) =============> 根據(jù)元素的自然順序，返回最大的元素。類比int min(Collection coll)

int max(Collection coll,Comparator c) ===> 根據(jù)定制排序，返回最大元素

void fill(List list,Object obj) =========> 用指定的元素代替指定list中的所有元素。

int frequency(Collection c,Object o) =====> 統(tǒng)計元素出現(xiàn)次數(shù)

int indexOfSubList(List list,List target) ===>統(tǒng)計target在list中第一次出現(xiàn)的索引，找不到則返回-1

boolean replaceAll(List list,Object oldVaule,Object newValue) ===>用新元素替換舊元素