很多剛學(xué)Java的同學(xué)們都知道HashMap，平常一般使用玲销，可能并不知道它的工作原理镐捧，前段時間有為剛畢業(yè)的同事在使用HashMap的時候碰到了個問題找我，問題大概是這樣的：
Map map = new HashMap();
map.put(1l, "abc");
System.out.println(map.get(1));
明明有值啊循诉，為什么是null呢毁习？
下面我們一起來探討一下HashMap的工作原理及實現(xiàn)，首先看個例子指孤，帶著問題去研究
public class TestMap {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<String, Integer>();
map.put(null, 0);
map.put("java", 1);
map.put("c++", 2);
map.put("python", 3);
map.put("php", 4);
map.put("nodejs", 5);
for(Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
System.out.println("php".hashCode() == "c++".hashCode());
}
}
運(yùn)行結(jié)果是：
null: 0
php: 4
c++: 2
java: 1
nodejs: 5
false
讓我們來看一下 HashMap 中的幾個參數(shù)的意義
- loadFactor : 負(fù)載因子 默認(rèn)0.75
initialCapacity : 初始化容量16，最大是（1 << 30）1073741824
table : Entry<K,V>[] table 是用來存儲數(shù)據(jù)的數(shù)組
Entry<K,V> 是HashMap的一個內(nèi)部類逆粹，鏈表結(jié)構(gòu)
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
...
}
既然table是用來存儲數(shù)據(jù)的，那么例子中我們往map放了六條數(shù)據(jù)炫惩，table中應(yīng)該就有六條數(shù)據(jù)對吧僻弹。細(xì)心的同學(xué)可能發(fā)現(xiàn)了上圖table中只有四條，table[0]他嚷，table[7]蹋绽，table[10]，table[12]數(shù)據(jù)筋蓖，還有兩條數(shù)據(jù)去哪了呢卸耘？而且打印結(jié)果也是六條數(shù)據(jù)。是不是eclipse有bug啊粘咖，還有兩條數(shù)據(jù)沒顯示出來蚣抗。 再仔細(xì)一看為什么“c++”這條數(shù)據(jù)跑到了table[7]的next去了，那null這條數(shù)據(jù)呢瓮下？看來不是eclipse的bug(尷尬的表情)翰铡，那原因是什么呢？
我們先來看看執(zhí)行put()的時候到底做了什么讽坏？大概瀏覽一下源碼
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
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;
}
執(zhí)行過程大致是這樣的：
先對table的非空檢查,為空就初始化
對key的非空檢查锭魔，如果key是null，會被存儲到table[0]路呜，因為null的hash值總是0
對key的hashCode()做hash迷捧，然后再通過indexFor()計算index,這個就是table數(shù)組的索引;
如果在剛才計算出來的索引位置中table沒有元素，直接把Entry對象放在那個索引上
如果索引上有元素胀葱，然后會進(jìn)行迭代漠秋，在迭代的過程中，會調(diào)用equals()方法來檢查key的相等性(key.equals(k))抵屿，如果這個方法返回true膛堤，它就會用當(dāng)前Entry的value來替換之前的value。如果返回false就一直到Entry->next是null晌该，把當(dāng)前的Entry對象變成鏈表的下一個節(jié)點(diǎn)
如果table的長度超過了loadFactor *current capacity肥荔，就要重新resize一個原來長度兩倍的HashMap
到這里就恍然大悟了，剛才“c++”為什么會跑到table[7]中了朝群，原來“PHP”和“c++”的hashCode()做hash燕耿，然后再通過indexFor()計算出來的index都是7，但是“php”和“c++”并不equals姜胖，所以這兩條數(shù)據(jù)就形成一個鏈表存在table[7]中誉帅。至于null那條數(shù)據(jù)去哪了，大家應(yīng)該也知道了。
那get()方法呢蚜锨？
當(dāng)你理解了hashmap的put的工作原理档插，理解get的工作原理就非常簡單了。當(dāng)你傳遞一個key從hashmap總獲取value的時候：
對key進(jìn)行null檢查亚再。如果key是null郭膛，table[0]這個位置的元素將被返回。
key的hashcode()方法被調(diào)用氛悬，然后計算hash值则剃。
indexFor(hash,table.length)用來計算要獲取的Entry對象在table數(shù)組中的精確的位置，使用剛才計算的hash值如捅。在獲取了table數(shù)組的索引之后棍现，會迭代鏈表，調(diào)用equals()方法檢查key的相等性镜遣，如果equals()方法返回true己肮，get方法返回Entry對象的value，否則悲关，返回null谎僻。
總結(jié)：
- HashMap中數(shù)據(jù)是用一個叫table的數(shù)組來存的，table的索引在邏輯上叫做“桶”(bucket)坚洽，它存儲了鏈表的第一個元素戈稿。
- HashMap有一個叫做Entry的內(nèi)部類西土，它用來存儲key-value對讶舰。table數(shù)組存的就是它。Entry用一個next屬性實現(xiàn)多個Entry以單向鏈表存放需了，插入元素時跳昼，如果兩條Key落在同一個桶，并且這兩條key不equals,后入桶的Entry將next指向桶當(dāng)前的Entry肋乍，否則后入桶的會將前面的給覆蓋（確保key的唯一性）;
- 使用HashMap的時候最好使用泛型鹅颊，如果key放的是自己的對象，最好重寫equals()和hashcode()墓造。
百度找了一張形象點(diǎn)的HashMap結(jié)構(gòu)圖（無恥）
由上圖可以看出哈希表是一個數(shù)組+鏈表的存儲結(jié)構(gòu)堪伍。HashMap存儲結(jié)構(gòu)文字解釋：
table[0] →[index=1,Entry<K,V>]
table[1] →[index=2,Entry<K,V>]
...
依次類推
