首先，紅黑樹細節暫時擼不出來，所以沒寫，承諾年前一定寫

?

?

HashMap

（底層是數組+鏈表/紅黑樹，無序鍵值對集合，非線程安全）

基于哈希表實現，鏈地址法。

loadFactor默認為0.75，threshold（閾）為12，并創建一個大小為16的Entry數組。

在遍歷時是無序的，如需有序，建議使用TreeMap。

采用數組方式存儲key、value構成的Entry對象，無容量限制。

基于key hash尋找Entry對象存放在數組中的位置，對于hash沖突采用鏈表/紅黑樹的方式來解決。

HashMap在插入元素時可能會擴大數組的容量，在擴大容量時需要重新計算hash，并復制對象到新的數組中。

是非線程安全的。

// 1. 哈希沖突時采用鏈表法的類，一個哈希桶多于8個元素改為TreeNodestatic class Node<K,V> implements Map.Entry<K,V>// 2. 哈希沖突時采用紅黑樹存儲的類，一個哈希桶少于6個元素改為Nodestatic final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

?

某個桶對應的鏈表過長的話搜索效率低，改為紅黑樹效率會提高。

?

為何按位與而不是取摸 hashmap的iterator讀取時是否會讀到另一個線程put的數據

紅黑樹；hashmap報ConcurrentModificationException的情況

?

Hash沖突中鏈表結構的數量大于8個，則調用樹化轉為紅黑樹結構，紅黑樹查找稍微快些；紅黑樹結構的數量小于6個時，則轉為鏈表結構

如果加載因子越大，對空間的利用更充分，但是查找效率會降低（鏈表長度會越來越長）；如果加載因子太小，那么表中的數據將過于稀疏（很多空間還沒用，就開始擴容了），對空間造成嚴重浪費。如果我們在構造方法中不指定，則系統默認加載因子為0.75，這是一個比較理想的值，一般情況下我們是無需修改的。

一般對哈希表的散列很自然地會想到用hash值對length取模（即除法散列法），Hashtable中也是這樣實現的，這種方法基本能保證元素在哈希表中散列的比較均勻，但取模會用到除法運算，效率很低，HashMap中則通過h&(length-1)的方法來代替取模，同樣實現了均勻的散列，但效率要高很多，這也是HashMap對Hashtable的一個改進。

哈希表的容量一定要是2的整數次冪。首先，length為2的整數次冪的話，h&(length-1)就相當于對length取模，這樣便保證了散列的均勻，同時也提升了效率；其次，length為2的整數次冪的話，為偶數，這樣length-1為奇數，奇數的最后一位是1，這樣便保證了h&(length-1)的最后一位可能為0，也可能為1（這取決于h的值），即與后的結果可能為偶數，也可能為奇數，這樣便可以保證散列的均勻性，而如果length為奇數的話，很明顯length-1為偶數，它的最后一位是0，這樣h&(length-1)的最后一位肯定為0，即只能為偶數，這樣任何hash值都只會被散列到數組的偶數下標位置上，這便浪費了近一半的空間，因此，length取2的整數次冪，是為了使不同hash值發生碰撞的概率較小，這樣就能使元素在哈希表中均勻地散列。

（了解即可）成員變量

/*** The default initial capacity - MUST be a power of two.*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.*/
static final int MAXIMUM_CAPACITY = 1 << 30;/*** The load factor used when none specified in constructor.*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** The bin count threshold for using a tree rather than list for a* bin.? Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.*/
static final int TREEIFY_THRESHOLD = 8;/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*/
static final int UNTREEIFY_THRESHOLD = 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*/
static final int MIN_TREEIFY_CAPACITY = 64;/*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)*/
transient Node<K,V>[] table;/*** Holds cached entrySet(). Note that AbstractMap fields are used* for keySet() and values().*/
transient Set<Map.Entry<K,V>> entrySet;/*** The number of key-value mappings contained in this map.*/
transient int size;/*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash).? This field is used to make iterators on Collection-views of* the HashMap fail-fast.? (See ConcurrentModificationException).*/
transient int modCount;/*** The next size value at which to resize (capacity * load factor).** @serial*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)// HashMap的閾值，用于判斷是否需要調整HashMap的容量（threshold = 容量*裝載因子）
int threshold;/*** The load factor for the hash table.** @serial*/
final float loadFactor;

構造方法

