工具類：Collection和Map，兩者是同一級(jí)別的

知識(shí)點(diǎn)：
expectedModCount
ArrayList：懶加載，transient，System.arraycopy()
LinkedList：雙向鏈表
Vector：鎖機(jī)制
Stack：繼承Vector，
知識(shí)點(diǎn)：
初始化：tableForSize
put:計(jì)算hash/如何轉(zhuǎn)樹擴(kuò)容
擴(kuò)容：如何定位
遍歷：迭代器
為什么是2
1.7/1.8d的區(qū)別
對(duì)比區(qū)別
LinkedListHashMap：結(jié)構(gòu)，LRU
TreeMap：比較器，一致性哈希
Queue:隊(duì)列
Set：內(nèi)置HashMap

List

arraylist源碼閱讀：
知識(shí)點(diǎn)一：

private transient Object[] elementData;

elementData，假如現(xiàn)在實(shí)際有了5個(gè)元素，而elementData的大小可能是10，那么在序列化時(shí)只需要儲(chǔ)存5個(gè)元素，數(shù)組中的最后五個(gè)元素是沒有實(shí)際意義的，不需要儲(chǔ)存。所以ArrayList的設(shè)計(jì)者將elementData設(shè)計(jì)為transient，然后在writeObject方法中手動(dòng)將其序列化，并且只序列化了實(shí)際存儲(chǔ)的那些元素，而不是整個(gè)數(shù)組

知識(shí)點(diǎn)二：
初始化時(shí)，如果指定Capacity則生成Capacity大小的數(shù)組，如果沒有指定則為空，等到添加元素的時(shí)候再擴(kuò)容，節(jié)約內(nèi)存懶加載機(jī)制？

參考資料

// 空的數(shù)組private static final Object[] EMPTY_ELEMENTDATA = {};// 默認(rèn)容量的空數(shù)組private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

這里有兩個(gè)空數(shù)組的定義，注意到是static，final不可改變的常量。所以說我們可以推斷，當(dāng)定義很多個(gè)空的ArrayList，他們都指向這兩個(gè)數(shù)組節(jié)約內(nèi)存

知識(shí)點(diǎn)三：
所以indexOf(Object o),remove等都可以穿入null
o==null
null既不是對(duì)象也不是一種類型，它僅是一種特殊的值，你可以將其賦予任何引用類型，它還僅僅是一個(gè)特殊值,并不屬于任何類型，用instanceof永遠(yuǎn)返回false

知識(shí)點(diǎn)四：

參考資料
操作中實(shí)現(xiàn)可拓展數(shù)組，根本在于System.arraycopy()
是native方法，一般是借助C/C++實(shí)現(xiàn)的

復(fù)制方法有四種：
1、for循環(huán)，手動(dòng)復(fù)制
2、System.arraycopy()方法
3、Arrays.copyOf()方法
4、clone()方法
由于System.arraycopy()是最貼近底層的，其使用的是內(nèi)存復(fù)制，省去了大量的數(shù)組尋址訪問等時(shí)間，故效率最高。
對(duì)于Arrays.copyOf()方法查看源碼可以看到：
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
它是借助System.arraycopy()方法實(shí)現(xiàn)的，故效率次于System.arraycopy()
clone()方法效率是最低的，一般需要重寫

LinkedList源碼閱讀
知識(shí)點(diǎn)一：可以看到LinkedList基于鏈表，并且是雙向循環(huán)鏈表，每一個(gè)節(jié)點(diǎn)是一個(gè)Entry，element，next，previous，構(gòu)造方法和entry(int index) ，entry(int index) 找index位置的元素并返回。其他的操作比如add,remove都是符合雙向循環(huán)鏈表基本操作

private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) {this.element = element;this.next = next;this.previous = previous; } private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);Entry<E> e = header;// 根據(jù)這個(gè)判斷決定從哪個(gè)方向遍歷這個(gè)鏈表if (index < (size >> 1)) {for (int i = 0; i <= index; i++)e = e.next;} else {// 可以通過header節(jié)點(diǎn)向前遍歷，說明這個(gè)一個(gè)循環(huán)雙向鏈表，header的previous指向鏈表的最后一個(gè)節(jié)點(diǎn)，這也驗(yàn)證了構(gòu)造方法中對(duì)于header節(jié)點(diǎn)的前后節(jié)點(diǎn)均指向自己的解釋for (int i = size; i > index; i--)e = e.previous;}return e;}}

知識(shí)點(diǎn)二“：
expectedModCount字段，
modCount，用于記錄對(duì)象的修改次數(shù)，比如增、刪、改
可以理解成version，在特定的操作下需要對(duì)version進(jìn)行檢查，適用于Fail-Fast機(jī)制。
Fail-Fast 機(jī)制
比如當(dāng)A通過iterator去遍歷某集合的過程中，因?yàn)閕terator長時(shí)間擁有對(duì)象，而且是線程安全即其他線程也可以操作對(duì)象，所以為了防止便利的時(shí)候讀取臟數(shù)據(jù)，通過checkForComodification（）方法，判斷modCount==expectedModCount，若其他線程修改了此集合，此時(shí)會(huì)拋出ConcurrentModificationException異常。

知識(shí)點(diǎn)三：重寫clone方法，利用clone.add(e.element);

public Object clone() {LinkedList<E> clone = null;try {clone = (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError();}clone.header = new Entry<E>(null, null, null);clone.header.next = clone.header.previous = clone.header;clone.size = 0;clone.modCount = 0;for (Entry<E> e = header.next; e != header; e = e.next)clone.add(e.element);return clone； }

Iterator:

參考資料

參考資料
知識(shí)點(diǎn)一：
接口中的default方法，能夠在借口中直接寫方法體和抽象類的區(qū)別又縮小了
但是如果實(shí)現(xiàn)A，B兩個(gè)接口都有相同函數(shù)簽名的default的方法，必須重寫因?yàn)椴恢缿?yīng)該繼承哪個(gè)
如果繼承父類A，和實(shí)現(xiàn)接口B都有default方法，則會(huì)實(shí)際為父類A的方法

