超詳細的HashMap解析(jdk1.8)
目錄
本文首發於 ofollow,noindex" target="_blank">cdream的個人部落格
歡迎轉載，轉載請註明出處。
本文是我在學習 java集合過程中，針對HashMap的一篇總結文章。由於博主是非科班出身程式員，在學習HashMap原理時遇到了很多困難，所以如果你和博主一樣，資料結構基礎也不紮實甚至是沒有基礎，這篇文章可能也非常適合你！
注：本文基於jdk1.8,不包括紅黑樹部分分析
以下是本文的結構，可根據需要跳轉到相應位置，不必按順序閱讀！
一、預備知識
時間複雜度
時間複雜度用來度量演算法的執行時間，記作: T(n) = O(f(n))。它表示隨著輸入 n 的增大，演算法執行需要的時間的增長速度可以用 f(n) 來描述。漸進時間複雜度用大寫O來表示，所以也被稱為大 O表示法。
常用的時間複雜度比較:
O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)
從左到右，演算法執行效率逐漸下降,
瞭解更多：
基本資料結構
HashMap主幹是雜湊表，這之前先了解一下其他幾種資料結構的效能。
陣列
採用一段連續的儲存單元來儲存資料。對於指定下標的查詢，時間複雜度為 O(1)；通過給定值進行查詢（順序查詢），需要遍歷陣列，逐一比對給定關鍵字和陣列元素，時間複雜度為 O(n)；對於有序陣列，可採用二分查詢，插值查詢，斐波那契查詢等方式，可將查詢複雜度提高為 O(logn)；對於指定位置的插入刪除操作，涉及到陣列元素的移動，其平均複雜度為 O(n)；另外修改和查詢實現複雜度相同。
連結串列
不是按線性的順序儲存資料，而是在每一個節點裡存到下一個節點的指標(Pointer)。對於連結串列的新增，刪除等操作（在找到指定操作位置後），僅需處理結點間的引用即可，時間複雜度為 O(1)，而查詢操作需要遍歷連結串列逐一進行比對，複雜度為 O(n)。
陣列與連結串列的根據指定值查詢時間複雜度都是O(1),但陣列更快
1. 連結串列需要在遍歷時，需要比陣列更多的定址操作 2. CPU快取會把一片連續的記憶體空間讀入，因為陣列結構是連續的記憶體地址，所以陣列全部或者部分元素被連續存在CPU快取裡面，而連結串列則不會紅黑樹
是一種自平衡二叉查詢樹，可以在O(log n)時間內做查詢，插入和刪除，jdk8之後HashMap桶內連結串列長度超過樹化閥值且總長度超過最小樹化容量後會將連結串列轉換為紅黑樹。
散列表
散列表(Hash table，也叫雜湊表)是一種根據 key-value進行訪問的資料結構。在散列表中進行新增，刪除，查詢等操作，效能十分之高，不考慮雜湊衝突的情況下，僅需一次定位即可完成，時間複雜度為O(1)。雜湊表是 HashMap主幹，所以在分析 HashMap前要先詳細瞭解一下雜湊表。
散列表(Hash table)，是根據鍵（Key）而直接訪問在記憶體儲存位置的資料結構。也就是說，它通過計算一個關於鍵值的函式f(x)，將所需查詢的資料對映到表中一個位置來訪問記錄，這加快了查詢速度。這個對映函式f(x)稱做 雜湊函式 ，存放記錄的陣列稱做散列表。
雜湊函式(Hash function)，經雜湊函式映象到地址集合中任何一個地址的概率是相等的，則稱此類雜湊函式為 均勻雜湊函式 (Uniform Hash function)，雜湊函式的設計至關重要，好的雜湊函式會盡可能地保證 計算簡單 和 雜湊地址分佈均勻 。雜湊函式構造方法包括直接定址法，隨機數法，除留餘數法等。
衝突(Collision)：對不同的Key可能得到同一雜湊地址，即k1≠ k2，而 f(k1)=f(k2)，再好的雜湊函式也無法避免衝突。產生衝突就要進行處理，通常處理衝突的方法有開發定址法，單獨連結串列法，雙雜湊，再雜湊等。在java中使用的是 單獨連結串列法 。
舉個例子：
假設有個陣列長度為4陣列(每一個位置都叫桶bucket)，這裡有3個人趙四，錢五，孫六要裝進去，我們定義一個規則，按姓氏在百家姓中的順序除以四得到的餘數作為索引放入四個位置。
當前存放三個人記錄的陣列就是散列表，我們定義的規則就是雜湊函式，根據雜湊函式進行對映的過程叫做雜湊過程。
如果又來一個人叫週日，根據我們的規則，週日也要落在1的位置上，此時就產生了衝突。這裡我們使用單獨連結串列法處理，把周天放在索引為一的位置和趙四構成連結串列（新元素是放在連結串列前端還是後端完全是取決於怎麼方便）。
散列表查詢是就是先找到桶的位置，再遍歷查詢需要的資料。如果雜湊函式設計的不好，所有的元素都落在一個桶裡那效率就特別低，和單鏈表隨機訪問沒什麼區別。
基本位運算
| 運算子 | 計算方式 |
|---|---|
| 與 & | 只有兩個數同一位都是1才會返回1 |
| 或 l | 兩個數同一位只要存在一個1就是1 |
| 異或 ^ | 兩個數同一位不能相同才為1 |
| 左移 << | 所有位置左移，低位補0 |
| 右移 >> | 正數：所有位置右移，高位補0 負數：寫出補碼（符號位不變，其餘位置取反，然後加1），所有位置右移高位補1，然後再獲取原碼（符號位不變，其餘位置取反，然後加1） |
| 無符號右移 >> | 無論正負高位補0 |
瞭解更多：
二、HashMap實現原理
結構
Node是 HashMap的靜態內部，HashMap主幹是一個Node陣列，Node是HashMap的最基本組成單位。
// HashMap的主幹陣列 transient Node<K,V>[] table;
Node
static class Node<K,V> implements Map.Entry<K,V> {
// 這個節點所在位置的hash值
final int hash;
final K key;
V value;
// 下一個節點的引用
Node<K,V> next;
/**
* 構造方法
*/
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
…………(其他get(),set()等方法省略)
}
在jdk8之前HashMap是陣列加連結串列的形式實現，但是在1.8之後為提高雜湊衝突後連結串列的查詢速度，當桶內連結串列長度超過 樹化閥值 且總長度超過 最小樹化容量 後會將連結串列轉換為紅黑樹。
jdk7
jdk8
速度
查詢與修改
先用雜湊函式對鍵進行雜湊，沒有衝突的情況下查詢是下標查詢，時間複雜度是 O(1),速度很快。
存在雜湊衝突的情況，需要對連結串列/紅黑樹進行遍歷，equals比對查詢。
效能上，考慮是連結串列/紅黑樹上的元素越是越好，越均勻越好；此外HashMap主幹未必越長越好，會有用不到的桶浪費空間。
增加與刪除
由於查詢速度快，而桶裡用連結串列/紅黑樹實現，所以新增和刪除效率也很高。HashMap會在size超過閥值後進行調整大下(resize)，所以根據具體情況提前給HashMap一個合適的初始長度是個不錯的習慣。
三、原始碼分析
基本常量
// 預設初始長度，即主幹陣列的長度，如果建立物件時沒有給長度，預設是16 // 在明確知道元素個數的情況下，初始化時建議可以把容量設定成expectedSize / 0.75F + 1.0F (guava) static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量,HashMap最大容量是2^30 // 因為int範圍是-2^31——2^31-1,但32位2進位制最高位是符號位，所以最大是2^30 static final int MAXIMUM_CAPACITY = 1 << 30; // 預設負載因子，預設是0.75，建立物件時可以自定義 // 可以用於計算擴容閥值transient Node<K,V>[] table; static final float DEFAULT_LOAD_FACTOR = 0.75f; // 樹化閥值 // 當某一個桶中連結串列長度超過8時會轉化為紅黑樹 static final int TREEIFY_THRESHOLD = 8; // 去樹化閥值 // 當一個桶裡紅黑樹總結點數小於6時，會轉化為連結串列 static final int UNTREEIFY_THRESHOLD = 6; // 最小樹化容量 // 樹化的另一個條件，只有主幹陣列長度大於64才進行樹化 static final int MIN_TREEIFY_CAPACITY = 64;
CAPACITY是 HashMap容量(主幹陣列長度)，size是鍵值對個數
基本成員變數
// 主幹陣列 transient Node<K,V>[] table; // 遍歷時經常用到 transient Set<Map.Entry<K,V>> entrySet; // HashMap中Node的總個數 transient int size; // 用於快速失敗，HashMap是非執行緒安全的,在迭代過程中，如果結構發生改變，會丟擲ConcurrentModificationException transient int modCount; // 閥值，是否調整主幹陣列長度的指標 // 一般由capacity(主幹陣列長度) * loadFactor計算，超過範圍會取最大容量MAXIMUM_CAPACITY int threshold; //負載因子，陣列的填充量，計算閥值使用，上面有個預設的0.75F final float loadFactor;
構造方法
主要構造方法
HashMap有四種構造方法，這裡只說最核心的一個，只說傳入初始容量和負載因子這種。
/**
* 核心構造方法
* @paraminitialCapacity 初始化容量
* @paramloadFactor負載因子
*/
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量小於0，拋異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 如果大於了最大容量，就轉成最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 負載因子小於0或是個非法數字(除數為0這種)，拋異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 這裡初始容量賦值給了閥值，後面會用到
this.threshold = tableSizeFor(initialCapacity);
}
在構造方法中，並沒有對table這個成員變數進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算。
tableSizeFor(initialCapacity) 方法是用來計算初始容量的，HashMap容量並不是傳多少就是多少，而一定是2的次冪。這個方法會返回一個比給定容量大的最小2的次冪的數。
舉個例子:如果你給了9，比9大的最小2的次冪是16(2^4)；如果你給個27，比27大的最小的2的次冪是32(2^5)。
static final int tableSizeFor(int cap) {
// 先是將cap減1，否則，如果cap是2的次冪，例如16，計算結果就是32，是我們需要的容量的2倍
int n = cap - 1;
// 這裡是先將n無符號右移，再與n進行或運算並賦值給n
// 這樣好理解一點 =>n = n | (n >>> 1)
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// 如果n<0返回1
// 如果n>最大容量返回最大容量
// 否則返回 n+1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
解釋：
n=0
經過幾次次無符號右移還是0，最後返回n+1是1
n>0
下面這個圖演示前三步移動的過程
剩下的大家腦補，最後算出來就是32位以內最高位那個1後面跟的都是1，然後n≠1的情況下會加個1，就是我們要的結果，這裡結果是2^8，原來那個顯然是大於2^7的一個數。看完這個過程是不是覺得"妙啊！"，我也覺得這個演算法好機智，哈哈。
其他構造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
以上幾個建構函式都沒有直接的建立一個切實存在的陣列，他們都是在為建立陣列需要的一些引數做初始化，table的初始化被推遲到了put方法中，所以這幾個建構函式中並沒有被初始化的屬性都會在實際初始化陣列的時候用預設值替換。
這個建構函式有put過程，table已經完成初始化
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
小結
1. 建構函式會建立一個容量（主幹陣列長度）大於等於initialCapacity的最小的2的冪長度的HashMap
2. 負載因子可以自定義
3. 多數構造方法中並沒有初始化table,table初始化的過程是在put方法中完成的put方法
put
put方法是一個重點方法，這裡有 HashMap初始化，資料在 HashMap中是如何儲存的，什麼情況下連結串列會轉換為紅黑樹等內容，需要仔細研究。
public V put(K key, V value) {
//這裡繼續呼叫putVal方法
return putVal(hash(key), key, value, false, true);
}
putVal
putVal是final修飾的方法，子類 LinkedHashMap也是用的這各方法，evict（看下面的的第5個引數）就是給 LinkedHashMap使用的，HashMap中並沒有什麼用。
/** * 真正進行插入操作的方法， * hash 傳入key的雜湊值 * onlyIfAbsent 如果該值是true,如果存在值就不會進行修改操作 * evict LinekdHashMap尾操作使用，這裡暫無用途 */ 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長度是0或table是null會調整一次大小 // 這時tab會指向調整大下後的Node<K,V>[](主幹陣列) // n被賦值為新陣列長度 // 如果沒有調整大小，tab指向table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /********開始查詢鍵的位置，並存儲value*******/ // i = (n - 1) & hash這個是獲取key應該在哪個桶裡,下面詳說 // 這裡將p指向當前key所需要的那個桶 if ((p = tab[i = (n - 1) & hash]) == null) // 如果空桶，也就是無雜湊衝突的情況，直接丟個Node進去。 // 此時的tab就是table tab[i] = newNode(hash, key, value, null); //存在衝突，開始尋找我們要找的節點 else { Node<K,V> e; K k; // 判斷第一個節點是不是我們找的 // 此時k儲存了 p.key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // hash系值相等，key值相等，定位完成,是修改操作 // e來儲存p這個節點，一會修改 e = p; // 判斷是否是紅黑樹節點 else if (p instanceof TreeNode) // 是紅黑樹節點，存在就返回那個節點，不存在就返回null e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 最終，是連結串列了，開始對連結串列遍歷查詢 else { for (int binCount = 0; ; ++binCount) { // 上面知道第一個接點不是我們要的，直接獲取下一個，並儲存給e // 下一個是空，直接丟個Node在這裡，然後p.next指向這裡 // 這裡下一個節點地址給了e if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // ！大於樹化閥值，開始樹化 // 注意-1是因為binCount是索引而不是長度 // 其實此時連結串列長度已經是7+1（索引） + 1（新進來的Node） // 已經大於樹化閥值8，也就是說連結串列長度為8時是不會樹化的 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); //加進去就跳出迴圈了 break; } // 下個節點有值，且是我們找的節點，跳出去 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //下一個節點不是我們找的節點繼續編歷 p = e; } } // 上面說了，這有修改操作e才能不是null if (e != null) { // existing mapping for key V oldValue = e.value; // 給e新值 if (!onlyIfAbsent || oldValue == null) e.value = value; // 這個是LinkedHashMap用的，HashMap裡是個空實現 afterNodeAccess(e); // 修改就會把舊值返回去 return oldValue; } } /*********修改完成的後續操作**********/ // 修改次數加1 ++modCount; // 如果size大於閥值，會執行resize()方法調整大小 if (++size > threshold) resize(); // 這個是給LinkedHashMap用的，HashMap裡也是個空實現 afterNodeInsertion(evict); // 新增成功返回null return null; }
hash
再來看一下hash()這個方法吧。
static final int hash(Object key) {
int h;
// key是null就返回0，key不是null就先取hashCode（）然後與這個hashCode（）無符號右移進行亦或運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可能小夥伴有疑惑，好好的hashCode()非弄個亦或運算幹啥？
舉個例子：下圖就是table.length為16時的計算情況，如果沒有亦或運算就只和低4位有關，這樣就會加大沖突的概率。
resize
這也是一個很重要的方法，主要包括兩部分，第一部分是根據size是否超過閥值判斷是否需要進行擴容，第二部分是擴容後將原Node[]中資料複製到擴容後的Node[]中
擴容部分
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 原容量，table為null返回0，否則返回table長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 原閥值
int oldThr = threshold;
// 新容量，新閥值
int newCap, newThr = 0;
// table已經初始化
if (oldCap > 0) {
// 容量已經超過最大容量，直接返回去
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
}
// 原陣列容量為0，未初始化，單閥值不為0
// 也就是構造方法裡threshold = tableSizeFor(initialCapacity）這個步驟
else if (oldThr > 0)
newCap = oldThr;
// 啥都沒有，預設構造
else {
newCap = 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;
複製資料部分
看原始碼前，先看下面這個圖
正常來講，向新陣列複製元素時需要重新計算位置，現在有了這個規律，就可以這樣做：
- x=0不改變位置
- x≠0原位置+原陣列長度獲取新位置
判斷x是否為0， e.hash & oldCap 可以完成，返回結果是0，代表x處是0，位置不用改變，否則改變位置
//建立新的陣列
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;
// x獲取桶的第一個節點
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 {
// 不是直接進行計算元素在新陣列中的位置，而是原位置加原陣列長度
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 把連結串列下一個節點放在 next裡
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;
}
複製過程，a過去，假設計算後位置不邊，進到i,此時i為null，a進去後即是head，又是tail
然後迴圈，到b，假設計算後還是i，i中已經有a，所以b直接丟到a後面，a任是head,單tail已經變成了b
以此類推，a,b,c,d都會放在i,j中
其實是先拼完連結串列才裝進桶裡的，這裡只是方便描述，說成是一個一個過去
至此，put方法已經說完了，重點是putVal,hash和resize三個方法，如果不理解可以看本文結尾的參考文獻，因為不同的人思維方式，表達方式都不同，說不定換一種表述方式就能理解了。
remove
remove就是先找到節點位置，然後移除,核心方法是removeNode()
public V remove(Object key) {
Node<K,V> e;
// 呼叫removeNode，如果移除成功返回原值，否則返回null
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
removeNode
/**
* value remove方法過載時使用，只有同時匹配key-value時移除該節點
* matchValue,為true時才會同時匹配key-value進行刪除
* movable 刪除節點後是否改變紅黑樹的結構，般都為true只有在iterator的時候才為false
*/
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;
// 1.原陣列不為null 2. 原陣列長度大於0 3.key陣列中的位置不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 宣告兩個節點node，e
Node<K,V> node = null, e; K k; V v;
// 第一個節點就我們要找的節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 先給node，在下面刪掉
node = p;
else if ((e = p.next) != null) {
// 如果是紅黑樹，獲取該接點並給node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 如果是連結串列，迴圈遍歷
else {
do {
// 如果是要找的節點就把這個節點給node
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
// 不是把節點給p記錄，繼續檢查下一個節點
p = e;
} while ((e = e.next) != null);
}
}
/**********刪除節點的部分*********/
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果是紅黑樹節點，使用removeTreeNode移除
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;
// 修改次數再加1
++modCount;
// 長度 -1
--size;
// 給LinkedList使用，這裡沒啥用
afterNodeRemoval(node);
// 刪除的值返回去
return node;
}
}
// 根本沒有這個鍵
return null;
}
大致過程就是這個樣子的~~，勉強看吧沒畫圖天賦！
原始碼分析到這裡就結束，看了這幾個方法，只要不是紅黑樹的部分，看起來就很沒那麼困難了。
四、日常使用注意事項
-
在可以明確HashMap長度的情況下，最好給HashMap一個初始容量
看完上面原碼後，會發現HashMap使用過程中會出現resize()操作，會涉及到雜湊表的重建，這是一個比較消耗資源的操作，如果在明確長度的情況下，能給定合適的容量就可以減少甚至避免擴容操作。
阿里巴巴開發手冊給出如下公式：
{% cq %}
initialCapacity = (需要儲存的元素個數 / 負載因子) + 1。
{% endcq %}
注意負載因子（即loader factor）預設為0.75， 如果暫時無法確定初始值大小，請設定為16（即預設值）
在guava中其實也使用這個公式，並且guava提供下面這個方法來建立HashMap：
{% note info %}Map<String, String> map = Maps.newHashMapWithExpectedSize(10){% endnote %}
其實這個公式是來自putAll()方法，感興趣的小夥伴可以去看一下。
-
重寫equals方法是一定要重寫hashCode方法
老生長談了，這裡主要針對key是物件的情況，舉個例子：
class Person{ int idCard; String name; public Person(int idCard, String name) { this.idCard = idCard; this.name = name; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()){ return false; } Person person = (Person) o; //兩個物件是否等值，通過idCard來確定 return this.idCard == person.idCard; } @Test public void test(){ Map map = new HashMap(); Person p1 = new Person(1234,"小白"); map.put(p1,"哈哈哈哈"); Person p2 = new Person(1234,"小白"); map.get(p2); }當用person來做key時，顯然，如果在hashcode不重寫的情況下，使用p2是無法獲得需要的內容的，因為兩個物件用來找桶的hashcode是不同的，所以無法找到想同的桶啊！桶都找不到去哪裡找值哈哈！
五、總結
本文記錄了我學習HashMap的全過程，包括預備知識、實現原理、原始碼分析、注意事項等幾個部分，對我這個沒資料結構基礎的人來說收穫真的很大，希望對各位讀者也有一定的幫助！存在問題希望大家指正！
本文參考：