摘要：允許從任一方向來遍歷對象，并在遍歷迭代過程中進行修改該對象，還能獲得迭代器的當(dāng)前位置。這個構(gòu)造函數(shù)是將返回了一個對象給，這也是的存儲實現(xiàn)原理。
一、容器產(chǎn)生的原因
1.數(shù)組的缺點：大小一旦給定就無法更改，除非復(fù)制到一個新的數(shù)組中，開銷大；而容器類都可以自動地調(diào)整自己的尺寸。
2.容器功能的多樣性：容器可以實現(xiàn)各種不同要求，如按不同依據(jù)將元素進行排序或者保證容器內(nèi)無重復(fù)元素等等。
關(guān)于容器的泛型參數(shù)：
當(dāng)指定了某個類型作為類型參數(shù)時，則可以將該類型及其子類型的對象放入到容器當(dāng)中，泛型保證了安全性。
二、Collection接口
Collection保存單一的元素，并且Collection繼承了Iterable接口，而Map中保存鍵值對。
1.Collection接口中的方法
Collection中提供了判空、大小、遍歷、是否包含某元素、是否包含其他Collection全部、添加某元素、添加其他Collecton全部、刪除某元素、刪除其他Collection全部(求差)、刪除全部元素*以及、只保留與其他Collection重合部分(求交)、以及toArray方法(所有Collection實現(xiàn)類都能轉(zhuǎn)換成數(shù)組并且如迭代器有是順序那么數(shù)組中也是相同順序的)。
2.Collection實現(xiàn)類中的構(gòu)造函數(shù)
Collection一個重要的作用就是作為它的具體實現(xiàn)集合之間相互轉(zhuǎn)換的中介，比較常用的Collection類如ArrayList、LinkedList、HashSet、LinkedHashSet、TreeSet中除了都有無參構(gòu)造函數(shù)外還全部都有一個接受Collection作為參數(shù)的構(gòu)造函數(shù)(LinkedList有且僅有這兩個)。
其中ArrayList(10)、HashSet(16,0.75)、LinkedHashSet(16,0.75)都有一個在創(chuàng)建時指定容量的構(gòu)造函數(shù),對于ArrayList而言是因為其底層是基于數(shù)組實現(xiàn)的。
其中HashSet和LinkedHashSet(LinkedHashSet繼承自HashSet)還多了一個可以同時指定容量和負載因子的構(gòu)造函數(shù),如不指定則默認是0.75。這是因為HashSet內(nèi)部是以一個HashMap對象實現(xiàn)的(構(gòu)造函數(shù)中創(chuàng)建賦給Map類型的成員變量map)、LinkedHashSet中是以一個LinkedHashMap對象實現(xiàn)的(構(gòu)造函數(shù)中調(diào)用父類的一個默認訪問權(quán)限級別的構(gòu)造函數(shù)來創(chuàng)建然后同樣賦給map)，因為HashMap和LinkedHashMap都是用數(shù)組+(雙向節(jié)點)鏈表來實現(xiàn)的，所以就有了容量和負載因子這兩個參數(shù)，也相應(yīng)地有了這兩個構(gòu)造函數(shù)。
其中TreeSet則有一個接受SortedSet作為參數(shù)的構(gòu)造函數(shù)和一個接受比較器Comparator作為參數(shù)的構(gòu)造函數(shù)。前者除了轉(zhuǎn)換集合類型外還有個作用是可以按照原本SortedSet里的比較器來進行排序(如果存在)，也就是說轉(zhuǎn)換后新舊SortedSet里面的元素順序是相同的。
3.遍歷Collection實現(xiàn)類中三種方法
使用聚合操作(Aggregate Operations)//待補充...話說思否不能設(shè)置字體顏色的么
使用foreach來進行遍歷
使用Iterator()方法或者spliterator()方法所返回的順序迭代器和并行迭代器。當(dāng)我們需要在遍歷過程中刪除元素或者需要并行遍歷Collection時都必須使用Iterator。
三、List接口及其實現(xiàn)類
Collection中的List有三個特點：1.可以允許重復(fù)的對象。2.可以插入多個null元素。3.是一個有序容器，保持了每個元素的插入順序，輸出的順序就是插入的順序。List重新規(guī)定了equals和hashCode方法的實現(xiàn)，這使得equals可以用來不同類型之間的List實現(xiàn)類對象之間來比較所包含元素是否完全相同,這個相同是按順序相同的，即54321與12345是不相同的。
常用的實現(xiàn)類有ArrayList和LinkedList，當(dāng)需要大量的隨機訪問則使用ArrayList，當(dāng)需要經(jīng)常從表前半部分插入和刪除元素則應(yīng)該根據(jù)靠前程度使用LinkedList(因為對于ArrayList而言插入或者刪除元素的位置越靠前，需要復(fù)制元素的次數(shù)就越接近size(添加是size-i刪除是size-i-1)；對于LinkedList而言，它是根據(jù)位置位于前半部分還是后半部分來選則是從前往后遍歷找還是從后往前找，對它而言位于插入或者刪除中間的元素反而是效率最低的。所以前部分是LinkedList比ArrayList效率更高的部分)。
除了繼承自Collection的方法，List接口還額外增加了以下方法：
索引訪問：可以根據(jù)索引進行g(shù)et、set、add、addAll和remove
查找元素：indexof和lastIndexof
迭代器：
新增了一個可以返回更適合List的迭代器對象的方法listIterator(Iterator的子類)。ListIterator允許從任一方向來遍歷List對象，并在遍歷(迭代)過程中進行修改該List對象，還能獲得迭代器的當(dāng)前位置。hasNext、next是正向遍歷，hasPrevious、previous是逆向遍歷。listIterator有兩個版本，一個是無參數(shù)的，會返回一個游標指向List開頭的ListIterator，另一個是帶有一個int參數(shù)的，會返回一個游標指向指定位置的ListIterator。
混合調(diào)用next和previous會返回同一個對象，extIndex返回的是下次調(diào)用next所要返回的元素的位置，previousIndex返回的是下次調(diào)用previous所要返回的元素的位置。在同一游標位置nextIndex總是比previousIndex更大的，以下是兩種邊界情況：一種返回-1另一種返回list.size() (1) a call to previousIndex when the cursor is before the initial element returns -1 and (2) a call to nextIndex when the cursor is after the final element returns list.size().
范圍視圖:
subList,返回的List(banked)是由原本的List(banking)所支持的，因此對原本數(shù)組元素的更改會反映到返回的數(shù)組當(dāng)中。任何能對List使用的方法對返回的subList一樣能夠使用該方法可得到一個banked List,但所有的方法都還是應(yīng)該推薦在baking List上使用，而不是banked List。
因為一旦你通過banking List或者另一個由subList得到的banked List2對鏈表進行了結(jié)構(gòu)修改(其實就是增刪元素，修改元素的內(nèi)容并沒有影響)，那么該baked List的所有public方法(除了subList外和一些繼承自O(shè)bject的方法外)，都會在運行時報ConcurrentModificationException異常。
?
Arrays.asList方法：可以讓一個數(shù)組被看做是一個List，但該List底層的實現(xiàn)還是原本的數(shù)組，對List中元素的更改也就是對數(shù)組的更改。數(shù)組是無法調(diào)整大小的，也因此，這個List無法add或者remove元素。
1. ArrayList
ArrayList:內(nèi)部使用了一個名為elementData的Object數(shù)組引用變量(后面以數(shù)組變量稱呼)，在ArrayList對象創(chuàng)建之后并且還沒有添加元素之前，該變量默認指向一個static(所以變量位于方法區(qū)) final的引用變量DEFAULTCAPACITY_EMPTY_ELEMENTDATA，這個引用變量指向一個空的數(shù)組對象，這是為了避免我們反復(fù)去創(chuàng)建未使用的數(shù)組，如果當(dāng)我們反復(fù)創(chuàng)建無用的數(shù)組了，那么它們其中的elementData就全都順著引用指向著那一個空的數(shù)組對象了。
當(dāng)我們首次添加一個元素時，就會新建大小為默認值10的Object數(shù)組對象傳給數(shù)組變量，然后將元素放進去。但這個時候size只會是1而不是10，因為size指代的是真正存放的元素的數(shù)量而不是容量。而當(dāng)每次size剛超過容量時就會進行1.5倍的擴容，比如我們有了10個元素裝滿了，現(xiàn)在添加第11個元素的時候就會把數(shù)組擴容成15，然后再將原數(shù)組復(fù)制過去以及第11個元素放進去，size變成11。實際上復(fù)制操作最底層都是通過System.arraycopy()來實現(xiàn)的，也就是直接賦值的淺拷貝(可見筆記關(guān)于Object的clone方法、淺拷貝、深拷貝)，因為native方法效率比循環(huán)復(fù)制要高。
當(dāng)在對ArrayList根據(jù)索引進行一次插入(復(fù)制次數(shù)size-i)或者刪除(復(fù)制次數(shù)size-i-1)元素的時候，索引越靠后，需要復(fù)制的次數(shù)越少，效率越高，索引越靠前需要復(fù)制的次數(shù)越多，效率越低。
2. LinkedList
LinkedList就是一個雙向鏈表的實現(xiàn)，它同時實現(xiàn)了List接口和Deque接口，也是說它即可以看作一個順序鏈表，又可以看做一個隊列(Queue)，同時又可以看做一個棧(Satck)。
順便談下關(guān)于棧，在java中有個現(xiàn)成的棧類，就是java.util.Stack這個類，但這個類java官方在api中也指出不再推薦使用。而是在需要使用這種先進后出的棧時推薦使用Deque接口下的實現(xiàn)類，比如這里的LinkedList，但更推薦的是ArrayDeque。
LinkedList對指定位置的增刪查改，都會通過與size>>1(表示size/2，使用移位運算提升代碼的運行效率)的相比較的方式來選擇從前遍歷還是從后遍歷。所以當(dāng)要增刪查改的位置剛好位于中間時，效率是最低的。
四、Set接口及其實現(xiàn)類
Set的特點是不接受重復(fù)元素，其中TreeSet不接受null,因為TreeSet是用TreeMap實現(xiàn)的，TreeMap其實就是個紅黑樹，而在紅黑樹當(dāng)中是不能插入一個空節(jié)點的；其他兩個HashSet和LinkedHashSet則可以接受null元素。Set重新規(guī)定了equals和hashCode方法的實現(xiàn)，這使得equals可以用來不同類型之間的Set實現(xiàn)類對象之間來比較所包含元素是否完全相同(與List相比不用順序相同)。
HashSet提供最快的查詢速度，而TreeSet保持元素處于排序狀態(tài)，LinkedHashSet以插入順序保存元素。其中LinkedHashSet是HashSet的子類。
1. HashSet
HashSet底層是用一個HashMap來實現(xiàn)的，這個HashMap的所有鍵值映射的值都是同一個對象(一個Obect對象)，就是下面代碼當(dāng)中的final修飾的PRESENT。
private transient HashMap map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
//這里的0.75還有16都是與HashMap中默認加載因子和默認容量是一致的
public HashSet(Collection c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
HashSet中的大小、增、刪、查、遍歷等操作都是通過map來進行的，代碼如下所示，值的提一下的是remove方法，因為在HashSet里面的所有元素作為鍵對應(yīng)值都是PRESENT，在map的remove方法當(dāng)中會返回刪除元素的值(在這里一定就是PRESENT了)或者null，所以用返回的值與PRESENT進行比較也是可以得出是否刪除成功也是可以的。
public Iterator iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
最后說下HashSet的專門為LinkedHashSet預(yù)留的一個構(gòu)造函數(shù)，這是一個包訪問權(quán)限的構(gòu)造函數(shù)，實際上被設(shè)置為只被LinkedHashSet所調(diào)用到了，因為LinkedHashSet繼承了HashSet。這個構(gòu)造函數(shù)是將返回了一個LinkedHashMap對象給map，這也是LinkedHashMap的存儲實現(xiàn)原理。
/**
* Constructs a new, empty linked hash set. (This package private
* constructor is only used by LinkedHashSet.) The backing
* HashMap instance is a LinkedHashMap with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy ignored (distinguishes this
* constructor from other int, float constructor.)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
2. LinkedHashSet
正如前面所述，LinkedHashSet是繼承了HashSet的，大部分操作也是直接繼承的，只有少部分自己的方法，并且構(gòu)造器方法都是想上調(diào)用了HashSet的那個創(chuàng)建一個LinkedHashMap的構(gòu)造器方法，如下所示。所以LinkedHashSet底層是用LinkedHashMap來實現(xiàn)的，
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
@Override
public Spliterator spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
3. TreeSet
TreeSet底層是用TreeMap來實現(xiàn)的，如下面代碼所示在構(gòu)造器函數(shù)中創(chuàng)建了一個TreeMap對象，并將其賦值給了m(NavigableMap接口類型，TreeMap也實現(xiàn)了該類)，與HashSet同樣的做法：將鍵作為元素，值則都指向PRESENT，同樣對應(yīng)的查找刪除添加操作也都是調(diào)用TreeMap來完成的，這里不再重復(fù)說明。
private transient NavigableMap m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap());
}
public TreeSet(Comparator comparator) {
this(new TreeMap<>(comparator));
}
五、Queue接口及其實現(xiàn)類
Queue常用的實現(xiàn)類是ArrayDeque和LinkedList,ArrayDeque是Deque 接口的大小可變數(shù)組的實現(xiàn)。數(shù)組雙端隊列沒有容量限制；它們可根據(jù)需要增加以支持使用。它們不是線程安全的；在沒有外部同步時，它們不支持多個線程的并發(fā)訪問。禁止 null 元素。此類很可能在用作堆棧時快于Stack，在用作隊列時快于LinkedList。
Queue中的三類方法如下：
插入：The addfirst and offerFirst methods insert elements at the beginning of the Deque instance. The addLast and offerLast methods insert elements at the end of theDeque instance. When the capacity of the Deque instance is restricted, the preferred methods are offerFirst and offerLast because addFirst might fail to throw an exception if it is full.
刪除：The removeFirst and pollFirst methods remove elements from the beginning of the Deque instance. The removeLast and pollLast methods remove elements from the end. The methods pollFirst and pollLast return null if the Deque is empty whereas the methods removeFirst and removeLast throw an exception if the Deque instance is empty.
查詢：The methods getFirst and peekFirst retrieve the first element of the Deque instance. These methods dont remove the value from the Deque instance. Similarly, themethods getLast and peekLast retrieve the last element. The methods getFirst and getLast throw an exception if the deque instance is empty whereas the methods
peekFirst and peekLast return NULL.
六、Map接口及其實現(xiàn)類
(1) HashMap：它根據(jù)鍵的hashCode值存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，并且是線程安全的，任一時間只有一個線程能寫Hashtable，并發(fā)性不如ConcurrentHashMap，因為ConcurrentHashMap引入了分段鎖。Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。
(3) LinkedHashMap：LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的，也可以在構(gòu)造時帶參數(shù)，按照訪問次序排序。
(4) TreeMap：TreeMap實現(xiàn)SortedMap接口，能夠把它保存的記錄根據(jù)鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當(dāng)用Iterator遍歷TreeMap時，得到的記錄是排過序的。如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。
對于上述四種Map類型的類，要求映射中的key是不可變對象。不可變對象是該對象在創(chuàng)建后它的哈希值不會被改變。如果對象的哈希值發(fā)生變化，Map對象很可能就定位不到映射的位置了。
1. HashMap
關(guān)于HashMap主要看這篇就好了Java 8系列之重新認識HashMap，然后下面是從文中稍微摘取了自認為幾個比較重要的點吧：
存儲結(jié)構(gòu):HashMap是數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現(xiàn)的。HashMap類中有一個非常重要的字段，就是 Node[] table，即哈希桶數(shù)組，明顯它是一個Node的數(shù)組。Node是HashMap的一個內(nèi)部類，實現(xiàn)了Map.Entry接口，本質(zhì)是就是一個映射(鍵值對)。
插入：HashMap就是使用哈希表來存儲的。哈希表為解決沖突，可以采用開放地址法和鏈地址法等來解決問題，Java中HashMap采用了鏈地址法。鏈地址法，簡單來說，就是數(shù)組加鏈表的結(jié)合。在每個數(shù)組元素上都一個鏈表結(jié)構(gòu)，當(dāng)數(shù)據(jù)被Hash后，得到數(shù)組下標，把數(shù)據(jù)放在對應(yīng)下標元素的鏈表上。
容量與加載因子：HashMap默認的容量即數(shù)組的長度是16，加載因子是0.75，對應(yīng)的閾值為threshold=length*Load factor即12，當(dāng)數(shù)組中存儲的Node個數(shù)超過了12時就會進行兩倍的擴容。為什么默認數(shù)組長度是16這個在后面的散列值計算方法里面有說。為什么加載因子是0.75，原因在于這是一個是對空間和時間效率的一個平衡選擇，建議不要修改，除非在時間和空間比較特殊的情況下，如果內(nèi)存空間很多而又對時間效率要求很高，可以降低負載因子Load factor的值；相反，如果內(nèi)存空間緊張而對時間效率要求不高，可以增加負載因子loadFactor的值，這個值可以大于1。
這也符合散列表以空間換時間的特點，小于1的負載因子的存在就是為了讓數(shù)組中的鏈表長度盡可能短，因為鏈表查找是更花費時間相比于數(shù)組的訪問，負載因子如為1就是在鍵的hash值擾動取模后均勻分布的理想情況下，每個桶內(nèi)的元素個數(shù)期望是1，鏈表長度就只是1，這是最理想的情況了。但實際上分布達不到這么均勻，為了減少鏈表長度把負載因子設(shè)置成了0.75來保證鏈表長度盡可能短。當(dāng)然僅這一種減少時間的做法java官方可能還不夠，如果就是出現(xiàn)了小概率事件某個桶內(nèi)鏈表長度比較長怎么辦，java8引入了樹化桶方法。在某個桶內(nèi)鏈表長度大于8時將其該鏈表轉(zhuǎn)換為紅黑樹結(jié)構(gòu)
散列值處理方法[12]：為了提高散列值取余(取模)的速度，HashMap中用了一個按位與運算的方式來代替，當(dāng)除數(shù)是2的冪次方時，a%b與a&(b-1)的結(jié)果是等價。先假設(shè)低位是足夠隨機均勻的，取模運算參與運算的是低位，為了保證低位的所有位都被用到，就將數(shù)組長度取為了2的整次冪，這樣數(shù)組長度-1的二進制碼就全為1，就能使散列值的低位信息都能保留下來。
但僅僅直接是原始的hashCode值低位信息顯然是不行的，hashCode值是為了保證整體均勻的(即盡可能不同的對象對應(yīng)不同的散列碼)，低位可能并不怎么均勻，為了解決這種情況HashMap中會將原始的hashCode值與高16位進行一個異或(不同為1相同為0)操作，這樣就混合了原始hashCode低位和高位，加大低位隨機均勻性。然后用這個混合后的hash值再去進行按位與運算。
以上也就是為什么要使用擾動函數(shù)、默認容量為16以及自己設(shè)定的容量會被自動提升為最近的2次冪大小的原因。
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don"t change existing value(如果值不為null,不進行覆蓋，這是為putIfAbsent這種插入方法準備的)
* @param evict if false, the table is in creation mode.
* evict參數(shù)是因為LinkedHashMap預(yù)留了一個可以鏈表中長度固定，并保持最新的N的節(jié)點數(shù)據(jù)的方法afterNodeInsertion(因為removeEldestEntry始終返回false所以目前并不生效)，
* 可以通過重寫removeEldestEntry來就能進行實現(xiàn)了。
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
//
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//看看對應(yīng)桶上是不是已經(jīng)有元素了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//桶中沒有結(jié)點的話，就將其直接放進去
else {//桶中已有結(jié)點的話
Node e; K k;
//則先看hash值是否相同(來到這個位置是根據(jù)的是hash擾動后的值，可能hash值就不一樣)，鍵的內(nèi)存地址是否相同，鍵的內(nèi)容是否相等。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//三個條件均滿足了則說明鍵相等，要對這個結(jié)點(可能是鏈表的頭結(jié)點，也可能是紅黑樹的根節(jié)點)進行更新了。不滿足則要進行插入了
else if (p instanceof TreeNode)//如果是紅黑樹結(jié)點那就調(diào)用插入到紅黑樹中的方法
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {//鏈表結(jié)點則以下
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//循環(huán)后發(fā)現(xiàn)沒有相等鍵的結(jié)點，則插入到最后一個節(jié)點后面
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 保證了在插入后鏈表長度為9時就進入桶樹化函數(shù) treeify是樹化的意思。
//但這個函數(shù)只會在數(shù)組長度大于等于64時進行將hash確定的這個桶內(nèi)的鏈表轉(zhuǎn)換成紅黑樹，對應(yīng)結(jié)點也轉(zhuǎn)換成了紅黑樹結(jié)點。
//如果數(shù)組長度小于64時就只會進行擴容操作了，而不是轉(zhuǎn)換成紅黑樹，因為擴容后很可能鏈表長度就減少了
treeifyBin(tab, hash);
break;//樹化桶執(zhí)行完畢之后結(jié)束循環(huán)，并且這個時候的e是null
}
//在循環(huán)中查找有無鍵相等的結(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//看hash值是否相同(來到這個位置是根據(jù)的是hash擾動后的值，可能hash值就不一樣)，鍵的內(nèi)存地址是否相同，鍵的內(nèi)容是否相等。
break;//相等則從循環(huán)中跳出來，這個時候的e保存的是桶內(nèi)鍵相等的結(jié)點的引用
p = e;
}
}
//e!=null說明e桶內(nèi)鍵相等的結(jié)點的引用，則進行值的覆蓋
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
?
2. LinkedHashMap
LinkedHashMap是HashMap的子類，相比HashMap增加的就是更換了結(jié)點為自己的內(nèi)部靜態(tài)類LinkedHashMap.Entry,這個Entry繼承自HashMap.Node,增加了before和after指針用來記錄插入順序。如下圖[via9]所示
3. TreeMap
用紅黑樹實現(xiàn)，關(guān)于紅黑樹實現(xiàn)原理已經(jīng)寫過了就不再寫了。
七、并發(fā)下的容器類
1.對于ArrayList和LinkedList
這兩個List實現(xiàn)類都不是同步的。如果多個線程同時訪問一個ArrayList或者LinkedList實例，而其中至少一個線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步。（結(jié)構(gòu)上的修改是指任何添加或刪除一個或多個元素的操作，或者顯式調(diào)整底層數(shù)組的大小；僅僅設(shè)置元素的值不是結(jié)構(gòu)上的修改。）
這一般通過對封裝該List的對象進行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用Collections.synchronizedList方法將該列表“包裝”起來。這最好在創(chuàng)建時完成，以防止意外對列表進行不同步的訪問，如下所示：
List list = Collections.synchronizedList(new ArrayList(...));
List list = Collections.synchronizedList(new LinkedList(...));
2.對于HashSet、LinkedHashSet和TreeSet
注意，這三個Set實現(xiàn)類都不是同步的。如果多個線程同時訪問HashSet、LinkedHashSet或者TreeSet，而其中至少一個線程修改了該set，則它必須保持外部同步。
這一般通過對封裝該set的對象進行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用 Collections.synchronizedSet (對于TreeSet是Collections.synchronizedSortedSet)方法來“包裝”該 set。最好在創(chuàng)建時完成這一操作，以防止意外的非同步訪問：
Set s = Collections.synchronizedSet(new LinkedHashSet(...));
Set s = Collections.synchronizedSet(new HashSet(...));
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
3.對于HashMap、LinkedHashMap和TreeMap
注意，這三個Map實現(xiàn)類都不是同步的。如果多個線程同時訪問一個HashMap、LinkedHashMap或者TreeMap，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須 保持外部同步。這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用 Collections.synchronizedMap(對于TreeMap應(yīng)該使用Collections.synchronizedSortedMap)方法來“包裝”該映射。最好在創(chuàng)建時完成這一操作，以防止對映射進行意外的非同步訪問，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...));
Map m = Collections.synchronizedMap(new LinkedHashMap(...));
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
（結(jié)構(gòu)上的修改是指添加或刪除一個或多個映射關(guān)系的任何操作；僅改變與實例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改。對于LinkedHashMap而言，當(dāng)按訪問排序的HashMap時，結(jié)構(gòu)上的修改還包括影響迭代順序的任何操作，但此時僅利用get查詢LinkedHashMapMap不是結(jié)構(gòu)修改）
參考文章：
Java? Platform Standard Ed. 8 Api
在中間位置添加元素，ArrayList比LinkedList效率更高？
arraylist add(int index) 方法時 index是處于前半部分還是后半部分效率高
ArrayList初始化
ArrayList底層數(shù)組擴容原理
List、Set、Map的區(qū)別
Java集合框架源碼剖析：LinkedHashSet 和 LinkedHashMap
淺談java 集合框架
JDK 源碼中 HashMap 的 hash 方法原理是什么？胖君的回答
編程語言中，取余和取模的區(qū)別到底是什么？
深入理解 hashcode 和 hash 算法