知識(shí)點(diǎn)二：
首先Java提供兩個(gè)迭代器接口Iterator和ListIterator
Iterator方法比較少：next,hasNext,remove
ListIterator方法比較多：add，previous等等

參考資料

AbstractList：是ArrayList和LinkedList的父類
實(shí)現(xiàn)了兩個(gè)內(nèi)部類Itr和ListItr
Itr：實(shí)現(xiàn)Iterator接口
ListItr：實(shí)現(xiàn)ListIterator并且繼承自Itr

ArrayList：直接使用AbstractList的Itr
Itr：cursor lastRet(remove時(shí)移除此元素)利用數(shù)組特性遍歷

checkForComodification(); try { Object next = get(cursor);//先取當(dāng)前光標(biāo)所在位置后面的元素 lastRet = cursor++;//然后把最后一次操作所在光標(biāo)設(shè)置成當(dāng)前光標(biāo)位置，再把當(dāng)前光標(biāo)后移一 return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); }

LinkedList：
單獨(dú)定義內(nèi)部類ListItr，它實(shí)現(xiàn)了ListIterator接口，用來對(duì)LinkedList進(jìn)行專門迭代，因?yàn)長inkedList與ArrayList還不同，它是使用鏈表結(jié)構(gòu)實(shí)現(xiàn)的，所以需專門的迭代器。
ListItr：
lastReturned：最近一次操作返回的元素
Entry next：即將返回的元素
nextIndex：即將返回的元素的編號(hào)

public Object next() { //檢查外部是否修改了集合結(jié)構(gòu)，即modCount是否與expectedModCount相等 checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next;//先記錄next所在位置，并把它賦給lastReturned next = next.next;//然后再把next指向下一個(gè)元素 nextIndex++;//nextIndex與next操作需同步，所以也要增一 return lastReturned.element; }

Vector
參考資料
1：底層實(shí)現(xiàn)與ArrayList類似，基于數(shù)組
2：線程安全，add,remove方法都是synchronized方法。但是其實(shí)并不是真正的意義安全，對(duì)方法加鎖實(shí)際上是沒有太大意義的。因?yàn)槿绻闵暾?qǐng)遍歷Vector，同樣需要鎖來禁止修改Vector遍歷沒加鎖而修改加鎖。注意add,remov仍然是不能同時(shí)執(zhí)行的，因?yàn)閟ynchronized非靜態(tài)方法是對(duì)對(duì)象實(shí)例加鎖，并且效率低下
3： Vector擴(kuò)容由oldCapacity 與 capacityIncrement共同決定，

int newCapacity = oldCapacity + ((capacityIncrement > 0) ？capacityIncrement : oldCapacity);

而ArrayList為

int newCapacity = (oldCapacity * 3)/2 + 1;

參考資料
stack：
public class Stack extends Vector
Vector：
public class Vector extends AbstractList implements List, RandomAccess, Cloneable, Serializable
繼承Vector 并實(shí)現(xiàn)pop，push等方法
問題一：為什么說Java的Stack類實(shí)現(xiàn)List接口是個(gè)笑話？
因?yàn)镾tack是FILO，但是LIst是RandomAccess，從設(shè)計(jì)角度上講不合理。接口的實(shí)現(xiàn)，不取決于類的應(yīng)用場景，而是接口的契約的應(yīng)用場景，固然棧有些時(shí)候是需要隨機(jī)訪問，但是他本質(zhì)還是FILO
就像牙刷是用來刷牙的，但是有些時(shí)候我們的確也可以用來洗衣服
問題二：為什么stack是一個(gè)類？
因?yàn)閏ollection體系是在jdk1.2被設(shè)計(jì)出來的，而vector，stack，hashtable這些是隨java的第一個(gè)版本就發(fā)布了的。簡而言之，在最初的java版本中，提供了基本的容器實(shí)現(xiàn)，但未經(jīng)良好設(shè)計(jì)，因此在革命性的1.2版本中，重新設(shè)計(jì)了后來獲得廣泛好評(píng)的Collection體系

HashMap

參考資料

參考資料
前沿：首先HashMap具體實(shí)現(xiàn)是由鏈表+數(shù)組的實(shí)現(xiàn)方式，并且采用了動(dòng)態(tài)擴(kuò)容技術(shù)
數(shù)據(jù)結(jié)構(gòu)：

特點(diǎn)：
1：動(dòng)態(tài)擴(kuò)充
數(shù)組是否需要擴(kuò)充是通過負(fù)載因子判斷的，如果當(dāng)前元素個(gè)數(shù)為數(shù)組容量的0.75時(shí)，就會(huì)擴(kuò)充數(shù)組。這個(gè)0.75就是默認(rèn)的負(fù)載因子，可由構(gòu)造傳入。我們也可以設(shè)置大于1的負(fù)載因子，這樣數(shù)組就不會(huì)擴(kuò)充，犧牲性能，節(jié)省內(nèi)存。
2：鏈表和紅黑樹轉(zhuǎn)化：
為了解決碰撞，數(shù)組中的元素是單向鏈表類型。當(dāng)1:鏈表長度到達(dá)一個(gè)閾值時(shí)（7或8）TREEIFY_THRESHOLD并且2:總數(shù)量是否到達(dá)一個(gè)閾值（64），會(huì)將鏈表轉(zhuǎn)換成紅黑樹提高性能。而當(dāng)鏈表長度縮小到另一個(gè)閾值時(shí)（6）UNTREEIFY_THRESHOLD，又會(huì)將紅黑樹轉(zhuǎn)換回單向鏈表提高性能
TreeNodes占用空間是普通Nodes的兩倍(兩個(gè)指針和一個(gè)指針)所以剛開始用Nodes節(jié)省空間，后面當(dāng)鏈表長度大泊松分布幾率小時(shí)再用紅黑樹

