先看一下 HashMap資料結構其中Entry為HashMap的内部類，它包含了鍵key、值value、下一個節點next，以及hash值，這是非常重要的，正是由于Entry才構成了table數組的項為連結清單
我們知道在 Java 中最常用的兩種結構是數組和模拟指針(引用)，幾乎所有的資料結構都可以利用這兩種來組合實作。數組的存儲方式在記憶體的位址是連續的，大小固定，一旦配置設定不能被其他引用占用。它的特點是查詢快，時間複雜度是O(1)，插入和删除的操作比較慢，時間複雜度是O(n)，連結清單的存儲方式是非連續的，大小不固定，特點與數組相反，插入和删除快，查詢速度慢。HashMap可以說是一種折中的方案吧。
本文基于Java7的源碼做剖析
先看一下成員變量
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16,預設初始容量為16，必須為2的幂；
/**
* 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 = << ;//最大容量值，容量值必須為2的幂且小于該值；
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = f;//預設加載因子
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};//空的Entry數組，未調整表容量前共享。
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//必須重設容量的Entry數組表，長度必須為2的幂；
/**
* The number of key-value mappings contained in this map.
*/
transient int size;//HashMap的大小，即Entry元素總量;
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;//臨界值，如果表是空的，則該值作為空表膨脹的初始容量；
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;//哈希表的加載因子
/**
* 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;//hashMap結構修改次數統計
/**
* The default threshold of map capacity above which alternative hashing is
* used for String keys. Alternative hashing reduces the incidence of
* collisions due to weak hash code calculation for String keys.
* <p/>
* This value may be overridden by defining the system property
* {@code jdk.map.althashing.threshold}. A property value of {@code 1}
* forces alternative hashing to be used at all times whereas
* {@code -1} value ensures that alternative hashing is never used.
*/
// 預設備用雜湊演算法啟用門檻值，預設大小為Integer.MAX_VALUE,該變量被靜态内部類Holder引用。
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* A randomizing value associated with this instance that is applied to
* hash code of keys to make hash collisions harder to find. If 0 then
* alternative hashing is disabled.
*/
//哈希種子，用于降低key的hash碰撞機率，如果為0則禁用備用雜湊演算法；
transient int hashSeed = ;
先來看看put的幾種分支
HashM ap源碼分析
HashMap通過鍵的hashCode來快速的存取元素。當不同的對象hashCode發生碰撞時，HashMap通過單連結清單來解決，将新元素加傳入連結表表頭，通過next指向原有的元素。
先說說大概的過程：當我們調用put存值時，HashMap首先會擷取key的哈希值，通過哈希值快速找到某個存放位置，這個位置可以被稱之為bucketIndex。
對于一個key，如果hashCode不同，equals一定為false，如果hashCode相同，equals不一定為true。
是以理論上，hashCode可能存在沖突的情況，也叫發生了碰撞，當碰撞發生時，計算出的bucketIndex也是相同的，這時會取到bucketIndex位置已存儲的元素，最終通過equals來比較，equals方法就是哈希碼碰撞時才會執行的方法，是以說HashMap很少會用到equals。HashMap通過hashCode和equals最終判斷出K是否已存在，如果已存在，則使用新V值替換舊V值，并傳回舊V值，如果不存在 ，則存放新的鍵值對<K, V>到bucketIndex位置。
- //當key為null，調用putForNullKey方法，儲存null于table第一個位置中，這是HashMap允許為null的原因
- if (key == null)
- return putForNullKey(value);
- //計算key的hash值
- int hash = hash(key.hashCode()); ------( )
- //計算key hash 值在 table 數組中的位置
- int i = indexFor(hash, table.length) ; ------()
- //從i出開始疊代 e,找到 key 儲存的位置
- for (Entry<K, V> e = table[i]; e != null; e = e.next) {
- Object k;
- //判斷該條鍊上是否有hash值相同的(key相同)
- //若存在相同，則直接覆寫value，傳回舊value
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value; //舊值 = 新值
- e.value = value;
- e.recordAccess( this);
- return oldValue; //傳回舊值
- }
- }
- //修改次數增加1
- modCount++;
- //将key、value添加至i位置處
- addEntry(hash, key, value, i);
- return null;
- }
通過源碼我們可以清晰看到HashMap儲存資料的過程為：
1)首先判斷key是否為null，若為null，則直接調用putForNullKey方法
從代碼可以看出，如果key為null的值，預設就存儲到table[0]開頭的連結清單了。然後周遊table[0]的連結清單的每個節點Entry，如果發現其中存在節點Entry的key為null，就替換新的value，然後傳回舊的value，如果沒發現key等于null的節點Entry，就增加新的節點
2)計算key的hashcode（hash(key.hashCode())），再用計算的結果二次hash（indexFor(hash, table.length)），找到Entry數組的索引i，這裡涉及到hash算法，最後會詳細講解
3)周遊以table[i]為頭節點的連結清單，如果發現hash，key都相同的節點時，就替換為新的value，然後傳回舊的value，隻有hash相同時，循環内并沒有做任何處理
4)modCount++代表修改次數，與疊代相關，在疊代篇會詳細講解
5)對于hash相同但key不相同的節點以及hash不相同的節點，就增加新的節點（addEntry()）
- void addEntry(int hash, K key, V value, int bucketIndex) {
- //擷取bucketIndex處的Entry
- Entry<K, V> e = table[bucketIndex];
- //将新建立的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
- table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
- //若HashMap中元素的個數超過極限了，則容量擴大兩倍
- if (size++ >= threshold)
- resize( * table.length);
- }
這裡新增加節點采用了頭插法，新節點都增加到頭部，新節點的next指向老節點
這裡涉及到了HashMap的擴容問題，随着HashMap中元素的數量越來越多，發生碰撞的機率就越來越大，所産生的連結清單長度就會越來越長，這樣勢必會影響HashMap的速度，為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數量等于table數組長度*加載因子。但是擴容是一個非常耗時的過程，因為它需要重新計算這些資料在新table數組中的位置并進行複制處理。
- void resize(int newCapacity) {
- HashMapEntry[] oldTable = table;
- int oldCapacity = oldTable.length;
- if (oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
- HashMapEntry[] newTable = new HashMapEntry[newCapacity];
- transfer(newTable);
- table = newTable;
- threshold = ( int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
- }
從代碼可以看出，如果大小超過最大容量就傳回。否則就new 一個新的Entry數組，長度為舊的Entry數組長度的兩倍。然後将舊的Entry[]複制到新的Entry[].
- void transfer(HashMapEntry[] newTable) {
- int newCapacity = newTable.length;
- for (HashMapEntry<K,V> e : table) {
- while( null != e) {
- HashMapEntry<K,V> next = e.next;
- int i = indexFor(e.hash, newCapacity);
- e.next = newTable[i];
- newTable[i] = e;
- e = next;
- }
- }
- }
在複制的時候數組的索引int i = indexFor(e.hash, newCapacity);重新參與計算
- 靜态内部類Holder的源碼：
/**
* holds values which can't be initialized until after VM is booted.
* 控制一些資料在VM啟動之前不能初始化
*/
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.當表容量溢出時使用備用雜湊演算法。
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
//擷取系統變量jdk.map.althashing.threshold，擷取備用雜湊演算法門檻值，預設為-1
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
//初始化門檻值
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
//如果門檻值為-1，則禁用備用雜湊演算法
if (threshold == -) {
threshold = Integer.MAX_VALUE;
}
if (threshold < ) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
//初始化備用雜湊演算法門檻值
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
很多文章講到這裡都是直接跳過，本人也是看得雲裡霧裡，怎麼莫名其妙的蹦出這麼個東西，好像在源碼中也沒多大用處，沒錯，它是沒多大用，至少對于目前的我們這種菜雞來說，因為它涉及到了一種JDK1.7新加入的雜湊演算法：
sun.misc.Hashing.stringHash32((String) k)
，針對String類型的key，提供一個新的hash算法處理hashcode分布以減少沖突，這個算法是不穩定的，還在實驗階段，預設情況下是關閉的，要想啟用這個新特性，需要手動設定
jdk.map.althashing.threshold
為非負數（預設為-1），這一點可以從Holder源碼中看出。
這有另一個關于String類更新的介紹：一個新的雜湊演算法。Oracle聲稱這個新的雜湊演算法會提供更好的哈希碼分布，這将會改善一些基于哈希碼集合的性能：HashMap,Hashtable,HashSet,LinkedHashMap,LinkedHashSet,WeakHashMap和ConcurrentHashMap。不像文章開頭所說的那個改變，這些改變是實驗性的，預設是關閉的。
正如你所想那樣，這些新特性隻用于String類型的Key。如果你想啟用這個特性，你可以将系統參數
設定為非負數（預設為-1），這個值将會成為集合大小的門檻值，新的雜湊演算法将會在超越門檻值時使用。提醒一下：雜湊演算法的隻會在重算hash時改變（當沒有多餘空間的時候）。是以，如果一個集合上一次rehash時的大小為160，而jdk.map.althashing.threshold
，則新的雜湊演算法将會在集合大小到達320（大概）時啟用。jdk.map.althashing.threshold = 200
是不是已經有點感覺了？新的hash算法的使用隻有在rehash中才會用到，而這個Holder靜态内部類，隻是加載并初始化
ALTERNATIVE_HASHING_THRESHOLD
參數而已。
構造方法：
| Constructor and Description |
|---|
|
|
|
|
在這四個構造方法中，其他三個構造方法都共同調用了第三個構造方法：
//其他三種構造方法最後都指向了該構造方法
public HashMap(int initialCapacity, float loadFactor) {
//檢查初始容量是否小于0，是則抛出異常
if (initialCapacity < )
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//檢查初始容量是否大于預設最大容量值，是則重置為MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//檢查加載因子是否合法
if (loadFactor <= || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//指定加載因子
this.loadFactor = loadFactor;
//初始化門檻值
threshold = initialCapacity;
//初始化函數，裡面是空的，供子類調用
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + ,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
下面開始分析HashMap的幾個常用方法的源碼：
put方法
public V put(K key, V value) {
//檢查是否為空表，是則膨脹容量
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//檢查key是否為null,這個很熟悉吧
if (key == null)
return putForNullKey(value);
//計算key的hash值
int hash = hash(key);
//擷取bucketIndex,即在table中存放的位置
int i = indexFor(hash, table.length);
//取出該索引下的Entry，周遊單鍊
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//檢查hash碼是否相同，key是否相等
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
//該key已存在，取出對應的value并轉移
V oldValue = e.value;
//存入新的value
e.value = value;
//該方法内容為空，供子類重寫所用
e.recordAccess(this);
//傳回對應的舊value
return oldValue;
}
}
//記錄表結構修改次數；到了這裡證明，該table中并不存在該key，向表中增加Entry
modCount++;
//增加Entry
addEntry(hash, key, value, i);
//傳回空值
return null;
}
從源碼中我們可以看到，put方法進行了如下操作：
1. HashMap是在put操作的時候才開始膨脹的；
2. 然後判斷輸入的key是否為空值，如果為空則調用putForNullKey(V)設入空key（原理差不多，但需要注意，空Key都是放在table[0]裡面的）；
3. hash(key)擷取哈希碼；
4. indexFor(hash, table.length)擷取存放位置的索引；
5. 周遊table[i]，檢查是否存在，存在則覆寫并傳回舊值；
6. 不存在，準備修改表結構，先記錄次數；
7. 調用addEntry(hash, key, value, i)增加元素。
這裡面涉及到幾個函數，我們依次分析就明白了。
inflateTable :
/**
* Inflates the table.
* 膨脹表容量
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
//将指定的表容量toSize傳入，擷取大于或等于toSize的2的幂值
int capacity = roundUpToPowerOf2(toSize);
//擷取下一次膨脹的門檻值；
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + );
//建立指定容量的新表
table = new Entry[capacity];
//初始化哈希種子作為備用
initHashSeedAsNeeded(capacity);
}
為了保證表容量為2的幂，必須将當初初始化
threshold
時指定的
initialCapacity
過濾一遍，那為什麼一定要保證容量為2的幂呢？那就是資源浪費和效率的二選一了，而顯然JDK開發人員選擇了後者，後文分析到相關函數時再作介紹。下面是
roundUpToPowerOf2(toSize)
的源碼：
roundUpToPowerOf2 :
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) !=
? (Integer.bitCount(number) > ) ? rounded << : rounded
: ;
return rounded;
}
先來理一下思路：
- 判斷number是否大于
MAXIMUM_CAPACITY
MAXIMUM_CAPACITY
- 擷取nubmer中的1出現的最高位（待會細講）賦給rounded，若rounded等于零，傳回1，否則進入第三步；
-
擷取number的1位出現的次數，若大于1，則rounded左移一位 （保證為2的幂），否則rounded為1，傳回rounded；
是以不管結果如何，最後該函數傳回的都是2的幂值。下面介紹第二步和第三步涉及到的Integer相關函數。
Integer
(已經了解了？直接跳過。)
highestOneBit (int)
//該函數實作擷取指定int數的二進制數中1出現的最高位
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> );
i |= (i >> );
i |= (i >> );
i |= (i >> );
i |= (i >> );
return i - (i >>> );
}
WTF?!又見位運算，高大上啊有沒有！但是有沒有一臉懵逼的感覺？好吧，快告訴我不是隻有我才這麼無聊去研究這個是怎麼實作的。先來個簡單的4bit運算，假設有個數 i=0110,我們來最笨的方法一位一位的移動:
有沒有看明白？它其實就是通過不斷的右移，再與原數i做或運算，重複以上步驟，得到一個自1的最高位到最低位都是1的數，如上面的0111，然後再拿它來和它的右移1位(無符号右移)得到的值做減運算，進而得到我們最終想要的結果：自1的最高位之後的所有低位都是0的數，如上面的0100。而我們的int的長度始終都是4個位元組，也就是32bit，是以上面要進行31位的右移操作。還有疑惑的話不妨動手試一試就明白了。
bitCount (int)
//該函數實作統計指定int數的二進制數中1出現的的次數。
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> ) & );
i = (i & ) + ((i >>> ) & );
i = (i + (i >>> )) & ;
i = i + (i >>> );
i = i + (i >>> );
return i & ;
}
這又是什麼鬼？簡直喪心病狂！這裡面用到了“分治”思想（如果不想看的也可以直接跳過本段），要統計32位數中1出現的次數，需要逐漸分組并組内求和得到對應位的數，每次分組的位數加倍，以2位一組作為起始統計：
先來分析一下第一行代碼：i = i - ((i >>> 1) & 0x55555555);
假設有個數 0xBC637EFF:1011 1100 0110 0011 0111 1110 1111 1111
進行第一次分組運算，每2位一組：
可以看出已經達到了我們想要的效果，那開發人員到底是怎麼想到的呢？我也不知道[尴尬]，在這裡我就說說我的了解吧。請結合上圖了解下面分析
- (i >>> 1)先将i無符号右移，則每2位中的高位移向低位，我們的目的是在這基礎上再将每2位中的高位置0（此時的高位為原每2位中的低位）；
- (i >>> 1)& 0x55555555：将每2位中的高位置0；
-
此時将出現以下結果：
1011 1100 0110 0011 0111 1110 1111 1111 [i]
0101 0100 0001 0001 0001 0101 0101 0101 [(i>>1)&0x55555555]
對比之下不難發現，上一行減下一行剛好是原數中每2位中1出現的次數。我們拿出最高的2位出來比較就很明顯了：
10
01 ：此數的高位永遠為0，而低位則是上一行的高位，上下兩數之差必等于上一行中1出現的次數。
這其實等價于i = (i& 0x55555555) + ((i >>> 1) & 0x55555555)，這樣更好了解，把原i和0x55555555相與過濾掉每2位中的高位，這樣就隻剩下低位了，而(i >>> 1) & 0x55555555又把高位移到了低位，兩個數相加同樣等于1出現的次數。了解了這個，後面就不難了解了吧，原理都是一樣的。
下面了分析
inflateTable(int)
函數裡面涉及到的第二個函數：
initHashSeedAsNeeded
/**
* Initialize the hashing mask value. We defer initialization until we
* really need it.
* 初始化哈希掩碼值。我們延遲初始化它直到我們需要它的時候。
*/
final boolean initHashSeedAsNeeded(int capacity) {
//檢查目前備用雜湊演算法狀态，hashSeed初始值為0
boolean currentAltHashing = hashSeed != ;
//檢查是否需要啟用備用雜湊演算法
//一般情況下，capacity小于Holder.ALTERNATIVE_HASHING_THRESHOLD，是以該值為false
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//進行異或判斷，一般情況下為switching為false
boolean switching = currentAltHashing ^ useAltHashing;
//若switching=true,則進行以下操作
if (switching) {
//若useAltHashing=true，傳回随機hashSeed,否則傳回0；
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: ;
}
return switching;
}
這個方法用于決定是否啟用新的hash算法，他被兩個方法所調用：
- inflateTable(int toSize)
- resize(int newCapacity)
hash
final int hash(Object k) {
int h = hashSeed;
//檢測hash種子的狀态，決定是否啟用新的hash算法。
if ( != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//使用舊的雜湊演算法
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
//保證hashCode 不同的算法，看不懂就随緣啦，太兇殘了
h ^= (h >>> ) ^ (h >>> );
return h ^ (h >>> ) ^ (h >>> );
}
indexFor
/**
* Returns index for hash code h.
* 傳回該hashcode在table中對應的索引
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";保證表容量必須為2的幂。
//hashcode在table中對應的索引
return h & (length-);
}
這裡就是需要保證容量必須為2的幂的原因，因為length為2的幂的話，length-1剛好就是索引範圍：[0,length),形成左閉右開區間，而又恰巧每一個有效位都為1，例如：
Capacity=16
則length=16， 二進制為0000 0000 0000 0000 0000 0000 0001 0000
lenght-1 =15，二進制為0000 0000 0000 0000 0000 0000 0000 1111
那麼通過
h & (length-1)
得到的就是key在表中的索引位置。
h & (length-1)
與
h%length
等價不等效，位運算的速度和效率是非常高的，這就是容量必須為2的幂的原因。
接下來就是周遊Entry單鍊了，這個應該很好了解，Entry是以單鍊的形式存在的，用于解決hash碰撞時的存放問題。最後就是addEntry()，向表中插入元素，内容拉的有點長，可以點下錨點跳至put源碼整理一下思路，現在再去看應該一目了然了吧。接下來基本上沒什麼難度了，讀懂源碼的表面意思就ok。
addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
//檢查存放元素的數量是否大于或等于門檻值，該bucketIndex下的表位置是否不為空
if ((size >= threshold) && (null != table[bucketIndex])) {
//擴容至原來2倍
resize( * table.length);
hash = (null != key) ? hash(key) : ;
//重新計算索引
bucketIndex = indexFor(hash, table.length);
}
//容量充足，進入建立Entry操作
createEntry(hash, key, value, bucketIndex);
}
resize
（或者先看createEntry方法?）
//重新調整表容量
void resize(int newCapacity) {
//備份表資料
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//檢查舊表的容量是否已是最大值，是則終止擴容直接傳回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//建立空的新表
Entry[] newTable = new Entry[newCapacity];
//轉移表資料，第二個參數決定是否重算hash碼
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//新表覆寫舊表
table = newTable;
//計算下一次調整的門檻值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
}
transfer
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//周遊table中的Entry
for (Entry<K,V> e : table) {
//周遊Entry單鍊
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? : hash(e.key);
}
//重新計算索引
int i = indexFor(e.hash, newCapacity);
//置空e.next。将table[i]的空引用指派給e.next，此時Entry連結清單中隻有一個e。
//也就是這裡，會觸發多線程并發問題
e.next = newTable[i];
//将e放入新table[i]中；
newTable[i] = e;
//将next連結清單指派給e，繼續循環周遊。
e = next;
}
}
}
這裡的後半部分可能比較難以了解，其實就是先把Entry從一個拖家帶口的家庭裡抽出來，單獨放到新的table中的過程，目的就是想讓表中的元素盡量單獨存在于表中，而不是以多個單鍊的形式存在，進而提高HashMap的性能。畫了個圖助于了解，醜了點，湊合看吧。。。
多線程并發問題
那麼這就牽扯到了多線程并發問題了，我在源碼注釋中也提到，e.next = newTable[i]
，就是問題所在，這裡将該索引下的Entry元素單鍊處理成單個元素，那麼連結清單之後的元素就是null
了，而恰巧你在此刻又進行了get操作，又很恰巧你的Entry元素在被處理掉的連結清單中，那麼他get到的還是原table中的資料，自然也就拿不到資料了，就會報空指針異常。最後一句
也是，假如你get的元素恰巧是之前這個e，而此刻e又被next頂掉了，同樣也會報空指針異常。e = next
createEntry
(跳回resize源碼)
void createEntry(int hash, K key, V value, int bucketIndex) {
//初始化索引為bucketIndex的表位置
Entry<K,V> e = table[bucketIndex];
//初始化Entry，可能會引發多線程并發問題
table[bucketIndex] = new Entry<>(hash, key, value, e);
//元素加1
size++;
}
多線程并發問題
Entry是一個連結清單結構，如果在 new Entry<>(hash, key, value, e)
了解一下Entry的内部結構：
Entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
//展現了entry的連結清單特性
Entry<K,V> next;
int hash;
/**
* Creates new entry.
* 将新new的entry插入到舊entry的鍊頭
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//省略展示部分方法
}
- 好了，到這裡我們put方法所涉及到的所有操作都分析完了。下面來分析get方法。
get
public V get(Object key) {
//檢測是否為空key
if (key == null)
return getForNullKey();
//擷取相應的Entry
Entry<K,V> entry = getEntry(key);
//檢查entry是否為空，是則傳回null；否則傳回對應的value
return null == entry ? null : entry.getValue();
}
getEntry
final Entry<K,V> getEntry(Object key) {
//檢查表中元素數量
if (size == ) {
return null;
}
//檢測key是否為空，是則傳回0；否則傳回key的hash碼
int hash = (key == null) ? : hash(key);
//根據hash碼和表長度擷取索引，從table中取出entry
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//檢測hash是否相同，key的記憶體位址是否相等，key是否為null，key的equals方法傳回值是否為true（之是以要比較這個是因為可以通過重寫equals實作兩個不同記憶體位址的對象傳回true值）。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//傳回entry
return e;
}
return null;
}
總結
本文重在梳理HashMap内部實作原理，至于HashMap的多線程問題，可以通過以下方式解決：
- 在包含HashMap的方法中實作同步機制，效率太低
- 外部包裝：
Map<K,V> map = Collections.synchronizedMap(new HashMap<K,V>());
- HashTable，效率太低
- 使用JDK1.5中引進的
Concurrent
ConcurrentHashMap
寫在最後
到這裡HashMap的一些常用方法源碼就分析完了，其中也提到了有關可能引發多線程并發問題的所在，摸清了這個資料結構，以後用起來也就胸有成竹了，當然，有興趣的同學也可以嘗試去寫自己的Map結構，在這裡就不再贅述了。相信如果已經了解了上面的内容，那麼閱讀HashMap的其他源碼并不是什麼難事，加油吧少年！