注意哪怕是指定了初始容量，也不會直接初始化table，而是在第一次put時調用resize來初始化table，resize里會將threshold視為初始容量。

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;// 閾值為不小于容量的2的冪次this.threshold = tableSizeFor(initialCapacity);
}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/*** Constructs an empty <tt>HashMap</tt> with the default initial capacity* (16) and the default load factor (0.75).*/
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

?

tableSizeFor（找到大于等于initialCapacity的最小的2的冪次以及原因）

/*** Returns a power of two size for the given target capacity.*/
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;
}

hash（hash算法，算法比較高效、均勻）

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

key的hash值高16位不變，低16位與高16位異或作為key的最終hash值。（h >>> 16，表示無符號右移16位，高位補0，任何數跟0異或都是其本身，因此key的hash值高16位不變。）

保證了對象的hashCode的高16位的變化能反應到低16位中，

hash to index

如何根據hash值計算index？（put和get中的代碼）

n = table.length;

index = (n-1)& hash;

當n總是2的n次方時，hash & (n-1)運算等價于h%n，但是&比%具有更高的效率。

put

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// onlyIfAbsent如果為true，只有在hashmap沒有該key的時候才添加// evict如果為false，hashmap為創建模式；只有在使用Map集合作為構造器創建LinkedHashMap或HashMap時才會為false。// 這兩個參數均為實現java8的新接口而設置Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; // tableNode<K,V> p;? // node pointerint n, i; // n 為length, i 為 node indexif ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// index處沒有元素，則直接放入新節點if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// index處有元素Node<K,V> e;K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 假如key是相同的，那么替換value即可e = p;else if (p instanceof TreeNode)// key不同，但如果p是紅黑樹根節點，那么將新節點放入紅黑樹e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// key不同，但如果p是鏈表頭節點，那么判斷鏈表中是否有該節點，如沒有，則將新節點插入到鏈表尾部for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 插入后如果發現已經鏈表長度已經適合轉為紅黑樹了，則轉換if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 鏈表中某元素key和key相同，則替換value即可if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

擴容 resize

// 擴容函數，如果hash桶為空，初始化默認大小，否則雙倍擴容// 注意！！因為擴容為2的倍數，根據hash桶的計算方法，元素哈希值不變// 所以元素在新的hash桶的下標，要不跟舊的hash桶下標一致，要不增加1倍。cap：capacitythr：thresholdfinal Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {?????????????? // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {// j位置原本元素存在oldTab[j] = null;if (e.next == null)// 如果該位置沒有形成鏈表，則再次計算index，放入新table// 假設擴容前的table大小為2的N次方，有上述put方法解析可知，元素的table索引為其hash值的后N位確定那么擴容后的table大小即為2的N+1次方，則其中元素的table索引為其hash值的后N+1位確定，比原來多了一位因此，table中的元素只有兩種情況：元素hash值第N+1位為0：不需要進行位置調整元素hash值第N+1位為1：調整至原索引的兩倍位置newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 如果該位置形成了紅黑樹，則split((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order// 如果該位置形成了鏈表，則分成兩個鏈表，分別放在0~oldCap,oldCap~oldCap*2位置處Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 用于確定元素hash值第N+1位是否為0：若為0，則使用loHead與loTail，將元素移至新table的原索引處若不為0，則使用hiHead與hiHead，將元素移至新table的兩倍索引處if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

get（O(logn)）

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// table不為空，且hash對應index元素不為空// 如果index位置就是我們要找的key，則直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 如果不是，則從鏈表或紅黑樹的角度繼續找if ((e = first.next) != null) {if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

remove

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}value=null,matchValue=false,movable=truefinal Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// 1) 如果hash 對應index即為我們要找的key，則找到if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;// 2) 從鏈表或紅黑樹的角度繼續找else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// 找到后，根據找到的位置不同 相應地進行刪除if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

containsKey

public boolean containsKey(Object key) {return getNode(hash(key), key) != null;
}

?

containsValue

public boolean containsValue(Object value) {Node<K,V>[] tab; V v;if ((tab = table) != null && size > 0) {for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next) {if ((v = e.value) == value ||(value != null && value.equals(v)))return true;}}}return false;
}

a）鏈表轉紅黑樹 treeifyBin

/*** Replaces all linked nodes in bin at index for given hash unless* table is too small, in which case resizes instead.*/
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}
}

b）紅黑樹轉鏈表 TreeNode#untreeify

final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;
}

LinkedHashMap

（底層是(數組+鏈表/紅黑樹)+環形雙向鏈表，繼承自HashMap）