3：數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹
拉鏈法進(jìn)行沖突處理

內(nèi)部類：
繼承關(guān)系如下：Node是單向鏈表節(jié)點(diǎn)，Entry是雙向鏈表節(jié)點(diǎn)，TreeNode是紅黑樹節(jié)點(diǎn)。
Node->Entry->TreeNode
注意Entry是JDK1.7之前的數(shù)據(jù)機(jī)構(gòu)，1.8后主要是用Node和TreeNode不用Entry可能認(rèn)為雙向循環(huán)鏈表意義不大，效率不如Node

Node

static class Node<K,V> implements Map.Entry<K,V> {// hash是經(jīng)過hash()方法處理過的hashCode，為了使hashCode分布更加隨機(jī)，// 待會(huì)會(huì)深入這個(gè)hash()方法。final int hash; final K key;V value;Node<K,V> next; // 下一個(gè)節(jié)點(diǎn)Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final int hashCode() {// key的hashCode異或value的哈希Codereturn Objects.hashCode(key) ^ Objects.hashCode(value);}// 其余略}

HashMap方法：

成員變量

/*** 數(shù)組的默認(rèn)初始長度，java規(guī)定hashMap的數(shù)組長度必須是2的次方* 擴(kuò)展長度時(shí)也是當(dāng)前長度 << 1。*/ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 數(shù)組的最大長度 static final int MAXIMUM_CAPACITY = 1 << 30;// 默認(rèn)負(fù)載因子，當(dāng)元素個(gè)數(shù)超過這個(gè)比例則會(huì)執(zhí)行數(shù)組擴(kuò)充操作。 static final float DEFAULT_LOAD_FACTOR = 0.75f;// 樹形化閾值，當(dāng)鏈表節(jié)點(diǎn)個(gè)大于等于TREEIFY_THRESHOLD - 1時(shí)， // 會(huì)將該鏈表換成紅黑樹。 static final int TREEIFY_THRESHOLD = 8;// 解除樹形化閾值，當(dāng)鏈表節(jié)點(diǎn)小于等于這個(gè)值時(shí)，會(huì)將紅黑樹轉(zhuǎn)換成普通的鏈表。 static final int UNTREEIFY_THRESHOLD = 6;// 最小樹形化的容量，即：當(dāng)內(nèi)部數(shù)組長度小于64時(shí)，不會(huì)將鏈表轉(zhuǎn)化成紅黑樹，而是優(yōu)先擴(kuò)充數(shù)組。 static final int MIN_TREEIFY_CAPACITY = 64;// 這個(gè)就是hashMap的內(nèi)部數(shù)組了，而Node則是鏈表節(jié)點(diǎn)對(duì)象。 transient Node<K,V>[] table;// 下面三個(gè)容器類成員，作用相同，實(shí)際類型為HashMap的內(nèi)部類KeySet、Values、EntrySet。 // 他們的作用并不是緩存所有的key或者所有的value，內(nèi)部并沒有持有任何元素。 // 而是通過他們內(nèi)部定義的方法，從三個(gè)角度（視圖）操作HashMap，更加方便的迭代。 // 關(guān)注點(diǎn)分別是鍵，值，映射。 transient Set<K> keySet; // AbstractMap的成員 transient Collection<V> values; // AbstractMap的成員 transient Set<Map.Entry<K,V>> entrySet;// 元素個(gè)數(shù)，注意和內(nèi)部數(shù)組長度區(qū)分開來。 transient int size;// 再上一篇文章中說過，是容器結(jié)構(gòu)的修改次數(shù)，fail-fast機(jī)制。 transient int modCount;// 閾值，超過這個(gè)值時(shí)擴(kuò)充數(shù)組。 threshold = capacity * load factor，具體看上面的靜態(tài)常量。 int threshold;// 裝在因子，具體看上面的靜態(tài)常量。 final float loadFactor;

其中，Node等為transient變量
1：有很多空的元素，不需要序列化
2：HashCode依賴于不同的虛擬機(jī)，常規(guī)序列化可能導(dǎo)致錯(cuò)誤

1：構(gòu)造方法
//主要是對(duì)傳入的initialCapacity和loadFactor進(jìn)行參數(shù)檢驗(yàn)，沒有為數(shù)組table分配內(nèi)存空間而是在執(zhí)行put操作的時(shí)候才真正構(gòu)建table數(shù)組

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);　　　　init();//init方法在HashMap中沒有實(shí)際實(shí)現(xiàn)，不過在其子類如 linkedHashMap中就會(huì)有對(duì)應(yīng)實(shí)現(xiàn)}

public HashMap(int initialCapacity, float loadFactor)這個(gè)構(gòu)造可以由我們指定數(shù)組的初始容量和負(fù)載因子。
但是前面說過，數(shù)組容量必須是2的次方。所以就需要通過某個(gè)算法將我們給的數(shù)值轉(zhuǎn)換成2的次方。
tableSizeFor(int cap)就是這個(gè)作用。

// 這個(gè)方法可以將任意一個(gè)整數(shù)轉(zhuǎn)換成2的次方。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
0000 0100 0000 0000
0000 0110 0000 0000
0000 0111 1000 0000
0000 0111 1111 1000
0000 0111 1111 1111
0000 1000 0000 0000 可以看到變成2的次方
為什么要 int n = cap - 1？
我的理解是，因?yàn)榻o定的MAXIMUM_CAPACITY = 1 << 30，相當(dāng)于在說明文檔中說，最大值可以取1<<30。如果不減1，那么將1<<30帶入后結(jié)果為0，與要求不符，所以-1后計(jì)算。

