JDK1.7 HashMap 源碼分析

發(fā)布時間：2016年12月14日作者：文章轉(zhuǎn)自網(wǎng)絡(luò)，版權(quán)歸原作者所有，反饋可立刻刪除 (該文來自筆記，點(diǎn)擊查看原文)

概述

HashMap是Java里基本的存儲Key、Value的一個數(shù)據(jù)類型，了解它的內(nèi)部實(shí)現(xiàn)，可以幫我們編寫出更高效的Java代碼。

本文主要分析JDK1.7中HashMap實(shí)現(xiàn)，JDK1.8中的HashMap已經(jīng)和這個不一樣了，后面會再總結(jié)。

正文

HashMap概述

HashMap根據(jù)鍵的hashCode值獲取存儲位置，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。

HashMap的存儲結(jié)構(gòu)如下圖所示：

HashMap根據(jù)鍵的hashCode值和HashMap里數(shù)組的大小取余，余數(shù)即為該Key存儲的數(shù)組位置。

如：一個Key的hashCode為15，HashMap的Size為6，15 % 6 = 3，所以該Key存儲在數(shù)組的第三個位置。

考慮另一種情況，如果一個Key的hashCode為21，那21 % 6 = 3，所以該Key也存儲在數(shù)組的第三個位置，這樣豈不是重復(fù)了？

所以對于在同一個位置的Key，HashMap把他們存儲在一個單向鏈表里，新的Key永遠(yuǎn)在最前面。

如果這個數(shù)組里存儲的太滿，HashMap還有擴(kuò)容機(jī)制。

下面我們分析HashMap的源代碼，來看看數(shù)據(jù)是怎么存儲的。

PUT

public V put(K key, V value) {

//判斷如果table為空，則初始化table

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

if (key == null)

return putForNullKey(value);

//計算key的hash值

int hash = hash(key);

//根據(jù)key的hash值和table.length計算KEY的位置

int i = indexFor(hash, table.length);

//判斷是否有重復(fù)的值，若有，則用新值替換舊值，并返回舊值

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;

}

//修改的次數(shù)加一，用于迭代HashMap時，判斷HashMap元素有沒有修改

modCount++;

//添加key

addEntry(hash, key, value, i);

return null;

}

inflateTable — 初始化HashMap內(nèi)部數(shù)組

private void inflateTable(int toSize) {

//根據(jù)toSize計算容量，即大于toSize的最小的2的n次方

int capacity = roundUpToPowerOf2(toSize);

………

}

private static int roundUpToPowerOf2(int number) {

// assert number >= 0 : "number must be non-negative";

return number >= MAXIMUM_CAPACITY

? MAXIMUM_CAPACITY

: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;

}

public static int highestOneBit(int i) {

// HD, Figure 3-1

i |= (i >> 1);

i |= (i >> 2);

i |= (i >> 4);

i |= (i >> 8);

i |= (i >> 16);

return i - (i >>> 1);

}

關(guān)鍵方法Integer.highestOneBit((number - 1) << 1)，這個方法的結(jié)果就是求出大于給定數(shù)值的，最小的2的N次方。

解釋之前先說明幾個概念：

<< : 按二進(jìn)制形式把所有的數(shù)字向左移動對應(yīng)的位數(shù)，高位移出(舍棄)，低位的空位補(bǔ)零。在數(shù)字沒有溢出的前提下，對于正數(shù)和負(fù)數(shù)，左移一位都相當(dāng)于乘以2的1次方，左移n位就相當(dāng)于乘以2的n次方；

>>: 按二進(jìn)制形式把所有的數(shù)字向右移動對應(yīng)位移位數(shù)，低位移出(舍棄)，高位的空位補(bǔ)符號位，即正數(shù)補(bǔ)零，負(fù)數(shù)補(bǔ)1。右移一位相當(dāng)于除2，右移n位相當(dāng)于除以2的n次方。

>>>: 無符號右移，忽略符號位，空位都以0補(bǔ)齊

我們拿數(shù)字10做示例，經(jīng)過(number - 1) << 1 = 18,二進(jìn)制表示為：10010

i |= (i >> 1) 即：10010 | 01001 = 11011

i |= (i >> 2) 即：11011 | 00110 = 11111

i |= (i >> 4) 即：11111 | 00001 = 11111

……

其實(shí)這幾步就是把i的最高位1之后的所有位都變成1

然后 i – (i >>> 1) 即：11111-01111=10000(16)

這步是把最高位，之后的都變成0，這樣就求出了最接近10的2的N次方（16）