LinkedHashMap是key鍵有序的HashMap的一種實現。它除了使用哈希表這個數據結構，使用環形雙向鏈表來保證key的順序。

HashMap是無序的，也就是說，迭代HashMap所得到的元素順序并不是它們最初放置到HashMap的順序。HashMap的這一缺點往往會造成諸多不便，因為在有些場景中，我們確需要用到一個可以保持插入順序的Map。慶幸的是，JDK為我們解決了這個問題，它為HashMap提供了一個子類 —— LinkedHashMap。雖然LinkedHashMap增加了時間和空間上的開銷，但是它通過維護一個額外的雙向鏈表保證了迭代順序。特別地，該迭代順序可以是插入順序，也可以是訪問順序。因此，根據鏈表中元素的順序可以將LinkedHashMap分為：保持插入順序的LinkedHashMap 和 保持訪問順序（LRU，get后調整鏈表序，最新獲取的放在最后）的LinkedHashMap，其中LinkedHashMap的默認實現是按插入順序排序的。

特點：

一般來說，如果需要使用的Map中的key無序，選擇HashMap；如果要求key有序，則選擇TreeMap。

但是選擇TreeMap就會有性能問題，因為TreeMap的get操作的時間復雜度是O(log(n))的，相比于HashMap的O(1)還是差不少的，LinkedHashMap的出現就是為了平衡這些因素，使得能夠以O(1)時間復雜度增加查找元素，又能夠保證key的有序性

實現原理：

將所有Entry節點鏈入一個雙向鏈表的HashMap。在LinkedHashMap中，所有put進來的Entry都保存在哈希表中，但由于它又額外定義了一個以head為頭結點的雙向鏈表，因此對于每次put進來Entry，除了將其保存到哈希表上外，還會將其插入到雙向鏈表的尾部。

LinkedHashMap#Entry

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

put

同HashMap，但重寫了afterNodeInsertion。

void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
}//可以自行重寫該方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;
}public class LRUHashMap<K, V> extends LinkedHashMap<K, V>{private final int MAX_CACHE_SIZE;public BaseLRUCache(int cacheSize) {super(cacheSize, 0.75f, true);MAX_CACHE_SIZE = cacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > MAX_CACHE_SIZE;}
}

remove

同HashMap，但重寫了afterNodeRemoval。

void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;
}

?get

public V get(Object key) {Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;if (accessOrder)afterNodeAccess(e);return e.value;
}void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
}

遍歷（迭代環形雙向鏈表）

..........

TreeMap

（底層是紅黑樹）

支持排序的Map實現。

基于紅黑樹實現，無容量限制。

是非線程安全的。

?

TreeMap是根據key進行排序的，它的排序和定位需要依賴比較器或覆寫Comparable接口，也因此不需要key覆寫hashCode方法和equals方法，就可以排除掉重復的key，而HashMap的key則需要通過覆寫hashCode方法和equals方法來確保沒有重復的key

TreeMap的查詢、插入、刪除效率均沒有HashMap高，一般只有要對key排序時才使用TreeMap。

TreeMap的key不能為null，而HashMap的key可以為null。

?

?

?

Fail-Fast

在ArrayList,LinkedList,HashMap等等的內部實現增，刪，改中我們總能看到modCount的身影，modCount字面意思就是修改次數，但為什么要記錄modCount的修改次數呢？

所有使用modCount屬性集合的都是線程不安全的。

在一個迭代器初始的時候會賦予它調用這個迭代器的對象的modCount，在迭代器遍歷的過程中，一旦發現這個對象的modCount和迭代器中存儲的modCount不一樣那就拋異常。

?

它是 java 集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變的操作時，有可能會產生 fail-fast。

?

例如 ：假設存在兩個線程（線程 1、線程 2），線程 1 通過 Iterator 在遍歷集合 A 中的元素，在某個時候線程 2 修改了集合 A 的結構（是結構上面的修改，而不是簡單的修改集合元素的內容），那么這個時候程序就會拋出 ConcurrentModificationException 異常，從而產生 fail-fast 機制。

?

原因： 迭代器在遍歷時直接訪問集合中的內容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內容發生變化，就會改變 modCount 的值。

?

每當迭代器使用 hashNext()/next() 遍歷下一個元素之前，都會檢測 modCount 變量是否為 expectedmodCount 值，是的話就返回遍歷；否則拋出異常，終止遍歷。

?

解決辦法：使用線程安全的集合