當(dāng)然，如果未指定容量，則同樣也是懶加載機(jī)制

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

特點(diǎn)

2：put
檢查數(shù)組是否為空，執(zhí)行resize()擴(kuò)充；
通過hash值計(jì)算數(shù)組索引，獲取該索引位的首節(jié)點(diǎn)。
如果首節(jié)點(diǎn)為null，直接添加節(jié)點(diǎn)到該索引位。
如果首節(jié)點(diǎn)不為null，那么有3種情況
① key和首節(jié)點(diǎn)的key相同，覆蓋value；否則執(zhí)行②或③
② 如果首節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)（TreeNode），將鍵值對(duì)添加到紅黑樹。
③ 如果首節(jié)點(diǎn)是鏈表，將鍵值對(duì)添加到鏈表。添加之后會(huì)判斷鏈表長度是否到達(dá)TREEIFY_THRESHOLD - 1這個(gè)閾值，“嘗試”將鏈表轉(zhuǎn)換成紅黑樹。
最后判斷當(dāng)前元素個(gè)數(shù)是否大于threshold，擴(kuò)充數(shù)組。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {//tab存放當(dāng)前的哈希桶，p用作臨時(shí)鏈表節(jié)點(diǎn) Node<K,V>[] tab; Node<K,V> p; int n, i;//如果當(dāng)前哈希表是空的，代表是初始化//table為Entry,tab為Node,Entry是Node的子類，上轉(zhuǎn)型對(duì)象if ((tab = table) == null || (n = tab.length) == 0)//那么直接去擴(kuò)容哈希表，并且將擴(kuò)容后的哈希桶長度賦值給nn = (tab = resize()).length;//如果當(dāng)前index的節(jié)點(diǎn)是空的，表示沒有發(fā)生哈希碰撞。直接構(gòu)建一個(gè)新節(jié)點(diǎn)Node，掛載在index處即可。if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//否則 發(fā)生了哈希沖突。Node<K,V> e; K k;//如果哈希值相等，key也相等，則是覆蓋value操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//將當(dāng)前節(jié)點(diǎn)引用賦值給eelse if (p instance of TreeNode)//如果是紅黑樹節(jié)點(diǎn)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//不是紅黑樹節(jié)點(diǎn)//遍歷鏈表for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//遍歷到尾部，，仍沒有key與其相等，說明是新節(jié)點(diǎn)，追加新節(jié)點(diǎn)到尾部p.next = newNode(hash, key, value, null);//如果追加節(jié)點(diǎn)后，鏈表數(shù)量>=8，則轉(zhuǎn)化為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果找到key與其相同，說明是曾經(jīng)插入過的節(jié)點(diǎn)if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果e不是null，說明有需要覆蓋的節(jié)點(diǎn)，由上面的break;彈出if (e != null) { // existing mapping for key//則覆蓋節(jié)點(diǎn)值，并返回原oldValueV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;//這是一個(gè)空實(shí)現(xiàn)的函數(shù)，用作LinkedHashMap重寫使用。afterNodeAccess(e);return oldValue;}}//如果執(zhí)行到了這里，說明插入了一個(gè)新的節(jié)點(diǎn)，所以會(huì)修改modCount，以及返回null。++modCount;//更新size，并判斷是否需要擴(kuò)容。if (++size > threshold)resize();//這是一個(gè)空實(shí)現(xiàn)的函數(shù)，用作LinkedHashMap重寫使用。afterNodeInsertion(evict);return null; }

計(jì)算實(shí)際存儲(chǔ)位置：
1：利用Java重寫的HashCode計(jì)算哈希值
2：對(duì)哈希值進(jìn)行擾動(dòng)處理 (h = key.hashCode()) ^ (h >>> 16)
3：與運(yùn)算代替模計(jì)算(n - 1) & hash

hash()：轉(zhuǎn)為hash值

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

hashCode的高16位與低16位進(jìn)行異或運(yùn)算注意h進(jìn)行h >>> 16已經(jīng)被賦值，因?yàn)閮?nèi)部數(shù)組的容量一般都不會(huì)很大，基本分布在16~256之間。所以一個(gè)32位的hashCode，一直都用最低的4到8位進(jìn)行與運(yùn)算，而高位幾乎沒有參與。“擾動(dòng)函數(shù)”
獲得索引值：

(p = tab[i = (n - 1) & hash]) == null

(n - 1) & hash實(shí)際上=hash%(n)n是長度，為一個(gè)2的次方數(shù)
利用與運(yùn)算代替模運(yùn)算可以極大增加運(yùn)算速度

Hash表擴(kuò)容：
1：計(jì)算新數(shù)組的容量和閾值
2：將原數(shù)組的元素拷貝到新數(shù)組中
這里JDK1.7之前利用的是重新計(jì)算Hash索引，即rehash操作
1.8后，由于數(shù)組容量是2的次方且擴(kuò)充后翻倍，則只需要判斷原來的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”

