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