JDK1.7的HashMap的put(key, value)原始碼剖析

摘要： 目錄 HashMap的put操作原始碼解析 HashMap的put操作原始碼解析 1、官方文件 1.1、繼承結構 java.lang.Object java.util.AbstractMap<K,V> java.util.Has...

目錄

• HashMap的put操作原始碼解析

HashMap的put操作原始碼解析

1、官方文件

1.1、繼承結構

java.lang.Object
java.util.AbstractMap<K,V>
java.util.HashMap<K,V>

1.2、型別引數：

K - 此對映所維護的鍵的型別
V - 所對映值的型別

2、put(key, value)

HashMap 是一種以 鍵——值 對的形式來儲存資料的資料結構。 HashMap 允許使用 null 值和 null 鍵，它並不能保證你存放資料和取出的順序是一致的。

接下來就以下面的程式碼來看一下 put 是怎麼將資料存放到 map 中的。

public class HashMapTest {
public static void main(String[] args) {
Map<String, Object> map = new HashMap<String, Object>();
map.put(null, "map-value");
map.put(map-key", "map-value");

System.out.println(map);
}
}

2.1、重點原始碼部分擷取

在 map.put() 這裡打個斷點 F5(我用的eclipse) 跟蹤進去。我們就會進到 put 方法中：

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

這裡的 EMPTY_TABLE 是 HashMap 的一個靜態常量，是一個Entry陣列，預設值是空陣列， table 是 HashMap 的一個屬性且其預設值就是 EMPTY_TABLE ，這個table也就是我們資料存放的地方，至此為止可以知道，HashMap其實是一個數組，但它又不是一個純粹的陣列。下面會進行解釋。

static final Entry<?,?>[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

而這個 Entry 其實是HashMap的一個內部類，定義如下(僅擷取部分程式碼)，記住這個類，記住這個構造方法：它在 new Entry 的時候接收了一個 Entry 物件，並將自己的 next 指向了傳入的 Entry 物件形成一個連結串列，其自身是表頭。

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;

Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}

從上面我們可以看出來這個 Entry 其實是一個連結串列，它存放了 key 和 value 並且還有一個指向下一個節點的引用 Entry ， 剩下的這個 hash 就是 key 的雜湊值。

現在我們可以捋一捋HashMap的結構了。首先 HashMap 是一個 Entry 陣列，而這個 Entry 是一個單向連結串列，我們大致可以將其結構畫成如下圖所示：

2.2、put(key, value)原始碼分析

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}

if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

1. 因為我們在例項化HashMap的時候使用的是無參構造方法，所以第一次 put 資料的時候 table 為空

if (table == EMPTY_TABLE) {
inflateTable(threshold); 
}

上面這段程式碼會被執行， inflateTable(threshold) 會將 table 初始化為一個長度為 16 的 Entry 陣列。

1. 它會對我們的 key 進行空判斷，如果是空就會執行下面的程式碼：

if (key == null)
return putForNullKey(value);

putForNullKey(value) 的實現如下：

private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

2.2.1 、 key 為 null 的情況

從上面可以看出來，如果 key 為 null 的話，它會從 table 中取出下標為0也就是第一個元素，沒忘記的話我們應該還知道它一個 Entry ，是一個連結串列，如果這個元素不是 null ，那麼就會遍歷這個連結串列，並判斷當前這個 Entry 節點物件的 key 是不是 null 。

1. 如果是 null ( key 相同了)： 使用 oldValue 來存放當前這個 Entry 節點物件的 value ，然後將我們新的值( map-value )賦給當前節點，再將原值 oldValue 返回回去。
2. 如果遍歷完連結串列的所有節點都沒有找到 key 為 null 的節點就會呼叫 addEntry(0, null, value, 0) ，這個方法前面的 if(){***} 這塊程式碼是判斷當前table是否要進行擴容。這裡只做簡單講述。
   size 是當前 table 存放的Entry連結串列的個數，拿我上面畫的那個 HapshMap 結構來看就是4。
   如果我們例項化HashMap的時候沒有給大小那麼： threshold = loadFactor (負載因子預設為 0.75f ) * DEFAULT_INITIAL_CAPACITY (HashMap預設大小也就是table長度為 16 )，所以 threshold = 12 。
   如果我們給了大小為 initialCapacity ，那麼負載因子還是預設的 0.75f ，但是threshold不需要算了，值就是 initialCapacity 。如果我們同時給了 HashMap 的大小 initialCapacity 和負載因子 loadFactor ，那麼 HashMap 就使用我們給定的負載因子值作為新的負載因子，給定的 HashMap 大小作為 threshold 。ok第一個條件結束。
   null != table[bucketIndex] 就很好理解了，就是我當前這個節點要存放的位置是空的。
   滿足上面兩個條件， HashMap 就會進行擴容，擴容後的大小為擴容前的2倍，然後對 key 重新計算它的 hash 值以及陣列下標。
3. 繼續 put 內容，從上面原始碼我們可以知道 key 為 null 的情況下它的 hash 值是0，至於 bucketIndex 的計算是這樣的 h & (length-1) ，也是將 hash 值與 table 的長度按位相與值也是。至此也就是確定了 key 為 null 的這個節點將存放在table的第一個位置上。然後就會呼叫 createEntry(0, null, "map-value", 0);
4. 在 createEntry(int hash, K key, V value, int bucketIndex) 這個方法裡首先拿到 table 中下標為 bucketIndex 的連結串列的表頭： Entry<K,V> e = table[bucketIndex]; 然後再用 Entry 物件的構造方法 new 一個 Entry 將我們的 hash 值， key ， value ，連結串列的表頭作為引數傳入： table[bucketIndex] = new Entry<>(hash, key, value, e); 就這樣我們的這個新節點就放在了原來的表頭的前面作為新的表頭了。沒看懂的再回到上面看一下 Entry 的構造方法，我有重點標註的。

2.2.2、 key 不為 null 的情況

原始碼依舊拿下來

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}

if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

1. 首先說一下 hash 值：對於相同的 key 它們的 hash 值是相同的。但是 hash 值相同，它們的 key 卻不一定是相同的，這就是雜湊碰撞。
2. key 不為 null 的話它會根據 key 算出這個 key 對就的 hash 值以及它的 bucketIndex ，然後拿到 table 中下標為 bucketIndex 的這個 Entry 連結串列，然後遍歷這個連結串列，判斷當前節點的 hash 其實也就是當前節點的 key 的 hash 是否等於我們傳入的 map-key 的 hash ，然後判斷當前節點的 key 是否與我們傳入的 key 相同。
   如果以上條件都滿足了，那麼就是 key 相同了，就會跟 Key 為 null 的分析中的第一條一樣將新值覆蓋舊值，並將舊值返回回去。
   如果遍歷完這個連結串列以上條件沒有得到滿足，那麼就會跟 key 為 null 的分析中的第四條一樣，獲得 table 下標為 i 的連結串列的表頭 e ，然後將我們的 map-key , map-value , hash 以及表頭 e 作為引數 new 一個新的 Entry 物件並將它的 next 指向原來的表頭 e ，它也就變成了新的表頭了。

3、完結

最怕你的能力配不上你的野心。