final HashMap.Node<K,V>[] resize() {HashMap.Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 如果數(shù)組已經(jīng)是最大長度，不進(jìn)行擴(kuò)充。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 否則數(shù)組容量擴(kuò)充一倍。（2的N次方）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 如果數(shù)組還沒創(chuàng)建，但是已經(jīng)指定了threshold（這種情況是帶參構(gòu)造創(chuàng)建的對(duì)象），threshold的值為數(shù)組長度// 在 "構(gòu)造函數(shù)" 那塊內(nèi)容進(jìn)行過說明。else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 這種情況是通過無參構(gòu)造創(chuàng)建的對(duì)象else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 可能是上面newThr = oldThr << 1時(shí)，最高位被移除了，變?yōu)?。if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;// 到了這里，新的數(shù)組長度已經(jīng)被計(jì)算出來，創(chuàng)建一個(gè)新的數(shù)組。@SuppressWarnings({"rawtypes","unchecked"})HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];table = newTab;// 下面代碼是將原來數(shù)組的元素轉(zhuǎn)移到新數(shù)組中。問題在于，數(shù)組長度發(fā)生變化。 // 那么通過hash%數(shù)組長度計(jì)算的索引也將和原來的不同。// jdk 1.7中是通過重新計(jì)算每個(gè)元素的索引，重新存入新的數(shù)組，稱為rehash操作。// 這也是hashMap無序性的原因之一。而現(xiàn)在jdk 1.8對(duì)此做了優(yōu)化，非常的巧妙。if (oldTab != null) {// 遍歷原數(shù)組for (int j = 0; j < oldCap; ++j) {// 取出首節(jié)點(diǎn)HashMap.Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;// 如果鏈表只有一個(gè)節(jié)點(diǎn)，那么直接重新計(jì)算索引存入新數(shù)組。if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 如果該節(jié)點(diǎn)是紅黑樹，執(zhí)行split方法，和鏈表類似的處理。else if (e instanceof HashMap.TreeNode)((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 此時(shí)節(jié)點(diǎn)是鏈表else { // preserve order// loHead，loTail為原鏈表的節(jié)點(diǎn)，索引不變。HashMap.Node<K,V> loHead = null, loTail = null;// hiHeadm, hiTail為新鏈表節(jié)點(diǎn)，原索引 + 原數(shù)組長度。HashMap.Node<K,V> hiHead = null, hiTail = null;HashMap.Node<K,V> next;// 遍歷鏈表do {next = e.next;// 新增bit為0的節(jié)點(diǎn)，存入原鏈表。if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 新增bit為1的節(jié)點(diǎn)，存入新鏈表。else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原鏈表存回原索引位if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 新鏈表存到：原索引位 + 原數(shù)組長度if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab; }

4:遍歷
參考資料
KeySet，values，EntrySet
Set< String>,Collections< String>,Set< Entry< String,String>>

在HashMap構(gòu)造時(shí)，只有一個(gè)KeySet的引用，而只有當(dāng)用戶調(diào)用Map.KeySet()方法時(shí)，才實(shí)例化一個(gè)最新的KeySet懶加載機(jī)制
public Set keySet() {
Set ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
而在KeySet是一個(gè)內(nèi)部類
擁有
一：iterator，即可以通過遍歷器遍歷
public final Iterator iterator() { return new KeyIterator(); }
返回一個(gè)KeyIterator，而KeyIterator有nextNode方法進(jìn)行遍歷
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
// fast-fail 機(jī)制的實(shí)現(xiàn) 即在迭代器往后遍歷時(shí)，每次都檢測expectedModCount是否和modCount相等
// 不相等則拋出ConcurrentModificationException異常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//如果遍歷越界，則拋出NoSuchElementException異常
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
//如果遍歷到末尾，則跳到table中下一個(gè)不為null的節(jié)點(diǎn)處
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
二：調(diào)用forEach方法
public final void forEach(Consumer<? super V> action) {—}思想和上述類似，都是利用tab[index]進(jìn)行遍歷訪問，并沒有涉及Set元素的增添

五：化樹

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // 紅黑樹父節(jié)點(diǎn)TreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // 刪除后需要取消鏈接boolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}

我們知道當(dāng)一個(gè)桶中節(jié)點(diǎn)數(shù)量超過8時(shí)就會(huì)轉(zhuǎn)化為紅黑樹，過程如下：
步驟一：treeifyBin()先將所有節(jié)點(diǎn)替換為TreeNode，然后再將單鏈表轉(zhuǎn)為雙鏈表
步驟二：treeify(tab);依次比較節(jié)點(diǎn)，分別比較Hash值（HashCode異或16位的值），是否有比較器，兩者的類名（），對(duì)象的HashCode
步驟三：進(jìn)行平衡調(diào)整
d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0

關(guān)鍵點(diǎn)：為什么實(shí)際大小總是2的冪？
我的理解：

原因一：
因?yàn)閕ndex=hash%length-1
比如對(duì)于：
length=16 則length-1 =15 即 00001111
length=32 則length-1=31 即 00011111
可以看到，對(duì)于一個(gè)相同的hash，分別&兩個(gè)不同的length-1，得到的結(jié)果result1,result2 差別就只在右數(shù)第5位，相當(dāng)于擴(kuò)容后只要修改一位就可以改變索引

原因二:
因?yàn)閘ength=2^n，則length-1的位都是保持00001111111的形狀，而hash&length-1中，高位不會(huì)產(chǎn)生影響，而低位任意一個(gè)變化變化都會(huì)產(chǎn)生影響，減少?zèng)_突的概率。
在h<length的情況下：
對(duì)于長度：23 length-1則比特為 10110，則對(duì)于結(jié)果result=10110
既可以是h=11110 10110 11111 10111 都對(duì)應(yīng)相同的結(jié)果沖突增加
而對(duì)于長度32 length-1 則比特位11111 ，則對(duì)于結(jié)果10110
只有h=10110才可以與其對(duì)應(yīng)

原因三：可以用與運(yùn)算代替模運(yùn)算，增加了效率