至于為什么要把數(shù)組的Size設(shè)置為2的N次方，我們后面說。

hash — 計算Key的hash值

final int hash(Object k) {

int h = hashSeed;

if (0 != 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).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

根據(jù)上面的注釋，我們可以看出，HashMap中使用的hash值，不是Key直接的hashCode，而是經(jīng)過一系列計算的。

計算hash值的作用就是避免hash碰撞，盡量減少單向鏈表的產(chǎn)生，因為鏈表中查找一個元素時間復(fù)雜度為O(n)。

indexFor — 計算Key所對應(yīng)的數(shù)組位置

static int indexFor(int h, int length) {

// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

return h & (length-1);

}

第一次看到這個方法很是不理解，不是應(yīng)該用 h % length嗎？其實(shí)這里用了一個非常巧妙的方法來取這個余數(shù)。

在計算機(jī)中CPU做除法運(yùn)算、取余運(yùn)算耗費(fèi)的CPU周期都比較長，一般幾十個CPU周期，而位移運(yùn)算、位運(yùn)算只用一個CPU周期。
這樣對于性能要求高的地方，就可以用位運(yùn)算代替普通的除法、取余等運(yùn)算，JDK源碼中有很多這樣的例子。

為了能夠使用位運(yùn)算求出這個余數(shù)，length必須是2的N次方，這也是我們上面初始化數(shù)組大小時要求的，然后使用 h & (length-1)，就可以求出余數(shù)。具體的算法推導(dǎo)，請自行搜索。

我們用個例子來說明下，如一個Key經(jīng)過運(yùn)算的hash為21，length為16：

直接取余運(yùn)算：21 % 16 = 5

位運(yùn)算：10101(21) & 01111(16-1) = 00101(5)

哇，這就是計算機(jī)運(yùn)算的魅力，這就是算法的作用。

addEntry — 添加數(shù)據(jù)

void addEntry(int hash, K key, V value, int bucketIndex) {

//如果size大于等于threshold，且數(shù)組的這個位置不為null，則擴(kuò)容數(shù)組

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);

}

threshold：HashMap實(shí)際可以存儲的Key的個數(shù)，如果size大于threshold，說明HashMap已經(jīng)太飽和了，非常容易發(fā)生hash碰撞，導(dǎo)致單向鏈表的產(chǎn)生。

在inflateTable方法中，我們可以看到

01	`threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +` `1);`

所以這個值是由HashMap的capacity 和負(fù)載因子（loadFactor默認(rèn)：0.75）計算出來的。

loadFactor越小，相同的capacity就更頻繁地擴(kuò)容，這樣的好處是HashMap會很大，產(chǎn)生hash碰撞的幾率就更小，但需要的內(nèi)存也更多，這就是所謂的空間換時間。

在這里也注意，擴(kuò)容時會直接將原來容量乘以2，滿足了length為2的N次方的條件。

createEntry就不多說了，就是將key、value保存到數(shù)組相應(yīng)的位置。

GET

final Entry<K,V> getEntry(Object key) {

if (size == 0) {

return null;

}

//用和添加時相同的算法求出hash值

int hash = (key == null) ? 0 : hash(key);

//直接從數(shù)組的響應(yīng)位置拿到數(shù)據(jù)，判斷hash相同、key相同，則返回

for (Entry<K,V> e = table[indexFor(hash, table.length)];

e != null;

e = e.next) {

Object k;

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

}

return null;

}

獲取時非常簡單，也非常迅速，添加時做的所有工作都是為快速獲取做的工作。

總結(jié)

HashMap是一個非常高效的Key、Value數(shù)據(jù)結(jié)構(gòu)，GET的時間復(fù)雜度為：O(1) ~ O(n)，我們在使用HashMap時需要注意以下幾點(diǎn)：

1. 聲明HashMap時最好使用帶initialCapacity的構(gòu)造函數(shù)，傳入數(shù)據(jù)的最大size，可以避免內(nèi)部數(shù)組resize；
2. 性能要求高的地方，可以將loadFactor設(shè)置的小于默認(rèn)值0.75，使hash值更分散，用空間換取時間；

分類導(dǎo)航

JDK1.7 HashMap 源碼分析

概述

正文

HashMap概述

PUT

inflateTable — 初始化HashMap內(nèi)部數(shù)組

hash — 計算Key的hash值

indexFor — 計算Key所對應(yīng)的數(shù)組位置

addEntry — 添加數(shù)據(jù)

GET

總結(jié)

延伸閱讀

我想了解如何學(xué)習(xí)