資訊專欄INFORMATION COLUMN
摘要：如果當(dāng)前桶為紅黑樹，那就要按照紅黑樹的方式寫入數(shù)據(jù)。否則判斷桶的第一個(gè)位置有可能是鏈表紅黑樹的是否為查詢的，是就直接返回。從這兩個(gè)核心方法可以看出中對大鏈表做了優(yōu)化，修改為紅黑樹之后查詢效率直接提高到了。如果數(shù)量大于則要轉(zhuǎn)換為紅黑樹。
前言
Map 這樣的 Key Value 在軟件開發(fā)中是非常經(jīng)典的結(jié)構(gòu)，常用于在內(nèi)存中存放數(shù)據(jù)。
本篇主要想討論 ConcurrentHashMap 這樣一個(gè)并發(fā)容器，在正式開始之前我覺得有必要談?wù)?HashMap，沒有它就不會有后面的 ConcurrentHashMap。
HashMap眾所周知 HashMap 底層是基于 數(shù)組 + 鏈表 組成的，不過在 jdk1.7 和 1.8 中具體實(shí)現(xiàn)稍有不同。
Base 1.71.7 中的數(shù)據(jù)結(jié)構(gòu)圖：
先來看看 1.7 中的實(shí)現(xiàn)。
這是 HashMap 中比較核心的幾個(gè)成員變量；看看分別是什么意思？
初始化桶大小，因?yàn)榈讓邮菙?shù)組，所以這是數(shù)組默認(rèn)的大小。
桶最大值。
默認(rèn)的負(fù)載因子（0.75）
table 真正存放數(shù)據(jù)的數(shù)組。
Map 存放數(shù)量的大小。
桶大小，可在初始化時(shí)顯式指定。
負(fù)載因子，可在初始化時(shí)顯式指定。
重點(diǎn)解釋下負(fù)載因子：
由于給定的 HashMap 的容量大小是固定的，比如默認(rèn)初始化：
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, 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;
threshold = initialCapacity;
init();
}
給定的默認(rèn)容量為 16，負(fù)載因子為 0.75。Map 在使用過程中不斷的往里面存放數(shù)據(jù)，當(dāng)數(shù)量達(dá)到了 16 * 0.75 = 12 就需要將當(dāng)前 16 的容量進(jìn)行擴(kuò)容，而擴(kuò)容這個(gè)過程涉及到 rehash、復(fù)制數(shù)據(jù)等操作，所以非常消耗性能。
因此通常建議能提前預(yù)估 HashMap 的大小最好，盡量的減少擴(kuò)容帶來的性能損耗。
根據(jù)代碼可以看到其實(shí)真正存放數(shù)據(jù)的是
transient Entry
這個(gè)數(shù)組，那么它又是如何定義的呢？
Entry 是 HashMap 中的一個(gè)內(nèi)部類，從他的成員變量很容易看出：
key 就是寫入時(shí)的鍵。
value 自然就是值。
開始的時(shí)候就提到 HashMap 是由數(shù)組和鏈表組成，所以這個(gè) next 就是用于實(shí)現(xiàn)鏈表結(jié)構(gòu)。
hash 存放的是當(dāng)前 key 的 hashcode。
知曉了基本結(jié)構(gòu)，那來看看其中重要的寫入、獲取函數(shù)：
put 方法 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 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;
}
判斷當(dāng)前數(shù)組是否需要初始化。
如果 key 為空，則 put 一個(gè)空值進(jìn)去。
根據(jù) key 計(jì)算出 hashcode。
根據(jù)計(jì)算出的 hashcode 定位出所在桶。
如果桶是一個(gè)鏈表則需要遍歷判斷里面的 hashcode、key 是否和傳入 key 相等，如果相等則進(jìn)行覆蓋，并返回原來的值。
如果桶是空的，說明當(dāng)前位置沒有數(shù)據(jù)存入；新增一個(gè) Entry 對象寫入當(dāng)前位置。
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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
當(dāng)調(diào)用 addEntry 寫入 Entry 時(shí)需要判斷是否需要擴(kuò)容。
如果需要就進(jìn)行兩倍擴(kuò)充，并將當(dāng)前的 key 重新 hash 并定位。
而在 createEntry 中會將當(dāng)前位置的桶傳入到新建的桶中，如果當(dāng)前桶有值就會在位置形成鏈表。
get 方法再來看看 get 函數(shù)：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
首先也是根據(jù) key 計(jì)算出 hashcode，然后定位到具體的桶中。
判斷該位置是否為鏈表。
不是鏈表就根據(jù) key、key 的 hashcode 是否相等來返回值。
為鏈表則需要遍歷直到 key 及 hashcode 相等時(shí)候就返回值。
啥都沒取到就直接返回 null 。
Base 1.8不知道 1.7 的實(shí)現(xiàn)大家看出需要優(yōu)化的點(diǎn)沒有？
其實(shí)一個(gè)很明顯的地方就是：
當(dāng) Hash 沖突嚴(yán)重時(shí)，在桶上形成的鏈表會變的越來越長，這樣在查詢時(shí)的效率就會越來越低；時(shí)間復(fù)雜度為 O(N)。
因此 1.8 中重點(diǎn)優(yōu)化了這個(gè)查詢效率。
1.8 HashMap 結(jié)構(gòu)圖：
先來看看幾個(gè)核心的成員變量：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
transient Node[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
和 1.7 大體上都差不多，還是有幾個(gè)重要的區(qū)別：
TREEIFY_THRESHOLD 用于判斷是否需要將鏈表轉(zhuǎn)換為紅黑樹的閾值。
HashEntry 修改為 Node。
Node 的核心組成其實(shí)也是和 1.7 中的 HashEntry 一樣，存放的都是 key value hashcode next 等數(shù)據(jù)。
再來看看核心方法。
put 方法看似要比 1.7 的復(fù)雜，我們一步步拆解：
判斷當(dāng)前桶是否為空，空的就需要初始化（resize 中會判斷是否進(jìn)行初始化）。
根據(jù)當(dāng)前 key 的 hashcode 定位到具體的桶中并判斷是否為空，為空表明沒有 Hash 沖突就直接在當(dāng)前位置創(chuàng)建一個(gè)新桶即可。
如果當(dāng)前桶有值（ Hash 沖突），那么就要比較當(dāng)前桶中的 key、key 的 hashcode 與寫入的 key 是否相等，相等就賦值給 e,在第 8 步的時(shí)候會統(tǒng)一進(jìn)行賦值及返回。
如果當(dāng)前桶為紅黑樹，那就要按照紅黑樹的方式寫入數(shù)據(jù)。
如果是個(gè)鏈表，就需要將當(dāng)前的 key、value 封裝成一個(gè)新節(jié)點(diǎn)寫入到當(dāng)前桶的后面（形成鏈表）。
接著判斷當(dāng)前鏈表的大小是否大于預(yù)設(shè)的閾值，大于時(shí)就要轉(zhuǎn)換為紅黑樹。
如果在遍歷過程中找到 key 相同時(shí)直接退出遍歷。
如果 e != null 就相當(dāng)于存在相同的 key,那就需要將值覆蓋。
最后判斷是否需要進(jìn)行擴(kuò)容。
get 方法
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)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;
}
get 方法看起來就要簡單許多了。
首先將 key hash 之后取得所定位的桶。
如果桶為空則直接返回 null 。
否則判斷桶的第一個(gè)位置(有可能是鏈表、紅黑樹)的 key 是否為查詢的 key，是就直接返回 value。
如果第一個(gè)不匹配，則判斷它的下一個(gè)是紅黑樹還是鏈表。
紅黑樹就按照樹的查找方式返回值。
不然就按照鏈表的方式遍歷匹配返回值。
從這兩個(gè)核心方法（get/put）可以看出 1.8 中對大鏈表做了優(yōu)化，修改為紅黑樹之后查詢效率直接提高到了 O(logn)。
但是 HashMap 原有的問題也都存在，比如在并發(fā)場景下使用時(shí)容易出現(xiàn)死循環(huán)。