JDK1.7和JDK1.8中HashMap的區(qū)別
底層：
最重要的一點(diǎn)是底層結(jié)構(gòu)不一樣，1.7是數(shù)組+鏈表，1.8則是數(shù)組+鏈表+紅黑樹結(jié)構(gòu);并且內(nèi)部類的實(shí)現(xiàn)也有區(qū)別
1.7：Entry
1.8：Node-Entry-TreeNode 兩個(gè)Entry是不同的

put：
1：1.8中會(huì)將節(jié)點(diǎn)插入到鏈表尾部，而1.7中是采用頭插
頭插法：
1:擴(kuò)容時(shí)顛倒鏈表順序
2:擴(kuò)容時(shí)形成閉環(huán)
線程1插入節(jié)點(diǎn)A，線程2插入節(jié)點(diǎn)B。順序
1A 2B 2A 此時(shí)成環(huán)
而尾插法會(huì)遍歷鏈表，如果發(fā)現(xiàn)已經(jīng)在則停止
為什么頭插法形成閉環(huán)
2：jdk1.7中的hash函數(shù)對(duì)哈希值的計(jì)算直接使用key的hashCode值，而1.8中則是采用key的hashCode異或上key的hashCode進(jìn)行無符號(hào)右移16位的結(jié)果，避免了只靠低位數(shù)據(jù)來計(jì)算哈希時(shí)導(dǎo)致的沖突，計(jì)算結(jié)果由高低位結(jié)合決定，使元素分布更均勻；

擴(kuò)容：
1：擴(kuò)容時(shí)1.8會(huì)保持原鏈表的順序，而1.7會(huì)顛倒鏈表的順序；
2：jdk1.8是擴(kuò)容時(shí)通過hash&cap是否等于0將鏈表分散，無需改變hash值，而1.7是通過更新hashSeed來修改hash值達(dá)到分散的目的；
3：擴(kuò)容策略：1.7中是只要不小于閾值就直接擴(kuò)容2倍；而1.8的擴(kuò)容策略會(huì)更優(yōu)化，當(dāng)數(shù)組容量未達(dá)到64時(shí)，以2倍進(jìn)行擴(kuò)容，超過64之后若桶中元素個(gè)數(shù)不小于7就將鏈表轉(zhuǎn)換為紅黑樹，但如果紅黑樹中的元素個(gè)數(shù)小于6就會(huì)還原為鏈表，當(dāng)紅黑樹中元素大于32的時(shí)候才會(huì)再次擴(kuò)容。

HashTable：
Hashtable 是遺留類
很多映射的常用功能與 HashMap 類似，不同的是它承自 Dictionary 類，
線程安全的，并發(fā)性不如 ConcurrentHashMap，
HashTable和HashMap的區(qū)別：
1:HashTable線程安全，HashMap線程不安全
2:HashTable不允許鍵和值為Null，而HashMap允許。
兩點(diǎn)原因：
1：源碼角度
HashTable：可以看到會(huì)直接調(diào)用hash=key.hashCode();當(dāng)key為null時(shí)報(bào)錯(cuò)
而HashMap會(huì)進(jìn)行一個(gè)判斷，如果key為null則設(shè)為0

2:設(shè)計(jì)角度，hashtable為早期版本，可能認(rèn)為null不可以作為分類依據(jù)。而后面的hashmap可能認(rèn)為null也可以作為分類依據(jù)

HashTable、ConcurrentHashMap以及Collections中的靜態(tài)方法SynchronizedMap比較：
HashTable：對(duì)set/get方法都使用synchronized
SynchronizedMap：內(nèi)部封裝HashMap，加了synchronized
ConcurrentHashMap：synchronized+CAS

紅黑樹：
參考資料
參考資料
性質(zhì)：
1：根節(jié)點(diǎn)和葉子結(jié)點(diǎn)是黑色
2：不能出現(xiàn)連續(xù)的兩個(gè)紅色結(jié)點(diǎn)
3：從根到任意葉子結(jié)點(diǎn)上的黑色結(jié)點(diǎn)數(shù)相同
根據(jù)定義：
若節(jié)點(diǎn)只有一棵子樹，那么一定是黑根+紅子

查找：O(log2(N))的時(shí)間復(fù)雜度
插入：插入節(jié)點(diǎn)都是紅色結(jié)點(diǎn)
判斷父親節(jié)點(diǎn)
1：若是黑色，直接插入紅色節(jié)點(diǎn)
2：若是紅色，判斷叔叔節(jié)點(diǎn)。插入紅色節(jié)點(diǎn)后
若叔叔節(jié)點(diǎn)是紅色：交換色（父叔節(jié)點(diǎn)和祖父節(jié)點(diǎn)換色）
若叔叔節(jié)點(diǎn)是黑色（或者不存在）：交換色+旋轉(zhuǎn) 四種情況
其實(shí)不可能是黑色，只有不存在的情形。因?yàn)楦赣H節(jié)點(diǎn)是單子樹或者子節(jié)點(diǎn)，但是如果是單子樹只能是黑色（這樣卻不滿足性質(zhì)3），所以父親節(jié)點(diǎn)是葉子結(jié)點(diǎn)，那么叔叔只能是紅色或者無
刪除：
步驟1：確定實(shí)際的刪除位置
步驟2：當(dāng)進(jìn)入情形1時(shí)，進(jìn)行樹的平衡調(diào)整

步驟1：
情形1：葉子節(jié)點(diǎn)：如果是紅色直接刪除，如果是黑色那么需要進(jìn)行平衡
情形2：有一個(gè)葉子：子節(jié)點(diǎn)代替（變?yōu)閯h除子節(jié)點(diǎn)）——轉(zhuǎn)化為情形1或2或3
情形3：有兩個(gè)葉子：最鄰近代替（一般是右子樹，變?yōu)閯h除替換節(jié)點(diǎn)）——直接轉(zhuǎn)化為情形1
葉子代替的時(shí)候，將代替節(jié)點(diǎn)轉(zhuǎn)化為被代替的顏色

