簡單介紹
HashMap基于哈希表，它實現(xiàn)了Map接口，以鍵值對形式存儲數(shù)據(jù)，是Java程序員最常用的集合之一。它的鍵key不可重復(fù)但可以為null，值value可以重復(fù)可以為null，元素存取無序，并且存儲元素時如果已經(jīng)有該鍵會采用新值覆蓋舊值的策略。
HashMap采用的數(shù)據(jù)結(jié)構(gòu)
由于HashMap是基于哈希表實現(xiàn)的，而哈希表隨著數(shù)據(jù)的增加一定會有哈希沖突問題（鴿巢原理），解決哈希沖突的方式主要有兩種：
開放地址法：產(chǎn)生哈希沖突時，重新探測一個新的空閑位置，將其插入，適用于數(shù)據(jù)量小的情況
拉鏈法：產(chǎn)生哈希沖突時，在沖突位置建立鏈表，并將其插入鏈表
HashMap采用拉鏈法解決哈希沖突，他的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表（JDK1.8后采用數(shù)組+鏈表+紅黑樹）
下面是它的實現(xiàn)代碼，在JDK1.8之前是Entry內(nèi)部類，JDK1.8后因為引入了紅黑樹變?yōu)榱薔ode內(nèi)部類?？梢钥吹剿拿恳粋€節(jié)點都有key,value,指向下一個節(jié)點的next，還有hash（這個hash是為了便于進(jìn)行比較，在后邊的代碼中可以看到）
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
? ? ? ? final int hash;
? ? ? ? final K key;
? ? ? ? V value;
? ? ? ? Node<K,V> next;
}
Hash算法
哈希表結(jié)構(gòu)中哈希算法尤為重要，首先不能太復(fù)雜，太復(fù)雜光計算就消耗太多的計算時間，其次生成的索引值要盡可能隨機并且分布均勻。那么HashMap的哈希算法是如何設(shè)計的？
下面截取了HashMap在JDK1.7和1.8版本下put()的部分源代碼
JDK1.7
public V put(K key, V value) {
? ? // ...
? ? int hash = hash(key.hashCode());
? ? int i = indexFor(hash, table.length);
? ? // ...
}
static int hash(int h) {
? ? h ^= (h >>> 20) ^ (h >>> 12);
? ? return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
? ? return h & (length-1);
}
JDK1.8
public V put(K key, V value) {
? ? return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
? ? // ...
? ? if ((p = tab[i = (n - 1) & hash]) == null)
? ? ? ? tab[i] = newNode(hash, key, value, null);
? ? // ...
}
static final int hash(Object key) {
? ? int h;
? ? return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
兩者比較可以看出有一些共同點
元素hash的計算采用的是JDK自帶的hashcode()+移位操作；
數(shù)組索引的計算采用的都是hash & (length - 1)。
這和我們傳統(tǒng)的認(rèn)知是不一樣的，我們先前計算數(shù)組散列后索引都是用%取余操作，那么HashMap為什么要用&與運算呢？而且還是和length - 1？
我們使用幾組數(shù)據(jù)進(jìn)行測試：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
假設(shè)hash結(jié)果為0101 0101（只截取了后8位），數(shù)組長度采用默認(rèn)長度16，那么length-1就是0000 1111
h : 0101 0101
15: 0000 1111
& : 0000 0101? 散列索引為5,屬于[0, 15]區(qū)間 √
結(jié)果貌似是對的，但是為什么呢？這是一個巧合嗎？
我發(fā)現(xiàn)length-1后，他的高28位全為0，低四位全為1，而根據(jù)&操作特性，他的結(jié)果中高28位肯定為0，
而低四位就是hash的低四位，那么索引結(jié)果就是hash的低四位，而低四位的區(qū)間剛好就是[0, 15]。
好吧，看來結(jié)果是對的！
但是我還注意到，在數(shù)組長度前有一行注釋，說長度必須是2的冪次？這又是為什么呢？
我接著測試...
hash結(jié)果還為0101 0101，數(shù)組長度長度為17，那么length-1就是0001 0000
h : 0101 0101
16: 0001 0000
& : 0001 0000? 散列索引為16，屬于[0，16]區(qū)間 √
這個結(jié)果是對的，但是我發(fā)現(xiàn)一個問題：length-1的低四位一直為0，那計算結(jié)果中低四位肯定為0；
再看高位，高位只會產(chǎn)生兩種結(jié)果（第27位是0/1），這樣肯定不行的，散列結(jié)果只能是0/16。
我沒有發(fā)現(xiàn)什么規(guī)律，那么下一組數(shù)據(jù)...
h : 0101 0101
31: 0001 1111
& : 0001 0101? 散列索引為21，屬于[0，31]區(qū)間 √
我發(fā)現(xiàn)了，length-1的二進(jìn)制表示中，如果高位全是0，低位全是1，可以奏效！
那么反過來看，length必須是1xxx的，這剛好就是2的冪次表示。
OK，這也就解釋了為什么table數(shù)組要求長度為2的冪次
解析put()源代碼
JDK1.7：null鍵直接放置在下標(biāo)0處；非null鍵計算下標(biāo)索引，使用頭插法插入到下標(biāo)索引對應(yīng)的鏈表中。中間發(fā)現(xiàn)相同鍵，新值替換舊值，當(dāng)容量超出HashMap閾值擴容為原長度的2倍
public V put(K key, V value) {?
? ? ? ? // 鍵為null，將元素放置到table數(shù)組的0下標(biāo)處
? ? ? ? if (key == null)?
? ? ? ? ? ? return putForNullKey(value);
? ? ? ? // 計算hash和數(shù)組下標(biāo)索引位置
? ? ? ? int hash = hash(key.hashCode());?
? ? ? ? int i = indexFor(hash, table.length);?
? ? ? ? // 根據(jù)索引找到鏈表，當(dāng)hash一致,鍵一致，說明該鍵已存在，使用新值替換舊值并返回
? ? ? ? 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;?
? ? }
? ? 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++;?
? ? ? ? // 插入到數(shù)組下標(biāo)為0位置
? ? ? ? addEntry(0, null, value, 0);?
? ? ? ? return null;?
? ? }
? ? void addEntry(int hash, K key, V value, int bucketIndex) {
? ? ? ? Entry<K, V> e = table[bucketIndex];
? ? ? ? // 頭插法：將新創(chuàng)建的Entry放入bucketIndex索引處，并且新Entry指向原來的
? ? ? ? table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
? ? ? ? // 計數(shù)，擴容
? ? ? ? if (size++ >= threshold)
? ? ? ? ? ? resize(2 * table.length);
? ? }
JDK1.8：計算數(shù)組索引下標(biāo)，如果索引下標(biāo)對應(yīng)table[index]為null，直接插入；不為null，如果是紅黑樹節(jié)點就插入紅黑樹；如果是鏈表，就使用尾插法插入鏈表末尾。中間發(fā)現(xiàn)相同鍵，新值替換舊值，當(dāng)容量超出HashMap閾值擴容為原長度的2倍
public V put(K key, V value) {
? ? return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
? ? ? ? ? ? ? boolean evict) {
? ? Node<K,V>[] tab; Node<K,V> p; int n, i;
? ? // table數(shù)組未初始化或長度為0，初始化、擴容（resize()既初始化又?jǐn)U容）
? ? if ((tab = table) == null || (n = tab.length) == 0)
? ? ? ? n = (tab = resize()).length;
? ? // 計算數(shù)組索引下標(biāo)，如果為null直接插入（寫的太簡潔了。。。）
? ? if ((p = tab[i = (n - 1) & hash]) == null)
? ? ? ? tab[i] = newNode(hash, key, value, null);
? ? else {
? ? ? ? Node<K,V> e; K k;
? ? ? ? // 當(dāng)hash一致,鍵一致，說明該鍵在table中已存在，使用e保存（后邊會實現(xiàn)新舊值替換邏輯）
? ? ? ? if (p.hash == hash &&
? ? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? e = p;
? ? ? ? // 鍵不存在，并且如果為紅黑樹節(jié)點，插入紅黑樹
? ? ? ? else if (p instanceof TreeNode)
? ? ? ? ? ? e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
? ? ? ? else {
? ? ? ? ? ? // 鍵不存在，并且如果為鏈表，插入鏈表
? ? ? ? ? ? for (int binCount = 0; ; ++binCount) {
? ? ? ? ? ? ? ? if ((e = p.next) == null) {
? ? ? ? ? ? ? ? ? ? // 使用尾插法：將元素插入到鏈表末尾
? ? ? ? ? ? ? ? ? ? /* 為什么1.7用頭插法，1.8用尾插法？
? ? ? ? ? ? ? ? ? ? 我想應(yīng)該是在1.8中引入了紅黑樹，在判斷是否樹化時有一個鏈表長度閾值，這個長度要一個個遍歷，既然是要一個個遍歷的話，就直接在尾部插入就好。而在1.7中他是不需要走到鏈表尾部的，采用頭插法效率更高
? ? ? ? ? ? ? ? ? ? */
? ? ? ? ? ? ? ? ? ? p.next = newNode(hash, key, value, null);
? ? ? ? ? ? ? ? ? ? // 如果鏈表長度達(dá)到樹化閾值，轉(zhuǎn)化為紅黑樹
? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? // 如果遍歷鏈表時，發(fā)現(xiàn)鏈表中存在該鍵，退出（后邊會實現(xiàn)新舊值替換邏輯）
? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? p = e;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 新舊值替換邏輯，和1.7一樣
? ? ? ? if (e != null) { // existing mapping for key
? ? ? ? ? ? V oldValue = e.value;
? ? ? ? ? ? if (!onlyIfAbsent || oldValue == null)
? ? ? ? ? ? ? ? e.value = value;
? ? ? ? ? ? afterNodeAccess(e);
? ? ? ? ? ? return oldValue;
? ? ? ? }
? ? }
? ? ++modCount;
? ? // 計數(shù)，擴容
? ? if (++size > threshold)
? ? ? ? resize();
? ? afterNodeInsertion(evict);
? ? return null;
}
解析get()源代碼
JDK1.7: null鍵去table[0]下找；非null鍵，根據(jù)key計算對應(yīng)數(shù)組索引下標(biāo)，遍歷鏈表，找到相同鍵返回，沒有返回null
public V get(Object key) {
? ? // 鍵為null時，調(diào)用getForNullKey
? ? if (key == null)
? ? ? ? return getForNullKey();
? ? // 計算hash值?
? ? int hash = hash(key.hashCode());
? ? // 計算數(shù)組下標(biāo)索引，遍歷鏈表
? ? for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
? ? ? ? Object k;
? ? ? ? // key相同，返回對應(yīng)value
? ? ? ? if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
? ? ? ? ? ? return e.value;
? ? }
? ? // 沒有該鍵，返回null
? ? return null;
}
JDK1.8: 根據(jù)key計算對應(yīng)數(shù)組索引位置，先比較數(shù)組元素，匹配的話直接返回；不匹配，遍歷其樹結(jié)構(gòu)或鏈表，找到后返回該節(jié)點，找不到返回null
public V get(Object key) {
? ? Node<K,V> e;
? ? return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
? ? Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
? ? // 賦值，獲取數(shù)組下標(biāo)索引對應(yīng)節(jié)點first
? ? if ((tab = table) != null && (n = tab.length) > 0 &&
? ? ? ? (first = tab[(n - 1) & hash]) != null) {
? ? ? ? // table[index]節(jié)點剛好就是要找的
? ? ? ? if (first.hash == hash && // always check first node
? ? ? ? ? ? ((k = first.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? return first;
? ? ? ? // 不是table[index]對應(yīng)元素，遍歷其鏈表或樹
? ? ? ? if ((e = first.next) != null) {
? ? ? ? ? ? // 首節(jié)點是tree類型，遍歷樹
? ? ? ? ? ? if (first instanceof TreeNode)
? ? ? ? ? ? ? ? // 找到返回樹節(jié)點
? ? ? ? ? ? ? ? return ((TreeNode<K,V>)first).getTreeNode(hash, key);
? ? ? ? ? ? // 遍歷鏈表，找到后返回鏈表節(jié)點
? ? ? ? ? ? do {
? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ? return e;
? ? ? ? ? ? } while ((e = e.next) != null);
? ? ? ? }
? ? }
? ? // 找不到，返回null
? ? return null;
}
以上就是我的一些個人見解，如有誤，還請大家指正?。。?/p>
