13-Java集合框架之HashMap詳解
文章目錄
1.HashMap是什麼?
概念:
基於哈希表(jdk1.8加入了紅黑樹)的 Map 接口的實現。HashMap 最先出如今 JDK 1.2中，底層基於散列算法實現。此實現提供全部可選的映射操做，並容許使用 null 值和 null 鍵。（除了非同步和容許使用 null 以外，HashMap 類與 Hashtable 大體相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。 此實現假定哈希函數將元素適當地分佈在各桶之間，可爲基本操做（get 和 put）提供穩定的性能。迭代 collection 視圖所需的時間與 HashMap 實例的「容量」（桶的數量）及其大小（鍵-值映射關係數）成比例。因此，若是迭代性能很重要，則不要將初始容量設置得過高（或將加載因子設置得過低）。另外，須要注意的是，HashMap 是非線程安全類，在多線程環境下可能會存在問題。node
重要參數
HashMap 的實例有兩個參數影響其性能：初始容量 和加載因子。容量是哈希表中桶的數量，初始容量只是哈希表在建立時的容量。加載因子 是哈希表在其容量自動增長以前能夠達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行 rehash 操做（即重建內部數據結構），從而哈希表將具備大約兩倍的桶數。在Java編程語言中，加載因子默認值爲0.75，默認哈希表元爲101。web
2.HashMap怎麼實現的?
從概念咱們知道了HashMap 底層是基於散列算法實現，散列算法分爲散列再探測和拉鍊式。HashMap 則使用了拉鍊式的散列算法，並在 JDK 1.8 中引入了紅黑樹優化過長的鏈表。數據結構示意圖以下：算法
對於拉鍊式的散列算法，其數據結構是由數組和鏈表（或樹形結構）組成。在進行增刪查等操做時，首先要定位到元素的所在桶的位置，以後再從鏈表中定位該元素。好比咱們要查詢上圖結構中是否包含元素35，步驟以下：編程
定位元素35所處桶的位置，index = 35 % 16 = 3
在3號桶所指向的鏈表中繼續查找，發現35在鏈表中。
上面就是 HashMap 底層數據結構的原理，HashMap 基本操做就是對拉鍊式散列算法基本操做的一層包裝。不一樣的地方在於 JDK 1.8 中引入了紅黑樹，底層數據結構由數組+鏈表變爲了數組+鏈表+紅黑樹，不過本質並未變。好了，原理部分先講到這，接下來講說源碼實現。數組
3.源碼分析
本篇文章所分析的源碼版本爲 JDK 1.8。與 JDK 1.7 相比，JDK 1.8 對 HashMap 進行了一些優化。好比引入紅黑樹解決過長鏈表效率低的問題。重寫 resize 方法，移除了 alternative hashing 相關方法，避免從新計算鍵的 hash 等。不過本篇文章並不打算對這些優化進行分析，本文僅會分析 HashMap 經常使用的方法及一些重要屬性和相關方法。緩存
3.1 構造方法
3.1.1 構造方法分析
HashMap 的構造方法很少，只有四個。HashMap 構造方法作的事情比較簡單，通常都是初始化一些重要變量，好比 loadFactor 和 threshold。而底層的數據結構則是延遲到插入鍵值對時再進行初始化。HashMap 相關構造方法以下：安全
/** 構造方法 1 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 構造方法 2 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 構造方法 3 */
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);
}
/** 構造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
上面4個構造方法中，你們平時用的最多的應該是第一個了。第一個構造方法很簡單，僅將 loadFactor 變量設爲默認值。構造方法2調用了構造方法3，而構造方法3仍然只是設置了一些變量。構造方法4則是將另外一個 Map 中的映射拷貝一份到本身的存儲結構中來，這個方法不是很經常使用。數據結構
上面就是對構造方法簡單的介紹，構造方法自己並沒什麼太多東西，因此就不說了。接下來講說構造方法所初始化的幾個的變量。多線程
3.1.2 初始容量、負載因子、閾值
咱們在通常狀況下，都會使用無參構造方法建立 HashMap。但當咱們對時間和空間複雜度有要求的時候，使用默認值有時可能達不到咱們的要求，這個時候咱們就須要手動調參。在 HashMap 構造方法中，可供咱們調整的參數有兩個，一個是初始容量 initialCapacity，另外一個負載因子 loadFactor。經過這兩個設定這兩個參數，能夠進一步影響閾值大小。但初始閾值 threshold 僅由 initialCapacity 通過移位操做計算得出。他們的做用分別以下：併發
| 名稱 | 用途 | 注意點 |
|---|---|---|
| initialCapacity | HashMap 初始容量 | 設置的數不能是小於0的數,否則會拋出IllegalArgumentException異常!設置的數不能大於MAXIMUM_CAPACITY(1 << 30 也就是1073741824),若是超過這個數會默認設置爲1073741824 |
| loadFactor | 負載因子 | 設置的數不能小於等於0,或者NAN,否則會拋出IllegalArgumentException異常! |
| threshold | 當前 HashMap 所能容納鍵值對數量的最大值，超過這個值，則需擴容 | 冪等和capacity * load factor的理解 |
相關代碼以下：
/** The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; /** The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; final float loadFactor; /** The next size value at which to resize (capacity * load factor). */ int threshold;
若是你們去看源碼，會發現 HashMap 中沒有定義 initialCapacity 這個變量。這個也並不難理解，從參數名上可看出，這個變量表示一個初始容量，只是構造方法中用一次，不必定義一個變量保存。但若是你們仔細看上面 HashMap 的構造方法，會發現存儲鍵值對的數據結構並非在構造方法裏初始化的。這就有個疑問了，既然叫初始容量，但最終並無用與初始化數據結構，那傳這個參數還有什麼用呢？這個問題我先不解釋，給你們留個懸念，後面會說明。
默認狀況下，HashMap 初始容量是16，負載因子爲 0.75。這裏並無默認閾值，緣由是閾值可由容量乘上負載因子計算而來（註釋中有說明），即threshold = capacity * loadFactor。但當你仔細看構造方法3時，會發現閾值並非由上面公式計算而來，而是經過一個方法算出來的。這是否是能夠說明 threshold 變量的註釋有誤呢？仍是僅這裏進行了特殊處理，其餘地方遵循計算公式呢？關於這個疑問，這裏也先不說明，後面在分析擴容方法時，再來解釋這個問題。接下來，咱們來看看初始化 threshold 的方法長什麼樣的的，源碼以下：
/**
* 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;
}
上面的代碼長的有點不太好看，反正我第一次看的時候不明白它想幹啥。不事後來在紙上畫畫，知道了它的用途。總結起來就一句話：找到大於或等於 cap 的最小2的冪。至於爲啥要這樣，後面再解釋。咱們先來看看 tableSizeFor 方法的圖解：
上面是 tableSizeFor 方法的計算過程圖，這裏cap = 536,870,913 = 229 + 1，屢次計算後，算出n + 1 = 1,073,741,824 = 230。經過圖解應該能夠比較容易理解這個方法的用途，這裏就很少說了。
說完了初始閾值的計算過程，再來講說負載因子（loadFactor）。對於 HashMap 來講，負載因子是一個很重要的參數，該參數反應了 HashMap 桶數組的使用狀況（假設鍵值對節點均勻分佈在桶數組中）。經過調節負載因子，可以使 HashMap 時間和空間複雜度上有不一樣的表現。當咱們調低負載因子時，HashMap 所能容納的鍵值對數量變少。擴容時，從新將鍵值對存儲新的桶數組裏，鍵的鍵之間產生的碰撞會降低，鏈表長度變短。此時，HashMap 的增刪改查等操做的效率將會變高，這裏是典型的拿空間換時間。相反，若是增長負載因子（負載因子能夠大於1），HashMap 所能容納的鍵值對數量變多，空間利用率高，但碰撞率也高。這意味着鏈表長度變長，效率也隨之下降，這種狀況是拿時間換空間。至於負載因子怎麼調節，這個看使用場景了。通常狀況下，咱們用默認值就能夠了。
3.2 查找
HashMap 的查找操做比較簡單，查找步驟與原理篇介紹一致，即先定位鍵值對所在的桶的位置，而後再對鏈表或紅黑樹進行查找。經過這兩步便可完成查找，該操做相關代碼以下：
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;
// 1. 定位鍵值對所在桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 2. 若是 first 是 TreeNode 類型，則調用黑紅樹查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 2. 對鏈表進行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
查找的核心邏輯是封裝在 getNode 方法中的，getNode 方法源碼我已經寫了一些註釋，應該不難看懂。咱們先來看看查找過程的第一步 - 肯定桶位置，其實現代碼以下：
// index = (n - 1) & hash first = tab[(n - 1) & hash]
這裏經過(n - 1)& hash便可算出桶的在桶數組中的位置，可能有的朋友不太明白這裏爲何這麼作，這裏簡單解釋一下。HashMap 中桶數組的大小 length 老是2的冪，此時，(n - 1) & hash 等價於對 length 取餘。但取餘的計算效率沒有位運算高，因此(n - 1) & hash也是一個小的優化。舉個例子說明一下吧，假設 hash = 185，n = 16。計算過程示意圖以下：
上面的計算並不複雜，這裏就很少說了。
在上面源碼中，除了查找相關邏輯，還有一個計算 hash 的方法。這個方法源碼以下：
/**
* 計算鍵的 hash 值
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看這個方法的邏輯好像是經過位運算從新計算 hash，那麼這裏爲何要這樣作呢？爲何不直接用鍵的 hashCode 方法產生的 hash 呢？你們先能夠思考一下，我把答案寫在下面。
這樣作有兩個好處，我來簡單解釋一下。咱們再看一下上面求餘的計算圖，圖中的 hash 是由鍵的 hashCode 產生。計算餘數時，因爲 n 比較小，hash 只有低4位參與了計算，高位的計算能夠認爲是無效的。這樣致使了計算結果只與低位信息有關，高位數據沒發揮做用。爲了處理這個缺陷，咱們能夠上圖中的 hash 高4位數據與低4位數據進行異或運算，即 hash ^ (hash >>> 4)。經過這種方式，讓高位數據與低位數據進行異或，以此加大低位信息的隨機性，變相的讓高位數據參與到計算中。此時的計算過程以下：
在 Java 中，hashCode 方法產生的 hash 是 int 類型，32 位寬。前16位爲高位，後16位爲低位，因此要右移16位。
上面所說的是從新計算 hash 的一個好處，除此以外，從新計算 hash 的另外一個好處是能夠增長 hash 的複雜度。當咱們覆寫 hashCode 方法時，可能會寫出分佈性不佳的 hashCode 方法，進而致使 hash 的衝突率比較高。經過移位和異或運算，可讓 hash 變得更復雜，進而影響 hash 的分佈性。這也就是爲何 HashMap 不直接使用鍵對象原始 hash 的緣由了。
3.3 遍歷
和查找查找同樣，遍歷操做也是你們使用頻率比較高的一個操做。對於 遍歷 HashMap，咱們通常都會用下面的方式：
for(Object key : map.keySet()) {
// do something
}
或
for(HashMap.Entry entry : map.entrySet()) {
// do something
}
從上面代碼片斷中能夠看出，你們通常都是對 HashMap 的 key 集合或 Entry 集合進行遍歷。上面代碼片斷中用 foreach 遍歷 keySet 方法產生的集合，在編譯時會轉換成用迭代器遍歷，等價於：
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
你們在遍歷 HashMap 的過程當中會發現，屢次對 HashMap 進行遍歷時，遍歷結果順序都是一致的。但這個順序和插入的順序通常都是不一致的。產生上述行爲的緣由是怎樣的呢？你們想一下緣由。我先把遍歷相關的代碼貼出來，以下：
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
/**
* 鍵集合
*/
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
// 省略部分代碼
}
/**
* 鍵迭代器
*/
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 尋找第一個包含鏈表節點引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
// 尋找下一個包含鏈表節點引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//省略部分代碼
}
如上面的源碼，遍歷全部的鍵時，首先要獲取鍵集合KeySet對象，而後再經過 KeySet 的迭代器KeyIterator進行遍歷。KeyIterator 類繼承自HashIterator類，核心邏輯也封裝在 HashIterator 類中。HashIterator 的邏輯並不複雜，在初始化時，HashIterator 先從桶數組中找到包含鏈表節點引用的桶。而後對這個桶指向的鏈表進行遍歷。遍歷完成後，再繼續尋找下一個包含鏈表節點引用的桶，找到繼續遍歷。找不到，則結束遍歷。舉個例子，假設咱們遍歷下圖的結構：
HashIterator 在初始化時，會先遍歷桶數組，找到包含鏈表節點引用的桶，對應圖中就是3號桶。隨後由 nextNode 方法遍歷該桶所指向的鏈表。遍歷完3號桶後，nextNode 方法繼續尋找下一個不爲空的桶，對應圖中的7號桶。以後流程和上面相似，直至遍歷完最後一個桶。以上就是 HashIterator 的核心邏輯的流程，對應下圖：
遍歷上圖的最終結果是 19 -> 3 -> 35 -> 7 -> 11 -> 43 -> 59，爲了驗證正確性，簡單寫點測試代碼跑一下看看。測試代碼以下：
/**
* 應在 JDK 1.8 下測試，其餘環境下不保證結果和上面一致
*/
public class HashMapTest {
@Test
public void testTraversal() {
HashMap<Integer, String> map = new HashMap(16);
map.put(7, "");
map.put(11, "");
map.put(43, "");
map.put(59, "");
map.put(19, "");
map.put(3, "");
map.put(35, "");
System.out.println("遍歷結果：");
for (Integer key : map.keySet()) {
System.out.print(key + " -> ");
}
}
}
遍歷結果以下：
遍歷結果: 19 -> 3 -> 35 -> 7 -> 11 -> 43 -> 59 ->
在本小節的最後，拋兩個問題給你們。在 JDK 1.8 版本中，爲了不過長的鏈表對 HashMap 性能的影響，特意引入了紅黑樹優化性能。但在上面的源碼中並無發現紅黑樹遍歷的相關邏輯，這是爲何呢？對於被轉換成紅黑樹的鏈表該如何遍歷呢？你們能夠先想一想，而後能夠去源碼或本文後續章節中找答案。
3.4 插入
3.4.1 插入邏輯分析
經過前兩節的分析，你們對 HashMap 低層的數據結構應該瞭然於心了。即便我不說，你們也應該能知道 HashMap 的插入流程是什麼樣的了。首先確定是先定位要插入的鍵值對屬於哪一個桶，定位到桶後，再判斷桶是否爲空。若是爲空，則將鍵值對存入便可。若是不爲空，則需將鍵值對接在鏈表最後一個位置，或者更新鍵值對。這就是 HashMap 的插入流程，是否是以爲很簡單。固然，你們先別高興。這只是一個簡化版的插入流程，真正的插入流程要複雜很多。首先 HashMap 是變長集合，因此須要考慮擴容的問題。其次，在 JDK 1.8 中，HashMap 引入了紅黑樹優化過長鏈表，這裏還要考慮多長的鏈表須要進行優化，優化過程又是怎樣的問題。引入這裏兩個問題後，你們會發現本來簡單的操做，如今略顯複雜了。在本節中，我將先分析插入操做的源碼，擴容、樹化（鏈表轉爲紅黑樹，下同）以及其餘和樹結構相關的操做，隨後將在獨立的兩小結中進行分析。接下來，先來看一下插入操做的源碼：
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶數組 table，table 被延遲到插入新數據時再進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 若是桶中不包含鍵值對節點引用，則將新鍵值對節點的引用存入桶中便可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 若是鍵的值以及節點 hash 等於鏈表中的第一個鍵值對節點時，則將 e 指向該鍵值對
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 若是桶中的引用類型爲 TreeNode，則調用紅黑樹的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 對鏈表進行遍歷，並統計鏈表長度
for (int binCount = 0; ; ++binCount) {
// 鏈表中不包含要插入的鍵值對節點時，則將該節點接在鏈表的最後
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 若是鏈表長度大於或等於樹化閾值，則進行樹化操做
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 條件爲 true，表示當前鏈表包含要插入的鍵值對，終止遍歷
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判斷要插入的鍵值對是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 爲 null 的狀況下更新鍵值對的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 鍵值對數量超過閾值時，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
插入操做的入口方法是 put(K,V)，但核心邏輯在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要作了這麼幾件事情：
當桶數組 table 爲空時，經過擴容的方式初始化 table
查找要插入的鍵值對是否已經存在，存在的話根據條件判斷是否用新值替換舊值
若是不存在，則將鍵值對鏈入鏈表中，並根據鏈表長度決定是否將鏈表轉爲紅黑樹
判斷鍵值對數量是否大於閾值，大於的話則進行擴容操做
以上就是 HashMap 插入的邏輯，並非很複雜，這裏就很少說了。接下來來分析一下擴容機制。
3.4.2 擴容機制
在 Java 中，數組的長度是固定的，這意味着數組只能存儲固定量的數據。但在開發的過程當中，不少時候咱們沒法知道該建多大的數組合適。建小了不夠用，建大了用不完，形成浪費。若是咱們能實現一種變長的數組，並按需分配空間就行了。好在，咱們不用本身實現變長數組，Java 集合框架已經實現了變長的數據結構。好比 ArrayList 和 HashMap。對於這類基於數組的變長數據結構，擴容是一個很是重要的操做。下面就來聊聊 HashMap 的擴容機制。
在詳細分析以前，先來講一下擴容相關的背景知識：
在 HashMap 中，桶數組的長度均是2的冪，閾值大小爲桶數組長度與負載因子的乘積。當 HashMap 中的鍵值對數量超過閾值時，進行擴容。
HashMap 的擴容機制與其餘變長集合的套路不太同樣，HashMap 按當前桶數組長度的2倍進行擴容，閾值也變爲原來的2倍（若是計算過程當中，閾值溢出歸零，則按閾值公式從新計算）。擴容以後，要從新計算鍵值對的位置，並把它們移動到合適的位置上去。以上就是 HashMap 的擴容大體過程，接下來咱們來看看具體的實現：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 若是 table 不爲空，代表已經初始化過了
if (oldCap > 0) {
// 當 table 容量超過容量最大值，則再也不擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按舊容量和閾值的2倍計算新容量和閾值的大小
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 threshold
/*
* 初始化時，將 threshold 的值賦值給 newCap，
* HashMap 使用 threshold 變量暫時保存 initialCapacity 參數的值
*/
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/*
* 調用無參構造方法時，桶數組容量爲默認容量，
* 閾值爲默認容量與默認負載因子乘積
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 爲 0 時，按閾值計算公式進行計算
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) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 從新映射時，須要對紅黑樹進行拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷鏈表，並將鏈表節點按原順序進行分組
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}
上面的源碼有點長，但願你們耐心看懂它的邏輯。上面的源碼總共作了3件事，分別是：
計算新桶數組的容量 newCap 和新閾值 newThr
根據計算出的 newCap 建立新的桶數組，桶數組 table 也是在這裏進行初始化的
將鍵值對節點從新映射到新的桶數組裏。若是節點是 TreeNode 類型，則須要拆分成黑樹。若是是普通節點，則節點按原順序進行分組。
上面列的三點中，建立新的桶數組就一行代碼，不用說了。接下來，來講說第一點和第三點，先說說 newCap 和 newThr 計算過程。該計算過程對應 resize 源碼的第一和第二個條件分支，以下：
// 第一個條件分支
if ( oldCap > 0) {
// 嵌套條件分支
if (oldCap >= MAXIMUM_CAPACITY) {...}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
}
else if (oldThr > 0) {...}
else {...}
// 第二個條件分支
if (newThr == 0) {...}
經過這兩個條件分支對不一樣狀況進行判斷，進而算出不一樣的容量值和閾值。它們所覆蓋的狀況以下：
分支一：
| 條件 | 覆蓋狀況 | 備註 |
|---|---|---|
| oldCap > 0 | 桶數組 table 已經被初始化 | |
| oldThr > 0 | threshold > 0，且桶數組未被初始化 | 調用 HashMap(int) 和 HashMap(int, float) 構造方法時會產生這種狀況，此種狀況下 newCap = oldThr，newThr 在第二個條件分支中算出 |
| oldCap == 0 && oldThr == 0 | 桶數組未被初始化，且 threshold 爲 0 | 調用 HashMap() 構造方法會產生這種狀況。 |
這裏把oldThr > 0狀況單獨拿出來講一下。在這種狀況下，會將 oldThr 賦值給 newCap，等價於newCap = threshold = tableSizeFor(initialCapacity)。咱們在初始化時傳入的 initialCapacity 參數通過 threshold 中轉最終賦值給了 newCap。這也就解答了前面提的一個疑問：initialCapacity 參數沒有被保存下來，那麼它怎麼參與桶數組的初始化過程的呢？
嵌套分支：
| 條件 | 覆蓋狀況 | 備註 |
|---|---|---|
| oldCap >= 230 | 桶數組容量大於或等於最大桶容量 230 | 這種狀況下再也不擴容 |
| newCap < 230 && oldCap > 16 | 新桶數組容量小於最大值，且舊桶數組容量大於 16 | 該種狀況下新閾值 newThr = oldThr << 1，移位可能會致使溢出 |
這裏簡單說明一下移位致使的溢出狀況，當 loadFactor小數位爲 0，整數位可被2整除且大於等於8時，在某次計算中就可能會致使 newThr 溢出歸零。見下圖：
分支二：
| 條件 | 覆蓋狀況 | 備註 |
|---|---|---|
| newThr == 0 | 第一個條件分支未計算 newThr 或嵌套分支在計算過程當中致使 newThr 溢出歸零 |
說完 newCap 和 newThr 的計算過程，接下來再來分析一下鍵值對節點從新映射的過程。
在 JDK 1.8 中，從新映射節點須要考慮節點類型。對於樹形節點，需先拆分成黑樹再映射。對於鏈表類型節點，則需先對鏈表進行分組，而後再映射。須要的注意的是，分組後，組內節點相對位置保持不變。關於紅黑樹拆分的邏輯將會放在下一小節說明，先來看看鏈表是怎樣進行分組映射的。
咱們都知道往底層數據結構中插入節點時，通常都是先經過模運算計算桶位置，接着把節點放入桶中便可。事實上，咱們能夠把從新映射看作插入操做。在 JDK 1.7 中，也確實是這樣作的。但在 JDK 1.8 中，則對這個過程進行了必定的優化，邏輯上要稍微複雜一些。在詳細分析前，咱們先來回顧一下 hash 求餘的過程：
上圖中，桶數組大小 n = 16，hash1 與 hash2 不相等。但由於只有後4位參與求餘，因此結果相等。當桶數組擴容後，n 由16變成了32，對上面的 hash 值從新進行映射：
擴容後，參與模運算的位數由4位變爲了5位。因爲兩個 hash 第5位的值是不同，因此兩個 hash 算出的結果也不同。上面的計算過程並不難理解，繼續往下分析。
假設咱們上圖的桶數組進行擴容，擴容後容量 n = 16，從新映射過程以下:
依次遍歷鏈表，並計算節點 hash & oldCap 的值。以下圖所示
若是值爲0，將 loHead 和 loTail 指向這個節點。若是後面還有節點 hash & oldCap 爲0的話，則將節點鏈入 loHead 指向的鏈表中，並將 loTail 指向該節點。若是值爲非0的話，則讓 hiHead 和 hiTail 指向該節點。完成遍歷後，可能會獲得兩條鏈表，此時就完成了鏈表分組：
最後再將這兩條連接存放到相應的桶中，完成擴容。以下圖：
從上圖能夠發現，從新映射後，兩條鏈表中的節點順序並未發生變化，仍是保持了擴容前的順序。以上就是 JDK 1.8 中 HashMap 擴容的代碼講解。另外再補充一下，JDK 1.8 版本下 HashMap 擴容效率要高於以前版本。若是你們看過 JDK 1.7 的源碼會發現，JDK 1.7 爲了防止因 hash 碰撞引起的拒絕服務攻擊，在計算 hash 過程當中引入隨機種子。以加強 hash 的隨機性，使得鍵值對均勻分佈在桶數組中。在擴容過程當中，相關方法會根據容量判斷是否須要生成新的隨機種子，並從新計算全部節點的 hash。而在 JDK 1.8 中，則經過引入紅黑樹替代了該種方式。從而避免了屢次計算 hash 的操做，提升了擴容效率。
本小節的內容講就先講到這，接下來，來說講鏈表與紅黑樹相互轉換的過程。
3.4.3 鏈表樹化、紅黑樹鏈化與拆分
JDK 1.8 對 HashMap 實現進行了改進。最大的改進莫過於在引入了紅黑樹處理頻繁的碰撞，代碼複雜度也隨之上升。好比，之前只需實現一套針對鏈表操做的方法便可。而引入紅黑樹後，須要另外實現紅黑樹相關的操做。紅黑樹是一種自平衡的二叉查找樹，自己就比較複雜。本篇文章中並不打算對紅黑樹展開介紹，本文僅會介紹鏈表樹化須要注意的地方。
在展開說明以前，先把樹化的相關代碼貼出來，以下：
static final int TREEIFY_THRESHOLD = 8;
/**
* 當桶數組容量小於該值時，優先進行擴容，而不是樹化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
/**
* 將普通節點鏈表轉換成樹形節點鏈表
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 桶數組容量小於 MIN_TREEIFY_CAPACITY，優先進行擴容而不是樹化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd 爲頭節點（head），tl 爲尾節點（tail）
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);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
在擴容過程當中，樹化要知足兩個條件：
1.鏈表長度大於等於 TREEIFY_THRESHOLD
2.桶數組容量大於等於 MIN_TREEIFY_CAPACITY
第一個條件比較好理解，這裏就不說了。這裏來講說加入第二個條件的緣由，我的以爲緣由以下：
當桶數組容量比較小時，鍵值對節點 hash 的碰撞率可能會比較高，進而致使鏈表長度較長。這個時候應該優先擴容，而不是立馬樹化。畢竟高碰撞率是由於桶數組容量較小引發的，這個是主因。容量小時，優先擴容能夠避免一些列的沒必要要的樹化過程。同時，桶容量較小時，擴容會比較頻繁，擴容時須要拆分成黑樹並從新映射。因此在桶容量比較小的狀況下，將長鏈表轉成紅黑樹是一件吃力不討好的事。
回到上面的源碼中，咱們繼續看一下 treeifyBin 方法。該方法主要的做用是將普通鏈表轉成爲由 TreeNode 型節點組成的鏈表，並在最後調用 treeify 是將該鏈表轉爲紅黑樹。TreeNode 繼承自 Node 類，因此 TreeNode 仍然包含 next 引用，原鏈表的節點順序最終經過 next 引用被保存下來。咱們假設樹化前，鏈表結構以下：
HashMap 在設計之初，並無考慮到之後會引入紅黑樹進行優化。因此並無像 TreeMap 那樣，要求鍵類實現 comparable 接口或提供相應的比較器。但因爲樹化過程須要比較兩個鍵對象的大小，在鍵類沒有實現 comparable 接口的狀況下，怎麼比較鍵與鍵之間的大小了就成了一個棘手的問題。爲了解決這個問題，HashMap 是作了三步處理，確保能夠比較出兩個鍵的大小，以下：
1.比較鍵與鍵之間 hash 的大小，若是 hash 相同，繼續往下比較
2.檢測鍵類是否實現了 Comparable 接口，若是實現調用 compareTo 方法進行比較
3.若是仍未比較出大小，就須要進行仲裁了，仲裁方法爲 tieBreakOrder（你們本身看源碼吧）
tie break 是網球術語，能夠理解爲加時賽的意思，起這個名字仍是挺有意思的。
經過上面三次比較，最終就能夠比較出孰大孰小。比較出大小後就能夠構造紅黑樹了，最終構造出的紅黑樹以下：
橙色的箭頭表示 TreeNode 的 next 引用。因爲空間有限，prev 引用未畫出。能夠看出，鏈表轉成紅黑樹後，原鏈表的順序仍然會被引用仍被保留了（紅黑樹的根節點會被移動到鏈表的第一位），咱們仍然能夠按遍歷鏈表的方式去遍歷上面的紅黑樹。這樣的結構爲後面紅黑樹的切分以及紅黑樹轉成鏈表作好了鋪墊，咱們繼續往下分析。
紅黑樹拆分
擴容後，普通節點須要從新映射，紅黑樹節點也不例外。按照通常的思路，咱們能夠先把紅黑樹轉成鏈表，以後再從新映射鏈表便可。這種處理方式是你們比較容易想到的，但這樣作會損失必定的效率。不一樣於上面的處理方式，HashMap 實現的思路則是上好佳（上好佳請把廣告費打給我）。如上節所說，在將普通鏈表轉成紅黑樹時，HashMap 經過兩個額外的引用 next 和 prev 保留了原鏈表的節點順序。這樣再對紅黑樹進行從新映射時，徹底能夠按照映射鏈表的方式進行。這樣就避免了將紅黑樹轉成鏈表後再進行映射，無形中提升了效率。
以上就是紅黑樹拆分的邏輯，下面看一下具體實現吧：
// 紅黑樹轉鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 紅黑樹節點仍然保留了 next 引用，故仍能夠按鏈表方式遍歷紅黑樹。
* 下面的循環是對紅黑樹節點進行分組，與上面相似
*/
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 若是 loHead 不爲空，且鏈表長度小於等於 6，則將紅黑樹轉成鏈表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
/*
* hiHead == null 時，代表擴容後，
* 全部節點仍在原位置，樹結構不變，無需從新樹化
*/
if (hiHead != null)
loHead.treeify(tab);
}
}
// 與上面相似
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
從源碼上能夠看得出，從新映射紅黑樹的邏輯和從新映射鏈表的邏輯基本一致。不一樣的地方在於，從新映射後，會將紅黑樹拆分紅兩條由 TreeNode 組成的鏈表。若是鏈表長度小於 UNTREEIFY_THRESHOLD，則將鏈表轉換成普通鏈表。不然根據條件從新將 TreeNode 鏈表樹化。舉個例子說明一下，假設擴容後，從新映射上圖的紅黑樹，映射結果以下：
紅黑樹鏈化
前面說過，紅黑樹中仍然保留了原鏈表節點順序。有了這個前提，再將紅黑樹轉成鏈表就簡單多了，僅需將 TreeNode 鏈表轉成 Node 類型的鏈表便可。相關代碼以下：
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// 遍歷 TreeNode 鏈表，並用 Node 替換
for (Node<K,V> q = this; q != null; q = q.next) {
// 替換節點類型
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
上面的代碼並不複雜，不難理解，這裏就很少說了。到此擴容相關內容就說完了，不知道你們理解沒。
3.5 刪除
若是你們堅持看完了前面的內容，到本節就能夠輕鬆一下。固然，前提是不去看紅黑樹的刪除操做。不過紅黑樹並不是本文講解重點，本節中也不會介紹紅黑樹相關內容，因此你們不用擔憂。
HashMap 的刪除操做並不複雜，僅需三個步驟便可完成。第一步是定位桶位置，第二步遍歷鏈表並找到鍵值相等的節點，第三步刪除節點。相關源碼以下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final 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 &&
// 1. 定位桶位置
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 若是鍵的值與鏈表第一個節點相等，則將 node 指向該節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 若是是 TreeNode 類型，調用紅黑樹的查找邏輯定位待刪除節點
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 2. 遍歷鏈表，找到待刪除節點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 3. 刪除節點，並修復鏈表或紅黑樹
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;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
刪除操做自己並不複雜，有了前面的基礎，理解起來也就不難了，這裏就很少說了。
3.6 其餘細節
前面的內容分析了 HashMap 的經常使用操做及相關的源碼，本節內容再補充一點其餘方面的東西。
被 transient 所修飾 table 變量
若是你們細心閱讀 HashMap 的源碼，會發現桶數組 table 被申明爲 transient。transient 表示易變的意思，在 Java 中，被該關鍵字修飾的變量不會被默認的序列化機制序列化。咱們再回到源碼中，考慮一個問題：桶數組 table 是 HashMap 底層重要的數據結構，不序列化的話，別人還怎麼還原呢？
這裏簡單說明一下吧，HashMap 並無使用默認的序列化機制，而是經過實現readObject/writeObject兩個方法自定義了序列化的內容。這樣作是有緣由的，試問一句，HashMap 中存儲的內容是什麼？不用說，你們也知道是鍵值對。因此只要咱們把鍵值對序列化了，咱們就能夠根據鍵值對數據重建 HashMap。有的朋友可能會想，序列化 table 不是能夠一步到位，後面直接還原不就好了嗎？這樣一想，倒也是合理。但序列化 talbe 存在着兩個問題：
table 多數狀況下是沒法被存滿的，序列化未使用的部分，浪費空間
同一個鍵值對在不一樣 JVM 下，所處的桶位置多是不一樣的，在不一樣的 JVM 下反序列化 table 可能會發生錯誤。
以上兩個問題中，第一個問題比較好理解，第二個問題解釋一下。HashMap 的get/put/remove等方法第一步就是根據 hash 找到鍵所在的桶位置，但若是鍵沒有覆寫 hashCode 方法，計算 hash 時最終調用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不一樣的 JVM 下，可能會有不一樣的實現，產生的 hash 可能也是不同的。也就是說同一個鍵在不一樣平臺下可能會產生不一樣的 hash，此時再對在同一個 table 繼續操做，就會出現問題。
綜上所述，你們應該能明白 HashMap 不序列化 table 的緣由了。
4.HashMap優缺點?
1.缺陷就在於其高度依賴hash算法，若是key是自定義類，你得本身重寫hashcode方法，寫hash算法。並且hashmap要求，存入時的hashcode什麼樣，以後就不能在變動，若是一個類的hashcode與其成員變量name有關，而以後name又發生了變化，那麼hashmap行爲將不正常。兩個對象若是equals相同，那hashcode的值必定相同，若是hashcode值相同，對象不必定equals相同，只能證實兩對象在散列存儲中處於同一位置！ 在散列存儲中存放元素，一般先判斷hash值，肯定是否是在這個位置，再判斷equals 和已存放的元素是否相等。因此hash值又必須跟對象屬性有關係，不然沒法保證equals相等 hash就等，但和屬性掛鉤，一旦屬性變化，hash就變化，處於散列存儲的位置就會發生變化.
2.hashmap的元素存儲位置，除了元素key的hash值有關，還跟數組自己長度有關，若是擴容數組長度發生變化，必須把全部元素從新計算其index存放位置，因此儘量事先肯定hashmap的大小，防止擴容.
3.非線程安全,HashMap在多線程狀況下插入元素過多的時候須要進行Resize，Resize的條件是HashMap.Size >= Capacity *LoadFactor。而且Hashmap的Resize包含擴容和ReHash兩個步驟，ReHash在併發的狀況下可能會造成鏈表環。
5.建議:
若是要保證HashMap在多線程下的安全性,能夠本身處理併發狀況,也能夠去採用另外一個集合類ConcurrentHashMap或者是經過Collections.synchronizedMap(new HashMap<>());的方式去建立map並使用.
6.其餘問題
6.1有什麼方法能夠減小碰撞？
擾動函數能夠減小碰撞，原理是若是兩個不相等的對象返回不一樣的hashcode的話，那麼碰撞的概率就會小些，這就意味着存鏈表結構減少，這樣取值的話就不會頻繁調用equal方法，這樣就能提升HashMap的性能。（擾動即Hash方法內部的算法實現，目的是讓不一樣對象返回不一樣hashcode。）
使用不可變的、聲明做final的對象，而且採用合適的equals()和hashCode()方法的話，將會減小碰撞的發生。不可變性使得可以緩存不一樣鍵的hashcode，這將提升整個獲取對象的速度，使用String，Interger這樣的wrapper類做爲鍵是很是好的選擇。爲何String, Interger這樣的wrapper類適合做爲鍵？由於String是final的，並且已經重寫了equals()和hashCode()方法了。不可變性是必要的，由於爲了要計算hashCode()，就要防止鍵值改變，若是鍵值在放入時和獲取時返回不一樣的hashcode的話，那麼就不能從HashMap中找到你想要的對象。
6.2 HashMap中hash函數怎麼是是實現的?
咱們能夠看到在hashmap中要找到某個元素，須要根據key的hash值來求得對應數組中的位置。如何計算這個位置就是hash算法。前面說過hashmap的數據結構是數組和鏈表的結合，因此咱們固然但願這個hashmap裏面的元素位置儘可能的分佈均勻些，儘可能使得每一個位置上的元素數量只有一個，那麼當咱們用hash算法求得這個位置的時候，立刻就能夠知道對應位置的元素就是咱們要的，而不用再去遍歷鏈表。 因此咱們首先想到的就是把hashcode對數組長度取模運算，這樣一來，元素的分佈相對來講是比較均勻的。可是，「模」運算的消耗仍是比較大的，能不能找一種更快速，消耗更小的方式，咱們來看看JDK1.8的源碼是怎麼作的
static final int hash(Object key) {
if (key == null){
return 0;
}
int h;
h=key.hashCode()；返回散列值也就是hashcode
// ^ ：按位異或
// >>>:無符號右移，忽略符號位，空位都以0補齊
//其中n是數組的長度，即Map的數組部分初始化長度
return (n-1)&(h ^ (h >>> 16));
}
簡單來講就是
一、高16bt不變，低16bit和高16bit作了一個異或(獲得的HASHCODE轉化爲32位的二進制，前16位和後16位低16bit和高16bit作了一個異或)
二、(n·1)&hash=->獲得下標
五、拉鍊法致使的鏈表過深問題爲何不用二叉查找樹代替，而選擇紅黑樹？爲何不一直使用紅黑樹？
之因此選擇紅黑樹是爲了解決二叉查找樹的缺陷，二叉查找樹在特殊狀況下會變成一條線性結構（這就跟原來使用鏈表結構同樣了，形成很深的問題），遍歷查找會很是慢。而紅黑樹在插入新數據後可能須要經過左旋，右旋、變色這些操做來保持平衡，引入紅黑樹就是爲了查找數據快，解決鏈表查詢深度的問題，咱們知道紅黑樹屬於平衡二叉樹，可是爲了保持「平衡」是須要付出代價的，可是該代價所損耗的資源要比遍歷線性鏈表要少，因此當長度大於8的時候，會使用紅黑樹，若是鏈表長度很短的話，根本不須要引入紅黑樹，引入反而會慢。
6.3 說說你對紅黑樹的看法？
一、每一個節點非紅即黑
二、根節點老是黑色的
三、若是節點是紅色的，則它的子節點必須是黑色的（反之不必定）
四、每一個葉子節點都是黑色的空節點（NIL節點）
五、從根節點到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點（即相同的黑色高度）
七、解決hash 碰撞還有那些辦法？
開放定址法。
當衝突發生時，使用某種探查技術在散列表中造成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定的地址。
按照造成探查序列的方法不一樣，可將開放定址法區分爲線性探查法、二次探查法、雙重散列法等。
下面給一個線性探查法的例子
問題：已知一組關鍵字爲(26，36，41，38，44，15，68，12，06，51)，用除餘法構造散列函數，用線性探查法解決衝突構造這組關鍵字的散列表。
解答：爲了減小衝突，一般令裝填因子α由除餘法因子是13的散列函數計算出的上述關鍵字序列的散列地址爲(0，10，2，12，5，2，3，12，6，12)。
前5個關鍵字插入時，其相應的地址均爲開放地址，故將它們直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。
當插入第6個關鍵字15時，其散列地址2(即h(15)=15％13=2)已被關鍵字41(15和41互爲同義詞)佔用。故探查h1=(2+1)％13=3，此地址開放，因此將15放入T[3]中。
當插入第7個關鍵字68時，其散列地址3已被非同義詞15先佔用，故將其插入到T[4]中。
當插入第8個關鍵字12時，散列地址12已被同義詞38佔用，故探查hl=(12+1)％13=0，而T[0]亦被26佔用，再探查h2=(12+2)％13=1，此地址開放，可將12插入其中。
相似地，第9個關鍵字06直接插入T[6]中；而最後一個關鍵字51插人時，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
6.4 若是HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
默認的負載因子大小爲0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)同樣，將會建立原來HashMap大小的兩倍的bucket數組，來從新調整map的大小，並將原來的對象放入新的bucket數組中。這個過程叫做rehashing，由於它調用hash方法找到新的bucket位置。這個值只可能在兩個地方，一個是原下標的位置，另外一種是在下標爲<原下標+原容量>的位置