Map是一個"Key Value"數(shù)據(jù)結(jié)構(gòu)的集合，在Java企業(yè)級項目里使用頻率非常高，僅次于List。
Map大家族里面成員非常多，有HashMap，TreeMap，LinkedHashMap，ConcurrentHashMap等等，這里重點(diǎn)聊一下HashMap和ConcurrentHashMap。
HashMap
HashMap的存儲結(jié)構(gòu)是基于數(shù)組+鏈表組成的，不過在jdk1.8之后有了一定的改變，當(dāng)鏈表達(dá)到一定的長度就會轉(zhuǎn)變成紅黑樹。HashMap在存儲數(shù)據(jù)的時候有三個基本概念：
| 名稱 | 說明 |
|---|---|
| table | 存儲所有節(jié)點(diǎn)的數(shù)組 |
| slot | 哈希槽，即table[i]這個位置 |
| bucket | 哈希桶，table[i]上所有元素的集合 |
如下圖所示，每一個紫色箭頭指向的即是哈希槽，它僅僅是一個位置的標(biāo)識。哈希桶即是哈希槽上形成的鏈表或樹上所有元素的集合。那么我們可以得知一個Map的size大小就等于所有哈希桶的元素總和。
hashMap存儲結(jié)構(gòu)圖
HashMap如何存放數(shù)據(jù)
HashMap里面每一個元素都是一個Node類型，JDK1.8之前每一個元素是Map.Entry類型，它和Node的屬性是一樣的。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
......
}
其中key和value就是我們存放鍵值對對應(yīng)的屬性，next屬性鏈接鏈表的下一個元素，hash是HashMap的hash方法通過每一個對象的hashcode值位移運(yùn)算計算出來的。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我們再來看一下hashMap的核心方法put，put方法邏輯其實(shí)比較容易理解，大概就是判斷這個元素放到什么位置，table容量是否需要擴(kuò)容，存放元素。
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;
//1、判斷hash桶是否為空，為空的話就初始化一個桶
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2、根據(jù)當(dāng)前key的hash值計算出這個元素所存放的hash槽是否為空，為空就直接新建一個元素存放進(jìn)去
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//3、如果該hash槽不為空就走下面的邏輯
else {
Node<K,V> e; K k;
//4、判斷是否有hash沖突已經(jīng)key值是否相等，如果key值相等就直接復(fù)制給臨時變量，并統(tǒng)一放到后面處理
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//5、判斷當(dāng)前桶是否是紅黑樹結(jié)構(gòu)，如果是的話就以紅黑數(shù)的方式寫入數(shù)據(jù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//6、當(dāng)前桶如果不是紅黑樹就存放到桶內(nèi)最后一個元素的末尾形成鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//7.判斷當(dāng)前鏈表的長度是否大于等于閾值，是的話就把鏈表轉(zhuǎn)換成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//8.判斷傳入的key是否存在，存在的話就直接覆蓋
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//9.判斷是否需要擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap如何獲取數(shù)據(jù)
HashMap獲取數(shù)據(jù)邏輯比較簡單，看一下get方法。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1、判斷table里面是否有數(shù)據(jù)，有數(shù)據(jù)就走下面的邏輯如果沒有直接返回null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 2、判斷hash槽的第一個元素的hash值和key是否一致，一致就直接返回hash槽的第一個元素
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//3、判斷hash槽內(nèi)的結(jié)構(gòu)是否是紅黑數(shù)，是的話就以紅黑樹的方式取數(shù)據(jù)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//4、否則迭代鏈表，找到對應(yīng)的元素并返回
do {
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap如何擴(kuò)容
通常HashMap擴(kuò)容邏輯是復(fù)雜且耗時的，所以通常在初始化一個HashMap的時候按照預(yù)計插入的數(shù)據(jù)量設(shè)置一個初始容量initialCapacity是一個不錯的選擇。
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
那么設(shè)置多大的容量比較合適呢，我們可以看一下resize方法。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
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;
......
可以看到傳入的初始化容量initialCapacity并不會直接使用，而是調(diào)用tableSizeFor方法轉(zhuǎn)換成一個為2的N次冪的數(shù)newCap，然后當(dāng)HashMap的size大于newCap * loadFactor(默認(rèn)是0.75)的時候就會進(jìn)行擴(kuò)容。例如initialCapacity是10那么最終HashMap的初始容量就是16，當(dāng)HashMap的size大于12(16 * 0.75)的時候就進(jìn)行第一次擴(kuò)容。initialCapacity是1000那么最終HashMap的初始容量就是1024，當(dāng)HashMap的size大于768(1024 * 0.75)的時候就進(jìn)行第一次擴(kuò)容。
所以可以得出結(jié)論，你HashMap初始化可以設(shè)置為(需要存儲的元素個數(shù) / 負(fù)載因子) +1，例如你需要存7個元素那么應(yīng)該設(shè)置map的初始值為7/0.75 +1 = 10。然后通過tableSizeFor方法的轉(zhuǎn)換HashMap初始的initialCapacity就會變成16，這就大大減少了擴(kuò)容的幾率。
ConcurrentHashMap
考慮到線程并發(fā)安全性 ConcurrentHashMap 是比 HashMap 更加推薦的一種哈希式集合。其底層的數(shù)據(jù)結(jié)構(gòu)依然是數(shù)組+鏈表+紅黑數(shù)。JDK8對ConcurrentHashMap進(jìn)行了脫胎換骨的改造，不再使用分段鎖Segment來保證線程安全問題。進(jìn)而使用的是CAS加synchronized來保證線程安全。
ConcurrentHashMap初始化容量
ConcurrentHashMap初始化容量的邏輯和HashMap略有不同。ConcurrentHashMap會把存入的初始容量加上其1/2然后再加上1，進(jìn)而再通過tableSizeFor方法轉(zhuǎn)換成一個2的N冪的數(shù)。這樣初始化數(shù)組的的值會比HashMap要大，避免了哈希碰撞。
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
ConcurrentHashMap是如何存放數(shù)據(jù)
ConcurrentHashMap會先初始化出一個數(shù)組，元素會優(yōu)先插入到數(shù)組的槽點(diǎn)中，如果槽點(diǎn)有元素就鎖住該槽點(diǎn)存放元素。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//第一次put數(shù)據(jù)的時候會線初始化一個table，再繼續(xù)循環(huán)存入第一數(shù)據(jù)
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//f 即為當(dāng)前 key 定位出的槽點(diǎn)位置，如果為空表示當(dāng)前槽點(diǎn)位置可以寫入數(shù)據(jù)，利用 CAS 嘗試寫入，失敗則自旋保證成功。
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//進(jìn)行cas操作，不斷嘗試把數(shù)據(jù)插入進(jìn)去
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//判斷是否屬于遷移狀態(tài)，是的話則輔助遷移
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//如果該槽點(diǎn)有值，就鎖住該槽點(diǎn)在后面插入元素
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//判斷鏈表數(shù)量是否大于閾值，則轉(zhuǎn)換成紅黑樹
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
ConcurrentHashMap如何取出數(shù)據(jù)
get的邏輯相對比較簡單，通過hashcode來尋址，如果直接在hash槽找到數(shù)據(jù)就直接返回，如果在hash桶里就根據(jù)鏈表遍歷或紅黑樹遍歷來查找數(shù)據(jù)。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap如何更新元素數(shù)量
ConcurrentHashMap主要由兩個屬性來存儲元素數(shù)量，baseCount和counterCells。
private transient volatile long baseCount;
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
private transient volatile CounterCell[] counterCells;
- 當(dāng)并發(fā)量比較小的時候，優(yōu)先使用CAS的方式直接更新
baseCount。 - 當(dāng)更新
baseCount沖突，則會通過啟用counterCells減少線程競爭，通過CAS的方式把總數(shù)更新情況記錄在counterCells對應(yīng)的位置上。 - 如果更新
counterCells上的某個位置出現(xiàn)了多次失敗，則會通過擴(kuò)容counterCells的方式減少沖突。 - 當(dāng)
counterCells處在擴(kuò)容期間時，會嘗試更新baseCount值。
對于元素總數(shù)的統(tǒng)計邏輯就很簡單了，用baseCount加上各counterCells內(nèi)的數(shù)據(jù)就可以得到ConcurrentHashMap總元素值，完全不需要加鎖。