樹的平衡調(diào)整
被刪除結(jié)點(diǎn)：
若被刪除結(jié)點(diǎn)兄弟節(jié)點(diǎn)在右子樹
被刪除結(jié)點(diǎn)節(jié)點(diǎn)紅色：直接刪除
被刪除結(jié)點(diǎn)節(jié)點(diǎn)黑色：
1 被刪除結(jié)點(diǎn)兄弟節(jié)點(diǎn)為紅色：父親兄弟改色+旋轉(zhuǎn)——2.3
2 被刪除結(jié)點(diǎn)兄弟節(jié)點(diǎn)是黑色：
2.1兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為紅色：兄弟黑，父親兄右紅+旋轉(zhuǎn)（唯一終態(tài)）
2.2兄弟節(jié)點(diǎn)的右子為黑色，但是左子為紅色：換色后旋轉(zhuǎn)——變?yōu)?.1
2.3兄弟節(jié)點(diǎn)雙子都是黑色：改色+父節(jié)點(diǎn)作為替換節(jié)點(diǎn)
優(yōu)勢：
平衡二叉樹的插入/刪除操作帶來的旋轉(zhuǎn)操作可能會(huì)達(dá)到logn次，而紅黑樹的插入/刪除操作帶來的旋轉(zhuǎn)操作最多為2/3次。

平衡二叉樹的刪除：

參考資料
左子樹上節(jié)點(diǎn)的刪除相當(dāng)于我們?cè)谟易訕渖喜迦肓艘粋€(gè)新節(jié)點(diǎn)，右子樹上節(jié)點(diǎn)的刪除相當(dāng)于在左子樹上插入了一個(gè)新節(jié)點(diǎn)
三種情況：
1：被刪節(jié)點(diǎn)為葉節(jié)點(diǎn)
2：被刪節(jié)點(diǎn)只一個(gè)葉節(jié)點(diǎn)
3：被刪節(jié)點(diǎn)有兩個(gè)葉子結(jié)點(diǎn)

LInkedHashMap：
HashMap和LinkedList的結(jié)合體，可以看到節(jié)點(diǎn)含有三個(gè)指針(鏈表)，四個(gè)指針(樹)

static class Entry<K,V> extends Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}

accessOrder兩種順序進(jìn)行存儲(chǔ)
一種是元素的插入順序，另一種便是元素的訪問順序（LRU緩存實(shí)現(xiàn)）
LRU的實(shí)現(xiàn)：最久未訪問元素
addBefore(lm.header)是把當(dāng)前訪問的元素挪到head的前面,即最近訪問的元素被放到了鏈表頭，如此要實(shí)現(xiàn)LRU算法只需要從鏈表末尾往前刪除就可以
而刪除如何實(shí)現(xiàn)的呢？

void addEntry(int hash, K key, V value, int bucketIndex) {super.addEntry(hash, key, value, bucketIndex);// Remove eldest entry if instructedEntry<K,V> eldest = header.after;if (removeEldestEntry(eldest)) {removeEntryForKey(eldest.key);}}

可以看到判斷removeEldestEntry(eldest)即是否需要?jiǎng)h除最晚元素
LinkedHashMap默認(rèn)的removeEldestEntry方法如下

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}

所以開發(fā)者需要實(shí)現(xiàn)LRU算法只需要繼承LinkedHashMap并重寫removeEldestEntry方法

內(nèi)部比較器和外部比較器：
參考資料
內(nèi)部：實(shí)現(xiàn)Comparable接口并重寫compareTo
外部：單獨(dú)定義一個(gè)類實(shí)現(xiàn)Comparator接口并重寫compare

TreeMap：底層架構(gòu)是紅黑樹
數(shù)據(jù)結(jié)構(gòu)是Entry，并沒有復(fù)用HashMap的TreeNode節(jié)省內(nèi)存？
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
}
比較是先進(jìn)行外部比較器的比較，再進(jìn)行內(nèi)部比較器的比較
如果沒有定義外部比較器，key=null則報(bào)錯(cuò)
如果沒有定義外部比較器，key也沒有實(shí)現(xiàn)Comparable接口，報(bào)
問題一：
基本數(shù)據(jù)結(jié)構(gòu)都實(shí)現(xiàn)了Comparable,但是如果是某個(gè)類，需要實(shí)現(xiàn)Comparable接口？
因?yàn)槠鋾?huì)調(diào)用compareTo的方法
問題二：如何實(shí)現(xiàn)一致性哈希
tailMap(K fromKey)方法，支持從紅黑樹中查找比fromKey大的值的集合，但并不需要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)
第一個(gè)順時(shí)針元素Integer i = subMap.firstKey();即是我們的存儲(chǔ)節(jié)點(diǎn)

我們只要把服務(wù)器的節(jié)點(diǎn)名字取hashCode（需要加虛擬節(jié)點(diǎn)，簡便實(shí)現(xiàn)方式為+i）put進(jìn)TreeMap中，之后對(duì)于查找的點(diǎn)調(diào)用tailMap/subMap.firstKey即可

LinkedListHashMap：結(jié)構(gòu)，實(shí)現(xiàn)LRU
TreeMap：比較器，實(shí)現(xiàn)一致性哈希

Queue

超級(jí)接口：
Queue 接口
Deque 雙端接口

ArrayQueue：普通隊(duì)列
參考資料
1：不可擴(kuò)容
2：循環(huán)隊(duì)列（數(shù)組）
一般來說，隊(duì)空隊(duì)滿head==tail的區(qū)分法有三種常用方法，但是ArrayQueue并沒有使用，而是利用this.capacity = capacity + 1;
當(dāng)add后if (newtail == head)表示此時(shí)已經(jīng)有 capacity + 1個(gè)元素，直接報(bào)錯(cuò) 不具有容錯(cuò)性，感覺不咋樣

