HashMap是Java裡基本的存儲Key、Value的一個數據類型,了解它的內部實現,可以幫我們編寫出更高效的Java代碼。
本文主要分析JDK1.7中HashMap實現,JDK1.8中的HashMap已經和這個不一樣了,後面會再總結。
HashMap根據鍵的hashCode值獲取存儲位置,大多數情況下可以直接定位到它的值,因而具有很快的訪問速度,但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null,允許多條記錄的值為null。HashMap非線程安全,即任一時刻可以有多個線程同時寫HashMap,可能會導致數據的不一致。如果需要滿足線程安全,可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力,或者使用ConcurrentHashMap。
HashMap的存儲結構如下圖所示:
HashMap根據鍵的hashCode值和HashMap裡數組的大小取余,余數即為該Key存儲的數組位置。
如:一個Key的hashCode為15,HashMap的Size為6,15 % 6 = 3,所以該Key存儲在數組的第三個位置。
考慮另一種情況,如果一個Key的hashCode為21,那21 % 6 = 3,所以該Key也存儲在數組的第三個位置,這樣豈不是重復了?
所以對於在同一個位置的Key,HashMap把他們存儲在一個單向鏈表裡,新的Key永遠在最前面。
如果這個數組裡存儲的太滿,HashMap還有擴容機制。
下面我們分析HashMap的源代碼,來看看數據是怎麼存儲的。
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);
//根據key的hash值和table.length計算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;
}
}
//修改的次數加一,用於迭代HashMap時,判斷HashMap元素有沒有修改
modCount++;
//添加key
addEntry(hash, key, value, i);
return
null
;
}
private
void
inflateTable(
int
toSize) {
//根據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
);
}
關鍵方法Integer.highestOneBit((number - 1) << 1),這個方法的結果就是求出大於給定數值的,最小的2的N次方。
解釋之前先說明幾個概念:
<< : 按二進制形式把所有的數字向左移動對應的位數,高位移出(捨棄),低位的空位補零。在數字沒有溢出的前提下,對於正數和負數,左移一位都相當於乘以2的1次方,左移n位就相當於乘以2的n次方;
>>: 按二進制形式把所有的數字向右移動對應位移位數,低位移出(捨棄),高位的空位補符號位,即正數補零,負數補1。右移一位相當於除2,右移n位相當於除以2的n次方。
>>>: 無符號右移,忽略符號位,空位都以0補齊
我們拿數字10做示例,經過(number - 1) << 1 = 18,二進制表示為:10010
i |= (i >> 1) 即:10010 | 01001 = 11011
i |= (i >> 2) 即:11011 | 00110 = 11111
i |= (i >> 4) 即:11111 | 00001 = 11111
……
其實這幾步就是把i的最高位1之後的所有位都變成1
然後 i – (i >>> 1) 即:11111-01111=10000(16)
這步是把最高位,之後的都變成0,這樣就求出了最接近10的2的N次方(16)
至於為什麼要不數組的Size設置為2的N次方,我們後面說。
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
);
}
根據上面的注釋,我們可以看出,HashMap中使用的hash值,不是Key直接的hashCode,而是經過一系列計算的。
計算hash值的作用就是避免hash碰撞,盡量減少單向鏈表的產生,因為鏈表中查找一個元素需要遍歷。
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
);
}
第一次看到這個方法很是不理解,不是應該用 h % length嗎?其實這裡用了一個非常巧妙的方法來取這個余數。
在計算機中CPU做除法運算、取余運算耗費的CPU周期都比較長,一般幾十個CPU周期,而位移運算、位運算只用一個CPU周期。
這樣對於性能要求高的地方,就可以用位運算代替普通的除法、取余等運算,JDK源碼中有很多這樣的例子。
為了能夠使用位運算求出這個余數,length必須是2的N次方,這也是我們上面初始化數組大小時要求的,然後使用 h & (length-1),就可以求出余數。具體的算法推導,請自行搜索。
我們用個例子來說明下,如一個Key經過運算的hash為21,length為16:
直接取余運算:21 % 16 = 5
位運算:10101(21) & 01111(16-1) = 00101(5)
哇,這就是計算機運算的魅力,這就是算法的作用。
void
addEntry(
int
hash, K key, V value,
int
bucketIndex) {
//如果size大於等於threshold,且數組的這個位置不為null,則擴容數組
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實際可以存儲的Key的個數,如果size大於threshold,說明HashMap已經太飽和了,非常容易發生hash碰撞,導致單向鏈表的產生。
在inflateTable方法中,我們可以看到
01threshold = (
int
) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +
1
);
所以這個值是由HashMap的capacity 和負載因子(loadFactor默認:0.75)計算出來的。
loadFactor越小,相同的capacity就更頻繁地擴容,這樣的好處是HashMap會很大,產生hash碰撞的幾率就更小,但需要的內存也更多,這就是所謂的空間換時間。
在這裡也注意,擴容時會直接將原來容量乘以2,滿足了length為2的N次方的條件。
createEntry就不多說了,就是將key、value保存到數組響應的位置。
final
Entry<K,V> getEntry(Object key) {
if
(size ==
0
) {
return
null
;
}
//用和添加時相同的算法求出hash值
int
hash = (key ==
null
) ?
0
: hash(key);
//直接從數組的響應位置拿到數據,判斷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
;
}
獲取時非常簡單,也非常迅速,添加時做的所有工作都是為快速獲取做的工作。
HashMap是一個非常高效的Key、Value數據結構,GET的時間復雜度為:O(1) ~ O(n),我們在使用HashMap時需要注意以下幾點:
1. 聲明HashMap時最好使用帶initialCapacity的構造函數,傳入數據的最大size,可以避免內部數組resize;
2. 性能要求高的地方,可以將loadFactor設置的小於默認值0.75,使hash值更分散,用空間換取時間;