Java 容器類 - Map
sschrodinger
2019/03/24
參考
《算法》第四版 - Robert.S 著轩勘，謝路云 譯
AbstractMap
EntrySet
類似的，AbstractMap 實現(xiàn)了 Map 的基礎(chǔ)框架里伯，在這個框架中，最重要的類是 EntrySet 結(jié)構(gòu)敢会。Map 實現(xiàn)不支持迭代器鉴腻，EntrySet 將鍵值對包裝成一個 Set，這樣就可以對 Set 做迭代兄春，實現(xiàn)對 Map 的遍歷澎剥。
舉例來說，containsValue(Object value) 函數(shù)在內(nèi)部使用 entrySet 的迭代器遍歷整個 Map赶舆，如果找到就返回 true，否則返回 false祭饭。
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
鍵視圖和值視圖
和 List 的 subList 類似芜茵，Map 支持返回鍵視圖和值視圖。因為 Map 的值要求唯一倡蝙，而 value 不做要求九串，所以 Map 的鍵視圖采用 Set 存儲，值視圖采用 Collection 存儲寺鸥，兩個視圖如下所示：
transient Set<K> keySet;
transient Collection<V> values;
懶加載模式
所謂的懶加載模式猪钮，即在創(chuàng)建類的時候不創(chuàng)建視圖，而是在使用視圖的時候胆建，如調(diào)用 keySet() 函數(shù)時才創(chuàng)建視圖烤低。
如下，當 keySet 不為空時笆载，直接返回 keySet扑馁；如果為空，才創(chuàng)建 keySet凉驻。
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new AbstractSet<K>() {
//...
};
keySet = ks;
}
return ks;
}
受限制的視圖
和 AbstractList 的 subList 所不同的是腻要，AbstractMap 提供的鍵視圖和值視圖是受限制的視圖。我們可以在 subList 中刪除元素涝登，增加元素雄家，取決于他的原 List 可以支持哪些操作，但是 AbstractMap 的鍵視圖和值視圖只支持部分操作胀滚。
KeySet 的實現(xiàn)重寫了 AbstractSet趟济，但是在 AbstractSet 中，所有的操作都被設(shè)置成了拋出 OperationNotSupportException蛛淋，所以只有其重寫的函數(shù)和該 Map 的實現(xiàn)所綁定咙好。
下面是 AbstractMap 的 keySet 實現(xiàn)。
new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
HashMap
特性
HashMap 是平常用的最多的一個 Map 實現(xiàn)褐荷，我們列出其幾大特性：
特性
- 基于 Hash table（哈希表）的實現(xiàn)
- 提供所有 map 接口勾效，允許 null 的鍵和 null 的值
- 非線程安全
- 不保證讀取鍵值對的順序，不僅僅包括鍵值對 put 和 get 順序不同，也包括隨時間變化层宫，迭代的順序也可能不同杨伙。
- 對于基本的操作（get 和 put），可以在常數(shù)時間上完成萌腿。
HashMap 實現(xiàn)原理
散列表 的作用相當于索引限匣，通過散列表可以快速的定位元素的位置。散列表依據(jù)如何解決沖突可以劃分為多種散列表毁菱，在 HashMap 的實現(xiàn)中米死，采用單獨鏈表法解決沖突。
首先看 Hash table 的原理贮庞，簡要的概括峦筒， hash table 的思想就是分區(qū)。
一個簡化版的 hash map 如下圖所示：
對于需要保存的每一個 entry窗慎，求出其 hash 值物喷，并與 hash table 的大小做取模運算（保證每一個 hash 值都可以映射到 hash table 中），然后遮斥，將取模運算之后的 hash 值對應(yīng)的 entry 連接到 hash table 對應(yīng)的項中峦失，如果已經(jīng)有元素，則將其連接到已有元素的后面术吗。
hashMap 采用 Node 類作為其 entry 節(jié)點尉辑，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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
Node 實際上是一個鏈表節(jié)點，這樣才能實現(xiàn) hash table 的鏈表引用藐翎。
在 HashMap 的實現(xiàn)中材蹬，采用 Node 數(shù)組作為哈希表結(jié)構(gòu)。
結(jié)構(gòu)如下圖：
transient Node<K,V>[] table;
舉個例子吝镣，我們使用如下程序初始化：
private void mapTest() {
Map<String, String> stringMap = new HashMap<>();
stringMap.put("key_1", "value_1");
stringMap.put("key_2", "value_2");
stringMap.put("key_3", "value_3");
stringMap.put("key_4", "value_4");
}
初始化之后堤器，存儲的結(jié)構(gòu)如下圖所示：
我們來看 HashMap 具體怎么實現(xiàn)存儲。
put 過程
根據(jù)散列表原理末贾，對每一個加入散列表的元素都要求他的哈希值找到對應(yīng)的存儲位置闸溃。在 hashMap 中，我們使用 key 查找值拱撵，所以在散列表中辉川，只要能根據(jù) key 的 hash 值快速找到 Node 節(jié)點，就可以定位 value 值拴测，所以 hashMap 使用 key 的 hash 值作為 hash table 的索引乓旗。
以下是 put 函數(shù)的部分源代碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//onlyIfAbsent:if true, don't change existing value
//evict:if false, the table is in creation mode
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// step 1: resize if necessary
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// step 2: if no entry in current tab, create a new node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// step 3: check if first entry key equals key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else {
// step 4: this loop state search entry key equals key in s specific hash or create a new entry if no equals entry found
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// step 5: modifify if exist
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
return null;
}
最主要的函數(shù)是 putVal 函數(shù)，他把 key 的哈希值集索，key 值和 value 值最為參數(shù)屿愚，總共分為五步汇跨，如下所示：
put 步驟
- step 1：如果 table 為空或者 table 長度為 0，重新配置 table
- step 2：利用
(n - 1) & hash找到 entry 所在的鏈表頭妆距。如果鏈表頭為空穷遂，直接創(chuàng)建新節(jié)點。
- 用
n - 1和 hash 做與操作娱据，可以將結(jié)果限制在 0 到 n - 1 中蚪黑，優(yōu)點是速度快，缺點是相當于只有低位參加了 hash 的過程中剩，導致碰撞幾率增大忌穿。
- step 3：檢查鏈表頭的 key 是否等于所期望的 key。如果一致咽安，記錄當前 node
- 需要滿足兩個條件
p.hash == hash和(k = p.key) == key || (key != null && key.equals(k))
- 第一個條件指的是同一個鍵的 hash 結(jié)果應(yīng)該維持不變伴网，所以先檢查 hash 結(jié)果，如果 hash 結(jié)果不一樣妆棒，則鍵肯定不一樣（一致性）
- 第二個條件是指滿足所期望的 key 和鏈表頭的 key 為同一對象（同一內(nèi)存）或者 equal 函數(shù)相同
- step 4：遍歷鏈表，如果滿足當前遍歷的節(jié)點和期望的 key 相同沸伏，記錄當前 node糕珊，break；如果鏈表中沒有滿足要求的 node毅糟，新建節(jié)點在鏈表最后红选。
- step 5：對于 step 3 和 step 4，如果存在滿足 key 條件的節(jié)點姆另，表明在原來的鏈表中有記錄喇肋，根據(jù) onlyIfAbsent 參數(shù)決定是否更新。
get 過程
get 過程比較簡單迹辐，根據(jù) key 值遍歷 Map蝶防，如果有元素，則返回值明吩，如果沒有间学，則返回空，代碼如下：
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 && // 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<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;
}
hash 函數(shù)
因為在 get 方法時使用了 (n - 1) & hash印荔，而不是取模運算低葫，相當與只有低位參加了運算，所以碰撞幾率相當?shù)母呷月桑瑸榱藴p少碰撞幾率嘿悬，hashMap 使用了一個支持方法 hash ，將 key 值 hash 的高位和低位做與或運算水泉，使得高位也參加到 hash 的計算中善涨，減少碰撞幾率窒盐。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
resize 實現(xiàn)
每當哈希表的使用率大于 $loadFactory * capicity$ 時，會自動擴大哈希表躯概，標準是每次擴大兩倍登钥。
擴大兩倍可以很好的解決元素重新排列的問題。我們知道 hashMap 使用 $ (n - 1) \& hash$ 作為哈希和表的映射娶靡，每一個元素需要調(diào)整的位置只能是當前位置或者是當前位置加上原來容量之后的位置牧牢，高位決定了是當前位置還是兩倍之后的位置。
假設(shè)當前容量大小為 $16$($0x10000$)姿锭，某一元素的哈希值為 $44$($0x101100$)塔鳍，不考慮內(nèi)置的 hash 函數(shù)，直接將 15 和 44 做與操作呻此，那么
會得到 $0x1100$轮纫，即在原來應(yīng)該放在 12 號位。容量擴大兩倍焚鲜，實際上是對 16 向左移動了 1 位掌唾，得到 32，當和 44 做與操作時忿磅，實際上前 4 位不會變動糯彬，只有第五位可能有區(qū)別，在這個例子中葱她，做與操作仍然是放在 12 號位撩扒，當然第五位可能是 1，變成當前位置加上原來容量之后的位置吨些。這樣就不用重新計算每一個的位置搓谆，而只需要計算高位不同的 hash 值并將存放位置加上當前容量的偏移。
note
- 最大 table 長度為
$1 << 30$
代碼如下：
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;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
迭代器構(gòu)建
HashMap 的迭代器都基于抽象類 HashIterator豪墅，都是快速失敗迭代器泉手。
HashIterator 基于深度遍歷的思想，首先遍歷一個鏈表結(jié)構(gòu)但校，然后遍歷下一個鏈表結(jié)構(gòu)螃诅。
代碼如下：
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 將 next 指向第一個存在的（不為空）的鏈表
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
在 HashIterator 的基礎(chǔ)上，hashMap 實現(xiàn)了自己的兩個迭代器状囱，如下：
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
Java 1.8 性能改進
HashMap 最重要的三個參數(shù)术裸， threshold 、 loadFactor 和 capacity亭枷。
capcity 指的是 table 的大小袭艺。
loadFactory 是一個比例，指 table 的填充比例叨粘，即當 table 中的元素填充個數(shù)大于 $ capacity * loadFactor$ 時（數(shù)組中有 $ capacity * loadFactor$ 個項不為空）猾编，則擴充節(jié)點瘤睹。
不同于低版本的 HashMap 實現(xiàn)， 1.8 增加了 threshold 指的是當單鏈表的長度大于 threshold 時答倡，將單鏈表重新組合成紅黑樹形式的存儲結(jié)構(gòu)轰传，增加讀取效率。詳細原理可參見 treeMap
treeMap
特性
TreeMap 是基于紅黑樹實現(xiàn)的一個 map瘪撇，有幾大基本特性获茬。
特性
- 基于紅黑樹實現(xiàn)
- 提供所有 map 接口。
- 非線程安全
- 迭代時的順序按照鍵值排列倔既，即存儲順序是有限的（在這個基礎(chǔ)上恕曲，同時實現(xiàn)了
NavigableMap接口，用于查找某個 key 之前的所有元素等操作）- 對于 put 操作渤涌，時間復雜度是
$O(logn)$佩谣，對于增加和刪除操作，時間復雜度不能保證- 支持
SortedMap接口实蓬，如 firstKey()茸俭，lastKey()，取得最大最小的key安皱，或sub(fromKey, toKey), tailMap(fromKey) 剪取Map的某一段
TreeMap 實現(xiàn)原理
2-3 查找樹
利用樹進行查找時瓣履，希望樹盡量的平衡，這樣才能夠保證在每一次的查找保證 $O(logn)$ 的復雜度练俐。在動態(tài)插入的過程種要維持平衡二叉樹的代價太高，所以使用一種新型的平衡樹 - 2-3 查找樹冕臭。
對于一個二叉查找樹腺晾，他的每一個節(jié)點有一個值和兩條連接，左連接指向的二叉查找樹的值都小于該節(jié)點辜贵，右連接指向的二叉查找樹的值都大于該節(jié)點悯蝉，對于一個整數(shù)類型的數(shù)組 int[] a = new int[] {1,2,3,4,5,6,7}，他所構(gòu)成的平衡二叉查找樹如下所示：
現(xiàn)引入 2-3 查找樹托慨，定義如下：
定義
- 為一棵空樹或由以下節(jié)點組成
- 2-節(jié)點鼻由，含有一個值和兩條連接，左連接指向的 2-3 樹中的值都小于該節(jié)點厚棵，右連接指向的 2-3 樹的值都大于該節(jié)點（類似于查找二叉樹）
- 3-節(jié)點蕉世，含有兩個值和三條連接，左連接指向的 2-3 樹中的值都小于該節(jié)點婆硬，中連接指向的 2-3 樹的值位于該節(jié)點的兩個值之間狠轻，右連接指向的 2-3 樹的值都大于該節(jié)點
對于一個字符數(shù)組 char[] chars = new char[] {A,C,H,L,P,S,X,E,J,R,M}，他的平衡 2-3 樹如下所示：
查找
2-3 樹查找過程和二叉樹相似彬犯，略向楼。
添加
在一個只有根節(jié)點且是 2-節(jié)點的樹上添加元素查吊。為了保證平衡，我們需要將該節(jié)點替換成一個 3-節(jié)點湖蜕，如下所示：
在一個只有根節(jié)點且是 3-節(jié)點的樹上添加元素逻卖。為了保證平衡，我們需要將該節(jié)點做局部變化昭抒，操作如下：首先將該節(jié)點臨時增加一個值變成 4-節(jié)點评也，然后對四節(jié)點進行拆分，變成 3 個 2-節(jié)點戈鲁，如下所示：
在一個父節(jié)點且是 2-節(jié)點仇参，該節(jié)點是3-節(jié)點的樹上添加元素。為了保證平衡婆殿，我們需要將該節(jié)點做局部變化诈乒，操作如下：首先將該節(jié)點臨時增加一個值變成 4-節(jié)點，然后對四節(jié)點進行拆分婆芦，變成 3 個 2-節(jié)點怕磨，最后將一個 2-節(jié)點 和 父節(jié)點合并，如下所示：
在一個父節(jié)點是 3-節(jié)點消约，該節(jié)點是3-節(jié)點的樹上添加元素肠鲫。為了保證平衡，我們需要將該節(jié)點做局部變化或粮，操作如下：首先將該節(jié)點臨時增加一個值變成 4-節(jié)點导饲，然后對四節(jié)點進行拆分，變成 3 個 2-節(jié)點氯材，最后將一個 2-節(jié)點 和 父節(jié)點合并然后遞歸的對父節(jié)點進行操作渣锦，直到根節(jié)點或者父節(jié)點是 2-節(jié)點停止，如下所示：
刪除
參見 mengzhisuoliu 博客
由此可見氢哮， 2-3 樹是由下向上生長的袋毙，但是刪除操作需要對樹進行從上和從下兩方面的判斷，相對來說冗尤，刪除非常費時听盖。
紅黑樹
紅黑樹是一種 2-3 平衡樹的實現(xiàn)。不用去定義特殊的新的數(shù)據(jù)結(jié)構(gòu)裂七，只需要一些附加信息皆看，就可以實現(xiàn) 2-3 樹的構(gòu)建。
在紅黑樹種碍讯，利用黑連接表示 2-3 樹的普通節(jié)點悬蔽， 紅連接將兩個 2-節(jié)點連接夠成一個三節(jié)點。
一個 2-3 樹可以化成一個等效的紅黑樹捉兴，如下圖所示：
定義
- 紅連接均為左連接
- 沒有任何一個節(jié)點同時和兩條連接相連
- 該樹是黑色完美平衡的蝎困，即任意空連接到根節(jié)點的路徑上的黑連接數(shù)量相同录语。
我們定義節(jié)點上存在 color 屬性，代表的是指向該節(jié)點的連接是什么顏色禾乘。
紅黑樹基本的操作是旋轉(zhuǎn)澎埠，在一些實現(xiàn)中，某些操作可能會出現(xiàn)紅色右連接或者兩條連續(xù)的紅連接始藕，我們定義左旋轉(zhuǎn)是將一條紅色的右連接旋轉(zhuǎn)得到一條左連接蒲稳。右連接相反，如下圖所示：
左旋轉(zhuǎn)的偽代碼如下所示：
Node rotateLset(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = red;
}
只需更改他的 color 屬性為紅伍派，并將他原來自身的 color 屬性賦值給右連接節(jié)點就行江耀。
同理，右連接示意圖如下：
NOde rotateRight(Node h) {
node x= h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = read;
}
對于每一個插入诉植，都插入一個紅連接祥国。
向單個 2-節(jié)點中插入新鍵。如果新鍵小于老鍵晾腔，則增加一個紅色左連接舌稀，否則增加一個紅色右連接并進行左旋轉(zhuǎn)，兩種情況都能產(chǎn)生一個等效的3-連接灼擂，如下所示：
向樹底部的 2-節(jié)點中插入新鍵壁查。總是增加一個新的紅色連接剔应，如果他的父節(jié)點是 2-節(jié)點睡腿，那么按照如上兩種方式調(diào)整節(jié)點就行。
向一棵雙鍵樹（3-節(jié)點）中插入新建峻贮，分為了三種子情況嫉到，第一種情況是新鍵最大，第二種情況是新鍵在中間月洛，第三種情況是新鍵最小。
如下如所示：
對于一個節(jié)點和兩個紅色連接直接相聯(lián)孽锥，這種情況等效于一個 4-節(jié)點嚼黔，當將這兩個紅色連接變黑時，需要將父節(jié)點由黑變紅惜辑，因為這樣的變換會在父節(jié)點產(chǎn)生一個 3-節(jié)點食侮，理由如下：
每產(chǎn)生一個紅色連接都會向上傳遞直到根節(jié)點充活。
具體實現(xiàn)
如下代碼展示了紅黑樹在 Map 中的存儲節(jié)點。
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
以 boolean color 存儲指向該節(jié)點的連接的顏色。
每當增加一個元素后媒峡，調(diào)用 fixAfterInsect 函數(shù)對紅黑樹進行修正，如下所示：
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
ConcurrentHashMap
特性
特性
- 基于 hash map 實現(xiàn)
- 提供所有 map 接口
- 不允許以 null 作為鍵或者值
- 線程安全，檢索操作不需要鎖定整個表
- 檢索操作通常不會阻塞，所以有可能和修改操作重疊
- 迭代時的順序按照鍵值排列胎撇，即存儲順序是有限的（在這個基礎(chǔ)上，同時實現(xiàn)了
NavigableMap接口殖氏，用于查找某個 key 之前的所有元素等操作）
ConcurrentHashMap 實現(xiàn)原理
在 JDK 1.7 及其之前的版本中晚树，ConcurrentHashMap 使用 Segement 數(shù)據(jù)結(jié)構(gòu)作為上鎖的最小單元，每一個 Segment 容納了一個 table雅采，結(jié)構(gòu)如圖所示（引用自 JOE-1992 博客）：
每當進行 get 操作時爵憎，定位到對應(yīng)的 segment，上鎖婚瓜，并執(zhí)行 put 操作宝鼓。
hash 操作
計算 hash 時，同樣使用了內(nèi)置的 hash 函數(shù)對 hash 進行再次求解巴刻。不過相比于 HashMap愚铡，ConcurrentHashMap 使用了single-word Wang/Jenkins hash 算法的變種。代碼如下：
private static int hash(int h) {
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}
note：Wang/Jenkins Hash 算法關(guān)鍵特性
- 雪崩性（更改輸入?yún)?shù)的任何一位冈涧，就將引起輸出有一半以上的位發(fā)生變化）
- 可逆性（input ==> hash ==> inverse_hash ==> input）
因此茂附，使用 Wang/Jenkins Hash 更加能夠獲得沖突更小的 hash。
存儲
在每一個 Segment 中督弓，使用 HashEntry 作為存儲結(jié)構(gòu)营曼，HashEntry 的定義如下：
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//保證set對所有線程可見（volatile 語義）
final void setNext(HashEntry<K,V> n) {
UNSAFE.putOrderedObject(this, nextOffset, n);
}
static final sun.misc.Unsafe UNSAFE;
static final long nextOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class k = HashEntry.class;
nextOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("next"));
} catch (Exception e) {
throw new Error(e);
}
}
}
其中，UNSAFE 為 Java 直接訪問內(nèi)存的函數(shù)愚隧，objectFieldOffset 為獲得某一變量的偏移量蒂阱， putOrderedObject(this, nextOffset, n) 是將 n 放在 this 偏移量 nextOffset 的位置，并且是一個具有 volatile 語義的修改狂塘，對所有的線程可見录煤。
Segment 直接繼承 ReentrantLock，可以簡化鎖或者一些單獨的構(gòu)造器荞胡，使得其可以單獨的當成一個鎖妈踊。結(jié)構(gòu)如下:
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
//真實的存儲結(jié)構(gòu)
transient volatile HashEntry<K,V>[] table;
//對一個 segment 所有元素計數(shù)
transient int count;
transient int modCount;
//當 table 中包含的 HashEntry 元素的個數(shù)超過本變量值時，觸發(fā) table 的再散列
transient int threshold;
final float loadFactor;
//... method
}
整個類 維持了一個 Segment 數(shù)組泪漂，和必要的信息廊营，如下：
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
/**
* segments 的掩碼值
* key 的散列碼的高位用來選擇具體的 segment
*/
final int segmentMask;
/**
* segment 外偏移量，和segment 維持多少個 table 有關(guān)
*/
final int segmentShift;
/**
* 由 Segment 對象組成的數(shù)組萝勤，每個都是一個特別的Hash Table
*/
final Segment<K,V>[] segments;
// 根據(jù) hash 找到對應(yīng) segment
private Segment<K,V> segmentForHash(int h) {
// 重點在 (h >>> segmentShift) & segmentMask 函數(shù)
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// 在 volatile 的環(huán)境下讀取 segments 的第 u 個元素
return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
}
}
在更老的版本中露筒，采用直接加鎖的方式修改數(shù)據(jù)，代碼如下：
// ConcurrentHashMap 方法
public V put(K key, V value) {
if (value == null) //ConcurrentHashMap 中不允許用 null 作為映射值
throw new NullPointerException();
int hash = hash(key.hashCode()); //計算鍵對應(yīng)的散列碼
//根據(jù)散列碼找到對應(yīng)的 Segment
return segmentFor(hash).put(key, hash, value, false);
}
// Segment 方法
V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock(); //當前的segment加鎖
try {
int c = count;
if (c++ > threshold) //如果超過再散列的閾值
rehash(); //執(zhí)行再散列敌卓，table 數(shù)組的長度將擴充一倍
HashEntry<K,V>[] tab = table;
//把散列碼值與 table 數(shù)組的長度減 1 的值相“與”
//得到該散列碼對應(yīng)的 table 數(shù)組的下標值
int index = hash & (tab.length - 1);
//找到散列碼對應(yīng)的具體的那個桶
HashEntry<K,V> first = tab[index];
HashEntry<K,V> e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue;
if (e != null) { //如果鍵/值對以經(jīng)存在
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value; // 設(shè)置 value 值
}
else { //鍵/值對不存在
oldValue = null;
++modCount; //添加新節(jié)點到鏈表中慎式，modCont 要加 1
// 創(chuàng)建新節(jié)點，并添加到鏈表的頭部
tab[index] = new HashEntry<K,V>(key, hash, first, value);
count = c; //寫 count 變量
}
return oldValue;
} finally {
unlock(); //解鎖
}
}
// get
V get(Object key, int hash) {
if(count != 0) { // 首先讀 count 變量
HashEntry<K,V> e = getFirst(hash);
while(e != null) {
if(e.hash == hash && key.equals(e.key)) {
V v = e.value;
if(v != null)
return v;
// 如果讀到 value 域為 null，說明發(fā)生了重排序瘪吏，加鎖后重新讀取
return readValueUnderLock(e);
}
e = e.next;
}
}
return null;
}
在如上的實現(xiàn)中癣防，最重要的是 get 函數(shù)的 count = c 操作和 put 函數(shù)的 count != 0 操作。這時實現(xiàn)可見性的關(guān)鍵肪虎。
當一個線程上鎖修改之后劣砍，會調(diào)用 count = c。 count 是 volatile 類型的變量扇救，這時就會將修改之后的 map 對所有線程可見刑枝。
當另一個線程讀取時，會調(diào)用 count != 0迅腔，這個操作保證了更新之后的值對當前線程可見装畅。
對于 1.7 版本，參見技術(shù)世界
對于讀操作沧烈，獲取Key所在的Segment時掠兄，需要保證可見性。具體實現(xiàn)上可以使用volatile關(guān)鍵字锌雀，也可使用鎖蚂夕。但使用鎖開銷太大，而使用volatile時每次寫操作都會讓所有CPU內(nèi)緩存無效腋逆，也有一定開銷婿牍。ConcurrentHashMap使用如下方法保證可見性，取得最新的Segment惩歉。
Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)
獲取Segment中的HashEntry時也使用了類似方法
HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)
獲取鎖時等脂，并不直接使用lock來獲取，因為該方法獲取鎖失敗時會掛起撑蚌。事實上上遥，它使用了自旋鎖，如果tryLock獲取鎖失敗争涌，說明鎖被其它線程占用粉楚，此時通過循環(huán)再次以tryLock的方式申請鎖。如果在循環(huán)過程中該Key所對應(yīng)的鏈表頭被修改亮垫，則重置retry次數(shù)解幼。如果retry次數(shù)超過一定值，則使用lock方法申請鎖包警。
這里使用自旋鎖是因為自旋鎖的效率比較高，但是它消耗CPU資源比較多底靠，因此在自旋次數(shù)超過閾值時切換為互斥鎖害晦。
為更好支持并發(fā)操作，ConcurrentHashMap會在不上鎖的前提逐個Segment計算3次size，如果某相鄰兩次計算獲取的所有Segment的更新次數(shù)（每個Segment都與HashMap一樣通過modCount跟蹤自己的修改次數(shù)壹瘟，Segment每修改一次其modCount加一）相等鲫剿，說明這兩次計算過程中無更新操作，則這兩次計算出的總size相等稻轨，可直接作為最終結(jié)果返回灵莲。如果這三次計算過程中Map有更新，則對所有Segment加鎖重新計算Size殴俱。該計算方法代碼如下
public int size() {
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
對于 1.8 版本政冻，參見技術(shù)世界 ，使用 CAS 直接完成任務(wù)线欲。
對于put操作明场，如果Key對應(yīng)的數(shù)組元素為null，則通過CAS操作將其設(shè)置為當前值李丰。如果Key對應(yīng)的數(shù)組元素（也即鏈表表頭或者樹的根元素）不為null苦锨，則對該元素使用synchronized關(guān)鍵字申請鎖，然后進行操作趴泌。如果該put操作使得當前鏈表長度超過一定閾值舟舒，則將該鏈表轉(zhuǎn)換為樹，從而提高尋址效率嗜憔。
對于讀操作秃励，由于數(shù)組被volatile關(guān)鍵字修飾，因此不用擔心數(shù)組的可見性問題痹筛。同時每個元素是一個Node實例（Java 7中每個元素是一個HashEntry）莺治，它的Key值和hash值都由final修飾，不可變更帚稠，無須關(guān)心它們被修改后的可見性問題谣旁。而其Value及對下一個元素的引用由volatile修飾，可見性也有保障滋早。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
對于Key對應(yīng)的數(shù)組元素的可見性榄审，由Unsafe的getObjectVolatile方法保證。
put杆麸、remove和get操作只需要關(guān)心一個Segment搁进，而size操作需要遍歷所有的Segment才能算出整個Map的大小。一個簡單的方案是昔头，先鎖住所有Sgment饼问，計算完后再解鎖。但這樣做揭斧，在做size操作時莱革，不僅無法對Map進行寫操作，同時也無法進行讀操作，不利于對Map的并行操作盅视。
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
size操作
put方法和remove方法都會通過addCount方法維護Map的size捐名。size方法通過sumCount獲取由addCount方法維護的Map的size。
ConcurrentSkipListMap
使用跳表實現(xiàn)闹击。
跳躍表原理參見漫畫算法：什么是跳躍表