public boolean add(T o) {queue[tail] = o;// 通過除余來實(shí)現(xiàn)下標(biāo)的循環(huán);int newtail = (tail + 1) % capacity;if (newtail == head)throw new IndexOutOfBoundsException("Queue full");tail = newtail;return true; // we did add something}public T remove(int i) {if (i != 0)throw new IllegalArgumentException("Can only remove head of queue");if (head == tail)throw new IndexOutOfBoundsException("Queue empty");T removed = queue[head];queue[head] = null;// 通過除余來實(shí)現(xiàn)下標(biāo)的循環(huán);head = (head + 1) % capacity;return removed;}

ArrayDeque：雙端隊(duì)列，實(shí)現(xiàn)了Deque超級(jí)接口
參考資料
1：可以擴(kuò)充，方式為2的次方容積和HashMap一致
區(qū)別在于如果輸入的大于1<<30，則返回1<<30 理解為10000–為-0，小于0

if (initialCapacity < 0) initialCapacity >>>= 1;

2：利用循環(huán)數(shù)組，且是雙端循環(huán)數(shù)組理解為兩個(gè)棧
開始的時(shí)候head=0,tail=0。當(dāng)要在head插入數(shù)值時(shí),是先移動(dòng)位置再賦值
步驟一：head = (head - 1)，此時(shí)head=-1，而負(fù)數(shù)是以偽碼形似存儲(chǔ)1111 1111 1111 1111 1111 1111 1111 1111
步驟二：1111 1111 1111 1111 1111 1111 1111 1111 & (elements.length - 1)
其實(shí)本質(zhì)就是對(duì)elements[elements.length - 1]=e
步驟三：當(dāng)再插入時(shí)，-2偽碼1111 1111 1111 1111 1111 1111 1111 1110
與之后相當(dāng)于elements[elements.length - 2]=e
可以看到實(shí)際就是上圖循環(huán)數(shù)組的龍尾部分

同理，我們可以對(duì)tail進(jìn)行分析,先賦值再移動(dòng)位置,實(shí)際上就是上圖的龍首部分

public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();

而當(dāng) if (head == tail)時(shí)，擴(kuò)充容newCapacity = n << 1
并將head之后的元素復(fù)制到新數(shù)組的開頭，把剩余的元素復(fù)制到新數(shù)組之后
原數(shù)組長度為n，(tail=head）——0為tail棧，（tail=head）——n-1為head棧。記head=tail=flag

新數(shù)組相當(dāng)于交叉原數(shù)組
新數(shù)組長度為2n，head=0——flag為head棧，tail——flag為tail棧

3：刪除元素。同樣分為pollFirst()和pollLast() 。并且實(shí)現(xiàn)了如棧操作：pop，push，peek，隊(duì)列操作：add，offer，remove，poll，peek，element，雙端隊(duì)列操作：addFirst，addLast，getFirst，getLast等方法，目的是模擬其他數(shù)據(jù)結(jié)構(gòu)

4：遍歷：可以看到從head開始遍歷到tail。沒有使用fast-fail機(jī)制，而是利用
if (tail != fence || result == null)，即判斷head和tail和記錄的有無更改和modCount一個(gè)思想

private class DeqIterator implements Iterator<E> {private int cursor = head;private int fence = tail;private int lastRet = -1;public boolean hasNext() {return cursor != fence;}public E next() {if (cursor == fence)throw new NoSuchElementException();@SuppressWarnings("unchecked")E result = (E) elements[cursor];if (tail != fence || result == null)throw new ConcurrentModificationException();lastRet = cursor;

PriorityQueue：
1：PriorityQueue是優(yōu)先級(jí)隊(duì)列，取出元素時(shí)會(huì)根據(jù)元素的優(yōu)先級(jí)進(jìn)行排序。其內(nèi)部內(nèi)部是一個(gè)用數(shù)組實(shí)現(xiàn)的小頂堆
2：使用場景：N取K，動(dòng)態(tài)插入含有優(yōu)先級(jí)的數(shù)組

private void grow(int minCapacity) {int oldCapacity = queue.length;// 如果當(dāng)前容量比較小（小于64）的話進(jìn)行雙倍擴(kuò)容，否則擴(kuò)容50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity +2) :(oldCapacity >> 1));// 如果發(fā)現(xiàn)擴(kuò)容后溢出了，則進(jìn)行調(diào)整if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}

Set

基本類
AbstractSet：提供 Set 接口的骨干實(shí)現(xiàn)，從而最大限度地減少了實(shí)現(xiàn)此接口所需的工作。實(shí)現(xiàn)了HashCode,equals,removeAll
SortedSet：按照對(duì)象的比較函數(shù)對(duì)元素排序
NavigableSet：接口繼承自SortedSet接口

引申類：
HashSet
通過內(nèi)部成員變量HashMap實(shí)現(xiàn)其功能
public Iterator iterator() {
return map.keySet().iterator();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
其中PRESENT是一個(gè)Object 對(duì)象

LinkedHashSet：擁有HashSet的功能，且能實(shí)現(xiàn)插入有序或者訪問有序。依靠成員變量LinkedHashMap實(shí)現(xiàn)
TreeSet:可自定義排序的Set
擁有成員變量NavigableMap
private transient NavigableMap<E,Object> m;
// map中共用的一個(gè)value
private static final Object PRESENT = new Object();

KeySet:HashMap的內(nèi)部類，繼承AbstractSet

總結(jié)

以上是生活随笔為你收集整理的Java基础知识——集合类的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。