HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList的底層實作

HashSet與HashMap差別

HashMap實作了Map接口 

HashSet實作了Set接口

HashMap儲存鍵值對 

HashSet僅僅存儲對象

HashMap使用put()方法将元素放入map中 

HashSet使用add()方法将元素放入set中

HashMap中使用鍵對象來計算hashcode值 

HashSet使用成員對象來計算hashcode值

HashMap比較快，因為是使用唯一的鍵來擷取對象 

HashSet較HashMap來說比較慢

HashTable與HashMap的差別

Hashtable方法是同步的 

HashMap方法是非同步的

Hashtable基于Dictionary類 

HashMap基于AbstractMap，而AbstractMap基于Map接口的實作

Hashtable中key和value都不允許為null，遇到null，直接傳回 NullPointerException 

HashMap中key和value都允許為null，遇到key為null的時候，調用putForNullKey方法進行處理，而對value沒有處理

Hashtable中hash數組預設大小是11，擴充方式是old*2+1 

HashMap中hash數組的預設大小是16，而且一定是2的指數

什麼是ArrayList

ArrayList可以了解為動态數組，它的容量能動态增長，該容量是指用來存儲清單元素的數組的大小，随着向ArrayList中不斷添加元素，其容量也自動增長 

ArrayList允許包括null在内的所有元素 

ArrayList是List接口的非同步實作 

ArrayList是有序的

定義如下：

ArrayList實作了List接口、底層使用數組儲存所有元素，其操作基 本上是對數組的操作

ArrayList繼承了AbstractList抽象類，它是一個數組隊列，提供了相關的添加、删除、修改、周遊等功能

ArrayList實作了RandmoAccess接口，即提供了随機通路功能，RandmoAccess是java中用來被List實作，為List提供快速通路功能的，我們可以通過元素的序号快速擷取元素對象，這就是快速随機通路

ArrayList實作了Cloneable接口，即覆寫了函數clone()，能被克隆 

ArrayList實作了java.io.Serializable接口，意味着ArrayList支援序列化

什麼是LinkedList

LinkedList基于連結清單的List接口的非同步實作 

LinkedList允許包括null在内的所有元素 

LinkedList是有序的 

LinkedList是fail-fast的

LinkedList與ArrayList的差別

LinkedList底層是雙向連結清單 

ArrayList底層是可變數組

LinkedList不允許随機通路，即查詢效率低 

ArrayList允許随機通路，即查詢效率高

LinkedList插入和删除效率快 

ArrayList插入和删除效率低

解釋一下：

對于随機通路的兩個方法，get和set，ArrayList優于LinkedList，因為LinkedList要移動指針 

對于新增和删除兩個方法，add和remove，LinedList比較占優勢，因為ArrayList要移動資料

什麼是ConcurrentHashMap

ConcurrentHashMap基于雙數組和連結清單的Map接口的同步實作 

ConcurrentHashMap中元素的key是唯一的、value值可重複 

ConcurrentHashMap不允許使用null值和null鍵 

ConcurrentHashMap是無序的

為什麼使用ConcurrentHashMap

我們都知道HashMap是非線程安全的，當我們隻有一個線程在使用HashMap的時候，自然不會有問題，但如果涉及到多個線程，并且有讀有寫的過程中，HashMap就會fail-fast。要解決HashMap同步的問題，我們的解決方案有

Hashtable 

Collections.synchronizedMap(hashMap) 

這兩種方式基本都是對整個hash表結構加上同步鎖，這樣在鎖表的期間，别的線程就需要等待了，無疑性能不高，是以我們引入ConcurrentHashMap，既能同步又能多線程通路

ConcurrentHashMap的資料結構

ConcurrentHashMap的資料結構為一個Segment數組，Segment的資料結構為HashEntry的數組，而HashEntry存的是我們的鍵值對，可以構成連結清單。可以簡單的了解為數組裡裝的是HashMap

從上面的結構我們可以了解到，ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的連結清單的頭部，是以，這一種結構的帶來的副作用是Hash的過程要比普通的HashMap要長，但是帶來的好處是寫操作的時候可以隻對元素所在的Segment進行加鎖即可，不會影響到其他的Segment。正是因為其内部的結構以及機制，ConcurrentHashMap在并發通路的性能上要比Hashtable和同步包裝之後的HashMap的性能提高很多。在理想狀态下，ConcurrentHashMap 可以支援 16 個線程執行并發寫操作（如果并發級别設定為 16），及任意數量線程的讀操作