資訊專欄INFORMATION COLUMN
摘要：如果當前桶為紅黑樹，那就要按照紅黑樹的方式寫入數據。否則判斷桶的第一個位置有可能是鏈表紅黑樹的是否為查詢的，是就直接返回。從這兩個核心方法可以看出中對大鏈表做了優化，修改為紅黑樹之后查詢效率直接提高到了。如果數量大于則要轉換為紅黑樹。
前言
Map 這樣的 Key Value 在軟件開發中是非常經典的結構，常用于在內存中存放數據。
本篇主要想討論 ConcurrentHashMap 這樣一個并發容器，在正式開始之前我覺得有必要談談 HashMap，沒有它就不會有后面的 ConcurrentHashMap。
HashMap眾所周知 HashMap 底層是基于 數組 + 鏈表 組成的，不過在 jdk1.7 和 1.8 中具體實現稍有不同。
Base 1.71.7 中的數據結構圖：
先來看看 1.7 中的實現。
這是 HashMap 中比較核心的幾個成員變量；看看分別是什么意思？
初始化桶大小，因為底層是數組，所以這是數組默認的大小。
桶最大值。
默認的負載因子（0.75）
table 真正存放數據的數組。
Map 存放數量的大小。
桶大小，可在初始化時顯式指定。
負載因子，可在初始化時顯式指定。
重點解釋下負載因子：
由于給定的 HashMap 的容量大小是固定的，比如默認初始化：
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();
}
給定的默認容量為 16，負載因子為 0.75。Map 在使用過程中不斷的往里面存放數據，當數量達到了 16 * 0.75 = 12 就需要將當前 16 的容量進行擴容，而擴容這個過程涉及到 rehash、復制數據等操作，所以非常消耗性能。
因此通常建議能提前預估 HashMap 的大小最好，盡量的減少擴容帶來的性能損耗。
根據代碼可以看到其實真正存放數據的是
transient Entry
這個數組，那么它又是如何定義的呢？
Entry 是 HashMap 中的一個內部類，從他的成員變量很容易看出：
key 就是寫入時的鍵。
value 自然就是值。
開始的時候就提到 HashMap 是由數組和鏈表組成，所以這個 next 就是用于實現鏈表結構。
hash 存放的是當前 key 的 hashcode。
知曉了基本結構，那來看看其中重要的寫入、獲取函數：
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;
}
判斷當前數組是否需要初始化。
如果 key 為空，則 put 一個空值進去。
根據 key 計算出 hashcode。
根據計算出的 hashcode 定位出所在桶。
如果桶是一個鏈表則需要遍歷判斷里面的 hashcode、key 是否和傳入 key 相等，如果相等則進行覆蓋，并返回原來的值。
如果桶是空的，說明當前位置沒有數據存入；新增一個 Entry 對象寫入當前位置。
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++;
}
當調用 addEntry 寫入 Entry 時需要判斷是否需要擴容。
如果需要就進行兩倍擴充，并將當前的 key 重新 hash 并定位。
而在 createEntry 中會將當前位置的桶傳入到新建的桶中，如果當前桶有值就會在位置形成鏈表。
get 方法再來看看 get 函數：
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;
}
首先也是根據 key 計算出 hashcode，然后定位到具體的桶中。
判斷該位置是否為鏈表。
不是鏈表就根據 key、key 的 hashcode 是否相等來返回值。
為鏈表則需要遍歷直到 key 及 hashcode 相等時候就返回值。
啥都沒取到就直接返回 null 。
Base 1.8不知道 1.7 的實現大家看出需要優化的點沒有？
其實一個很明顯的地方就是：
當 Hash 沖突嚴重時，在桶上形成的鏈表會變的越來越長，這樣在查詢時的效率就會越來越低；時間復雜度為 O(N)。
因此 1.8 中重點優化了這個查詢效率。
1.8 HashMap 結構圖：
先來看看幾個核心的成員變量：
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 大體上都差不多，還是有幾個重要的區別：
TREEIFY_THRESHOLD 用于判斷是否需要將鏈表轉換為紅黑樹的閾值。
HashEntry 修改為 Node。
Node 的核心組成其實也是和 1.7 中的 HashEntry 一樣，存放的都是 key value hashcode next 等數據。
再來看看核心方法。
put 方法看似要比 1.7 的復雜，我們一步步拆解：
判斷當前桶是否為空，空的就需要初始化（resize 中會判斷是否進行初始化）。
根據當前 key 的 hashcode 定位到具體的桶中并判斷是否為空，為空表明沒有 Hash 沖突就直接在當前位置創建一個新桶即可。
如果當前桶有值（ Hash 沖突），那么就要比較當前桶中的 key、key 的 hashcode 與寫入的 key 是否相等，相等就賦值給 e,在第 8 步的時候會統一進行賦值及返回。
如果當前桶為紅黑樹，那就要按照紅黑樹的方式寫入數據。
如果是個鏈表，就需要將當前的 key、value 封裝成一個新節點寫入到當前桶的后面（形成鏈表）。
接著判斷當前鏈表的大小是否大于預設的閾值，大于時就要轉換為紅黑樹。
如果在遍歷過程中找到 key 相同時直接退出遍歷。
如果 e != null 就相當于存在相同的 key,那就需要將值覆蓋。
最后判斷是否需要進行擴容。
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 。
否則判斷桶的第一個位置(有可能是鏈表、紅黑樹)的 key 是否為查詢的 key，是就直接返回 value。
如果第一個不匹配，則判斷它的下一個是紅黑樹還是鏈表。
紅黑樹就按照樹的查找方式返回值。
不然就按照鏈表的方式遍歷匹配返回值。
從這兩個核心方法（get/put）可以看出 1.8 中對大鏈表做了優化，修改為紅黑樹之后查詢效率直接提高到了 O(logn)。
但是 HashMap 原有的問題也都存在，比如在并發場景下使用時容易出現死循環。
