前言
需要知道的是幢泼，HashMap在Java8里發(fā)生了比較大的變化。在Java8中劲腿，table的桶（bucket）中旭绒，每個(gè)桶跟之前一樣，是維護(hù)一個(gè)鏈表焦人。但是如果鏈表大小超過閾值（TREEIFY_THRESHOLD=8）挥吵，鏈表就會(huì)被改造為紅黑樹結(jié)構(gòu)。
這是因?yàn)榛ㄍ郑诖罅縣ash碰撞下忽匈，Map就會(huì)被弱化為類似鏈表的結(jié)構(gòu)（全部存在一個(gè)bucket中），這樣會(huì)大大降低性能矿辽。在超過閾值以后丹允，改為紅黑樹的方式，可以提高查找性能袋倔。
本文最下方還介紹了 LinkedHashMap 和 TreeMap 的區(qū)別雕蔽。
Map整體結(jié)構(gòu)
Map通常被包含在集合框架里，但是Map并不繼承自 Collection 接口宾娜，最底層接口是Map批狐。
類的繼承結(jié)構(gòu)可以參考下圖：
HashMap和HashTable區(qū)別
- 最主要區(qū)別在于線程安全，HashMap不是線程安全的前塔，而HashTable是線程安全的嚣艇。
hashtable內(nèi)部添加了synchronized關(guān)鍵字來確保線程同步。而HashMap沒有华弓，因此性能上來說食零，HashMap會(huì)相對(duì)高一些。
我們平時(shí)使用一般情況下是用HashMap寂屏，而如果要在多線程情況下使用HashMap贰谣，可以使用Collections.synchronizedMap()來獲取一個(gè)線程安全的集合娜搂。
Collections.synchronizedMap() 的實(shí)現(xiàn)原理是，Collections內(nèi)部定義了一個(gè)SynchronizedMap的內(nèi)部類冈爹，這個(gè)類實(shí)現(xiàn)了Map接口涌攻，使用synchronized關(guān)鍵字在復(fù)寫的方法中實(shí)現(xiàn)線程安全，然后操作傳入的實(shí)例對(duì)象频伤。
//以下是Collections.SynchronizedMap 內(nèi)部的put方法實(shí)現(xiàn)
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
HashMap可以使用null作為key，而HashTable不允許這樣做芝此。
雖然HashMap支持null作為key憋肖，但一般不建議這樣做。因?yàn)檫@樣做比較坑╮(╯▽╰)╭婚苹。另外HastTable已經(jīng)不建議在代碼中使用岸更，如果需要線程安全的場(chǎng)景，建議使用ConcurrentHashMap
順便說一下膊升，如果HashMap以null作為key的話怎炊，Entry節(jié)點(diǎn)對(duì)象總是存在table數(shù)組的第一個(gè)節(jié)點(diǎn)上
HashMap是對(duì)Map接口的實(shí)現(xiàn)，HashTable在實(shí)現(xiàn)了Map接口的同時(shí)廓译，繼承了Dictionary抽象類评肆。
這倆都實(shí)現(xiàn)了 Map Coneable 和 Serializable 接口，但是沒有實(shí)現(xiàn)Collection接口非区。
構(gòu)造器有兩個(gè)可選參數(shù)：
int initialCapacity, float loadFactor瓜挽。分別表示初始容量 和，加載因子征绸。
兩個(gè)默認(rèn)的加載因子都是0.75久橙。如果容量達(dá)到荷載因子*size的話，就要進(jìn)行擴(kuò)容(resize)管怠，擴(kuò)容的同時(shí)要重新計(jì)算每個(gè)元素在新數(shù)組中的位置淆衷，因此性能開銷較大。
HashMap的初始容量是16渤弛，擴(kuò)容時(shí)按2的指數(shù)冪擴(kuò)容祝拯。
HashTable的初始容量是11，擴(kuò)容時(shí)按2的指數(shù)冪+1擴(kuò)容
而關(guān)于加載因子為什么選用0.75
Hash表為解決沖突暮芭，可以使用開放地址法和鏈地址法來解決鹿驼，Java的HashTable采用了鏈地址法，即數(shù)組+鏈表辕宏。荷載因子就是一個(gè)特別重要的參數(shù)畜晰，應(yīng)該嚴(yán)格限制在0.7~0.8以下。超過0.8查表時(shí)CPU緩存不命中概率將按照指數(shù)級(jí)上升瑞筐，嚴(yán)重降低性能凄鼻。hash表的平均查找長(zhǎng)度，是關(guān)于荷載因子a的函數(shù)
-
兩者計(jì)算hash的方法不同
都是根據(jù)key進(jìn)行hash運(yùn)算后確定存儲(chǔ)地址index。
HashTable計(jì)算hash是用key的hash對(duì)數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
而hashMap為了減少Hash碰撞概率块蚌，進(jìn)行了二次hash
以下是源碼實(shí)現(xiàn)闰非。注意jdk1.7和jdk1.8的實(shí)現(xiàn)方法不一樣
//JDK1.7 方法一：
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
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);
}
//JDK1.8 方法一：
static final int hash(Object key) { //jdk1.8
int h;
// h = key.hashCode() 為第一步 取hashCode值
// h ^ (h >>> 16) 為第二步 高位參與運(yùn)算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二：
static int indexFor(int h, int length) { //jdk1.7的源碼，jdk1.8沒有這個(gè)方法峭范，但是實(shí)現(xiàn)原理一樣的
return h & (length-1); //第三步 取模運(yùn)算
}
這里要注意财松，為什么這里需要將高位數(shù)據(jù)移位到低位進(jìn)行異或運(yùn)算呢？
這是因?yàn)橛行?shù)據(jù)計(jì)算出的哈希值差異主要在高位纱控，而 HashMap 里的哈希尋址是忽略容量以上的高位的辆毡，那么這種處理就可以有效避免類似情況下的哈希碰撞。
為了分布均勻甜害，我們首先想到的就是把hash值對(duì)數(shù)組長(zhǎng)度取模運(yùn)算舶掖，這樣元素的分布相對(duì)均勻。但是取模運(yùn)算對(duì)于性能消耗還是比較大的尔店。
在HashMap中是這樣做的眨攘，調(diào)用方法二來計(jì)算index。
這個(gè)方法非常巧妙嚣州。它通過h & (table.length -1)得到該對(duì)象的保存位鲫售，而HashMap低層數(shù)組的長(zhǎng)度總是2的n次方，這是HashMap在速度上的優(yōu)化避诽。而當(dāng)length總是等2的n次方時(shí)龟虎，h & (table.length -1) 運(yùn)算等價(jià)于對(duì)length取模，也就是h%table.length沙庐，但是&操作更有效率鲤妥。
- HashMap和HashTable都是 使用鏈地址法解決Hash碰撞，使用 數(shù)組+鏈表 的方式存儲(chǔ)拱雏。（JDK1.8中鏈表改為了紅黑樹）
如果hash碰撞棉安，則會(huì)用equals()比較key到底是否相同。相同則覆蓋铸抑，如果不相同贡耽，則會(huì)放到相同的bukectIndex下面，用鏈表存儲(chǔ)下一個(gè)元素的位置鹊汛。
Entry是HashMap的一個(gè)靜態(tài)內(nèi)部類蒲赂，實(shí)現(xiàn)一個(gè)鏈表結(jié)構(gòu)，保存了之前的Enrty對(duì)象為next元素刁憋。
以下為JDK1.7的Map部分源碼滥嘴。
static class Entry<K,V> implements Map.Entry<K,V>{
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
//put源碼 JDK1.7
public V put(K key, V value) {
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;
}
//校驗(yàn)并擴(kuò)容
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);
}
//創(chuàng)建Entry節(jié)點(diǎn)，相同bucketIndex創(chuàng)建為鏈表節(jié)點(diǎn)
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++;
}
HashMap和HashTable的實(shí)現(xiàn)原理
resize()方法
由第6點(diǎn)可以看到至耻，在addEntry()方法內(nèi)若皱，每次執(zhí)行createEntry()之前镊叁，都需要校驗(yàn)一遍是否需要擴(kuò)容。
(size >= threshold) && (null != table[bucketIndex])
如果size達(dá)到了臨界值走触，并且當(dāng)前要添加的節(jié)點(diǎn)不為null晦譬。就要進(jìn)行擴(kuò)容。
具體過程為：
先創(chuàng)建一個(gè)容量為table.length*2（也就是2次方翻倍）的新table互广，修改臨界值敛腌。然后把HashMap里的所有元素根據(jù)新的length重新計(jì)算index放入新的table中。
這里要注意兜辞，是用 每個(gè)元素的hash重新計(jì)算Index迎瞧，而不是簡(jiǎn)單的把原table的index放到新table中。（因?yàn)橛?jì)算index時(shí)逸吵，是根據(jù)length長(zhǎng)度均勻分布的）所以resize()是比較消耗性能的操作。如果在創(chuàng)建map時(shí)能大概預(yù)見到大小缝裁，那么設(shè)置一個(gè)相對(duì)大點(diǎn)的初始容量是一個(gè)不錯(cuò)的選擇扫皱。
resize()源碼就不放了。JDK1.8有新實(shí)現(xiàn)hash() 和 indexFor()
hash()是方法是為了對(duì)key.hashCode()進(jìn)行二次散列捷绑，以獲得更好的散列值韩脑，減少碰撞概率。
indexFor()是根據(jù)散列值計(jì)算出存儲(chǔ)在table中的下標(biāo)粹污，與table.length取模段多。均勻分布。
LinkedHashMap 和 TreeMap
這兩種Map都可以保證某種順序壮吩，但是實(shí)現(xiàn)原理是不同的进苍。
- LinkedHashMap
提供的是遍歷順序符合插入順序，它的實(shí)現(xiàn)是通過為Entry（鍵值對(duì)）維護(hù)一個(gè)雙向鏈表鸭叙。
部分源碼如下：
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
- TreeMap
它的整體順序是由鍵來確定的觉啊，通過 Comparator 或 Comparable（自然順序）來決定。
最后說一下HashSet
內(nèi)部實(shí)現(xiàn)是一個(gè)HashMap沈贝，只不過value是一個(gè)固定對(duì)象杠人。
HashSet部分源碼如下
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
參考資料:
HashMap原理解析(較全面)
HashMap與HashTable實(shí)現(xiàn)原理淺析
Java8系列之重新認(rèn)識(shí)HashMap(深度解析)
