借鑒于[美團(tuán)點(diǎn)評(píng)技術(shù)團(tuán)隊(duì)][2]
[2]: http://tech.meituan.com/java-hashmap.html
hashMap繼承自AbstractMap抽象類
非線程安全，所以效率可能較高于Hashtable
其中鍵和值都是對(duì)象，并且不能包含重復(fù)鍵，但可以包含重復(fù)值
允許null的鍵和值
HashMap是Hashtable的輕量級(jí)實(shí)現(xiàn)
分析
HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)構(gòu)，通過(guò)key的hashCode來(lái)計(jì)算Hash值，只要HashCode相同，計(jì)算出來(lái)的值也就一樣，然后再計(jì)算數(shù)組下標(biāo)，如果多個(gè)key對(duì)應(yīng)到一個(gè)下標(biāo)，就用鏈表串起來(lái)，新插入的在前面。在jdk1.8里 加入了紅黑樹的實(shí)現(xiàn)，當(dāng)鏈表的長(zhǎng)度大于8時(shí)，轉(zhuǎn)換為紅黑樹的結(jié)構(gòu)。
20161222113920705.png
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//用于定位數(shù)組索引的位置
final K key;
V value;
Node<K,V> next;//鏈表的下一個(gè)Node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
Node是HashMap的一個(gè)內(nèi)部類，實(shí)現(xiàn)Map.Entry接口，本質(zhì)就是一個(gè)映射（鍵值對(duì)）。
//threshold是HashMap所能容納的最大數(shù)據(jù)量的Node(鍵值對(duì))個(gè)數(shù)
int threshold; // 所能容納的key-value對(duì)極限
final float loadFactor; // 負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認(rèn)負(fù)載因子
//默認(rèn)的初始容量（容量為HashMap中桶的數(shù)目）是16，且實(shí)際容量必須是2的整數(shù)次冪。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
......
else {
newCap = DEFAULT_INITIAL_CAPACITY;
//默認(rèn)使用0.75*16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
......
}
也就是說(shuō)，負(fù)載因子越大，也就是能容納的鍵值對(duì)更多。這樣空間利用率高了，但是沖突機(jī)會(huì)增大。
put方法實(shí)現(xiàn)：
put思路如下：
- 判斷鍵值對(duì)數(shù)組table是否為空或者null，否則進(jìn)行resize()擴(kuò)容操作。
- 根據(jù)鍵值key計(jì)算hash得到插入索引index，如果table為空，直接新建新節(jié)點(diǎn)，轉(zhuǎn)向步驟6判斷擴(kuò)容。
- 判斷節(jié)點(diǎn)key存在，直接覆蓋value。
- 判斷table是否為treeNode紅黑樹，如果是紅黑樹，直接在樹中插入鍵值對(duì)。
- 遍歷table,鏈表長(zhǎng)度大于8，就轉(zhuǎn)換為紅黑樹，否則進(jìn)行鏈表的插入操作,過(guò)程中發(fā)現(xiàn)相同的key直接進(jìn)行覆蓋value。
- 插入成功后，判斷實(shí)際的size是否超過(guò)了最大的容量threshold,如果超過(guò)，進(jìn)行擴(kuò)容。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
*生成hash的方法
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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是否為空，
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//創(chuàng)建一個(gè)新的table數(shù)組，并且獲取該數(shù)組的長(zhǎng)度
//根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點(diǎn)添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//如果對(duì)應(yīng)的節(jié)點(diǎn)存在
Node<K,V> e; K k;
//判斷table[i]的首個(gè)元素是否和key一樣，如果相同直接覆蓋value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對(duì)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 該鏈為鏈表
else {
//遍歷table[i]，判斷鏈表長(zhǎng)度是否大于TREEIFY_THRESHOLD(默認(rèn)值為8)，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作；遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 寫入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入成功后，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold，如果超過(guò)，進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get方法實(shí)現(xiàn)：
get思路如下：
- table中的第一個(gè)節(jié)點(diǎn)，直接取出
- 通過(guò)key.equals()去查找對(duì)應(yīng)的entry
若為鏈表，時(shí)間復(fù)雜度O(n),若為紅黑樹，則為O(logn)
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // 每次都是校驗(yàn)第一個(gè)node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 在樹中獲取
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中獲取
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
擴(kuò)容機(jī)制：
我們分析下resize的源碼，鑒于JDK1.8融入了紅黑樹，較復(fù)雜，為了便于理解我們?nèi)匀皇褂肑DK1.7的代碼，好理解一些
void resize(int newCapacity) { //傳入新的容量
Entry[] oldTable = table; //引用擴(kuò)容前的Entry數(shù)組
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改閾值為int的最大值(2^31-1)，這樣以后就不會(huì)擴(kuò)容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一個(gè)新的Entry數(shù)組
transfer(newTable); //！！將數(shù)據(jù)轉(zhuǎn)移到新的Entry數(shù)組里
table = newTable; //HashMap的table屬性引用新的Entry數(shù)組
threshold = (int)(newCapacity * loadFactor);//修改閾值
}
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了舊的Entry數(shù)組
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
Entry e = src[j]; //取得舊Entry數(shù)組的每個(gè)元素
if (e != null) {
if (e != null) {
src[j] = null;//釋放舊Entry數(shù)組的對(duì)象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對(duì)象）
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新計(jì)算每個(gè)元素在數(shù)組中的位置
e.next = newTable[i]; //標(biāo)記[1]
newTable[i] = e; //將元素放在數(shù)組上
e = next; //訪問(wèn)下一個(gè)Entry鏈上的元素
} while (e != null);
}
}
}
其他
HashMap是非線程安全的，如果想得到線程安全的HashMap，可以通過(guò)Collections類的靜態(tài)方法synchronizedMap獲得線程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());
HashMap和ConcurrentHashMap的區(qū)別
ConcurrentHashMap引入一個(gè)"分段鎖"的概念，將Map分成N個(gè)Segment,每一個(gè)Segment類似于HashTable,相當(dāng)于每一個(gè)分段都進(jìn)行了鎖保護(hù)。默認(rèn)是分成了16個(gè)。
