HashMap和ConcurrentHashMap在Java7和Java8中原理不同败玉，所以這里分別介紹。
Java7 HashMap
在Java7中镜硕，HashMap內(nèi)部是一個(gè)數(shù)組运翼，每個(gè)數(shù)組元素是一個(gè)單向鏈表。
每個(gè)綠色實(shí)體是一個(gè)Entity實(shí)例兴枯，它包含4個(gè)屬性：key血淌、value、hashCode和指向下一個(gè)Entity實(shí)例的next指針。
每個(gè)HashMap中還包括：1. capacity（數(shù)組容量悠夯，大小為2^n）癌淮；2. loadFactor（負(fù)載銀子，默認(rèn)0.75）沦补；3. threshold（擴(kuò)容閾值乳蓄，capacity*loadFactory）
注：HashMap的初始化和擴(kuò)容大小都是2^n，因?yàn)镠ashMap在獲取key的hashCode后夕膀，需要與數(shù)組長(zhǎng)度進(jìn)行與運(yùn)算虚倒，以便確定存儲(chǔ)在數(shù)組中的index位置，為了不浪費(fèi)空間店诗，做與運(yùn)算時(shí)裹刮，所有位都不要出現(xiàn)0，否則會(huì)造成浪費(fèi)庞瘸。
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
- h：插入元素的hashCode值
- length：hashMap的容量大小
length值為2次冪捧弃，那么length-1的值就是一個(gè)全為1的值：1111...11。與運(yùn)算效率高擦囊，全為1的值做與運(yùn)算不會(huì)有空間浪費(fèi)违霞。
如果length不為2^n，那么length-1可能有0位瞬场，例如：1110买鸽，在與h做與運(yùn)算時(shí)，0001贯被、0011眼五、1001等這樣的位置就不可能被使用了，造成空間浪費(fèi)彤灶，同時(shí)增大碰撞檢測(cè)幾率看幼，減慢查詢(xún)效率。
put
public V put(K key, V value) {
// 當(dāng)插入第一個(gè)元素的時(shí)候幌陕，需要先初始化數(shù)組大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 為 null诵姜，感興趣的可以往里看，最終會(huì)將這個(gè) entry 放到 table[0] 中
if (key == null)
return putForNullKey(value);
// 1. 求 key 的 hash 值
int hash = hash(key);
// 2. 找到對(duì)應(yīng)的數(shù)組下標(biāo)
int i = indexFor(hash, table.length);
// 3. 遍歷一下對(duì)應(yīng)下標(biāo)處的鏈表搏熄，看是否有重復(fù)的 key 已經(jīng)存在棚唆，
// 如果有，直接覆蓋心例，put 方法返回舊值就結(jié)束了
for (Entry<K,V> 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++;
// 4. 不存在重復(fù)的 key宵凌，將此 entry 添加到鏈表中，細(xì)節(jié)后面說(shuō)
addEntry(hash, key, value, i);
return null;
}
數(shù)組初始化
inflateTable()為HashMap中數(shù)組的初始化函數(shù)：
private void inflateTable(int toSize) {
// 保證數(shù)組大小一定是 2 的 n 次方契邀。
// 比如這樣初始化：new HashMap(20)摆寄，那么處理成初始數(shù)組大小是 32
int capacity = roundUpToPowerOf2(toSize);
// 計(jì)算擴(kuò)容閾值：capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 算是初始化數(shù)組吧
table = new Entry[capacity];
initHashSeedAsNeeded(capacity); //ignore
}
數(shù)組大小保持為 2 的 n 次方，具體原因前面已經(jīng)講過(guò)坯门。
計(jì)算具體數(shù)組位置
根據(jù)key計(jì)算出的hash值微饥，與length進(jìn)行與運(yùn)算。
static int indexFor(int hash, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return hash & (length-1);
}
就是取 hash 值的低 n 位古戴。如在數(shù)組長(zhǎng)度為 32 的時(shí)候欠橘，其實(shí)取的就是 key 的 hash 值的低 5 位，作為它在數(shù)組中的下標(biāo)位置现恼。
添加節(jié)點(diǎn)到鏈表
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果當(dāng)前 HashMap 大小已經(jīng)達(dá)到了閾值肃续，并且新值要插入的數(shù)組位置已經(jīng)有元素了，那么要擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴(kuò)容叉袍，后面會(huì)介紹一下
resize(2 * table.length);
// 擴(kuò)容以后始锚，重新計(jì)算 hash 值
hash = (null != key) ? hash(key) : 0;
// 重新計(jì)算擴(kuò)容后的新的下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
// 往下看
createEntry(hash, key, value, bucketIndex);
}
// 這個(gè)很簡(jiǎn)單，其實(shí)就是將新值放到鏈表的表頭喳逛，然后 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
首先判斷數(shù)組是否需要擴(kuò)容瞧捌，然后將新值放在鏈表表頭，size++润文。
數(shù)組擴(kuò)容
擴(kuò)容后姐呐，數(shù)組大小為原來(lái)的 2 倍。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新的數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將原來(lái)數(shù)組中的值遷移到新的更大的數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
擴(kuò)容就是new一個(gè)新數(shù)組典蝌，并將老數(shù)組中的數(shù)據(jù)遷移至新數(shù)組宗曙砂。原來(lái)table[i]鏈表中的所有節(jié)點(diǎn)，會(huì)被重新分配到table[i]和table[i + oldLength]中（如原來(lái)數(shù)組長(zhǎng)度是 16骏掀，那么擴(kuò)容后鸠澈，原來(lái) table[0] 處的鏈表中的所有元素會(huì)被分配到新數(shù)組中 newTable[0] 和 newTable[16] 這兩個(gè)位置）。
get
public V get(Object key) {
// 之前說(shuō)過(guò)截驮，key 為 null 的話(huà)笑陈，會(huì)被放到 table[0]，所以只要遍歷下 table[0] 處的鏈表就可以了
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
// 確定數(shù)組下標(biāo)侧纯，然后從頭開(kāi)始遍歷鏈表新锈，直到找到為止
for (Entry<K,V> 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ì)算 hash 值。
- 找到相應(yīng)的數(shù)組下標(biāo)：hash & (length – 1)眶熬。
- 遍歷該數(shù)組位置處的鏈表妹笆，直到找到相等(==或equals)的 key。
Java7 ConcurrentHashMap
CuncurrentHashMap是一個(gè)數(shù)組娜氏，每個(gè)元素是一個(gè)Segment拳缠，每個(gè)segment繼承自ReentrantLook來(lái)實(shí)現(xiàn)鎖，也就是說(shuō)CuncurrentHashMap是通過(guò)鎖住每一個(gè)segment從而實(shí)現(xiàn)整體的線程安全贸弥。
初始化CuncurrentHashMap時(shí)可以定義數(shù)組大小窟坐，默認(rèn)為16，即最多支持16條線程同時(shí)讀寫(xiě)（分布于16個(gè)不同的Segment），一旦定義哲鸳，不可修改臣疑。
初始化
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
// 計(jì)算并行級(jí)別 ssize，因?yàn)橐３植⑿屑?jí)別是 2 的 n 次方
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 我們這里先不要那么燒腦徙菠，用默認(rèn)值讯沈，concurrencyLevel 為 16，sshift 為 4
// 那么計(jì)算出 segmentShift 為 28婿奔，segmentMask 為 15缺狠，后面會(huì)用到這兩個(gè)值
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// initialCapacity 是設(shè)置整個(gè) map 初始的大小，
// 這里根據(jù) initialCapacity 計(jì)算 Segment 數(shù)組中每個(gè)位置可以分到的大小
// 如 initialCapacity 為 64萍摊，那么每個(gè) Segment 或稱(chēng)之為"槽"可以分到 4 個(gè)
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
// 默認(rèn) MIN_SEGMENT_TABLE_CAPACITY 是 2挤茄，這個(gè)值也是有講究的，因?yàn)檫@樣的話(huà)冰木，對(duì)于具體的槽上穷劈，
// 插入一個(gè)元素不至于擴(kuò)容，插入第二個(gè)的時(shí)候才會(huì)擴(kuò)容
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 創(chuàng)建 Segment 數(shù)組片酝，
// 并創(chuàng)建數(shù)組的第一個(gè)元素 segment[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
// 往數(shù)組寫(xiě)入 segment[0]
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
- initialCapacity：初始容量囚衔，這個(gè)值指的是整個(gè) ConcurrentHashMap 的初始容量，實(shí)際操作的時(shí)候需要平均分給每個(gè) Segment雕沿。
- loadFactor：負(fù)載因子练湿，Segment 數(shù)組不可以擴(kuò)容，這個(gè)負(fù)載因子是給每個(gè) Segment 內(nèi)部使用的审轮。
- cap是每個(gè)Segment的初始大小肥哎，默認(rèn)MIN_SEGMENT_TABLE_CAPACITY=2，而默認(rèn)的負(fù)載因子LoadFactor是0.75疾渣，所以每個(gè)Segment的初始閾值為2*0.75=1.5篡诽，即放入第一個(gè)值時(shí)不會(huì)擴(kuò)容，第二個(gè)值才開(kāi)始擴(kuò)容榴捡。
- 初始化時(shí)只初始化了Segment[0]杈女，其他位置為null
- 當(dāng)前 segmentShift 的值為 32 – 4 = 28，segmentMask 為 16 – 1 = 15
put
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 1. 計(jì)算 key 的 hash 值
int hash = hash(key);
// 2. 根據(jù) hash 值找到 Segment 數(shù)組中的位置 j
// hash 是 32 位吊圾，無(wú)符號(hào)右移 segmentShift(28) 位达椰，剩下低 4 位，
// 然后和 segmentMask(15) 做一次與操作项乒，也就是說(shuō) j 是 hash 值的最后 4 位啰劲，也就是槽的數(shù)組下標(biāo)
int j = (hash >>> segmentShift) & segmentMask;
// 剛剛說(shuō)了，初始化的時(shí)候初始化了 segment[0]檀何，但是其他位置還是 null蝇裤，
// ensureSegment(j) 對(duì) segment[j] 進(jìn)行初始化
if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
// 3. 插入新值到槽s中
return s.put(key, hash, value, false);
}
Segment.put()
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 在往該 segment 寫(xiě)入前廷支，需要先獲取該 segment 的獨(dú)占鎖
// 先看主流程，后面還會(huì)具體介紹這部分內(nèi)容
HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
V oldValue;
try {
// 這個(gè)是 segment 內(nèi)部的數(shù)組
HashEntry<K,V>[] tab = table;
// 再利用 hash 值栓辜，求應(yīng)該放置的數(shù)組下標(biāo)
int index = (tab.length - 1) & hash;
// first 是數(shù)組該位置處的鏈表的表頭
HashEntry<K,V> first = entryAt(tab, index);
// 下面這串 for 循環(huán)雖然很長(zhǎng)恋拍，不過(guò)也很好理解，想想該位置沒(méi)有任何元素和已經(jīng)存在一個(gè)鏈表這兩種情況
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
// 覆蓋舊值
e.value = value;
++modCount;
}
break;
}
// 繼續(xù)順著鏈表走
e = e.next;
}
else {
// node到底是不是null啃憎，這個(gè)要看獲取鎖的過(guò)程芝囤，不過(guò)和這里都沒(méi)有關(guān)系似炎。
// 如果不為null辛萍，那就直接將它設(shè)置為鏈表表頭；如果是null羡藐，初始化并設(shè)置為鏈表表頭贩毕。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 如果超過(guò)了該 segment 的閾值，這個(gè) segment 需要擴(kuò)容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); // 擴(kuò)容后面也會(huì)具體分析
else
// 沒(méi)有達(dá)到閾值仆嗦，將 node 放到數(shù)組 tab 的 index 位置辉阶，
// 其實(shí)就是將新的節(jié)點(diǎn)設(shè)置成原鏈表的表頭
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 解鎖
unlock();
}
return oldValue;
}
這里面，首先通過(guò)hash判斷value需要放在segment中的數(shù)組的那個(gè)位置瘩扼，然后獲取該位置的鏈表的表頭first谆甜，如果表頭first不為null，則插入鏈表頭集绰；如果first為空规辱，設(shè)置新鏈表，賦值栽燕。
每個(gè)Segment都有一個(gè)獨(dú)占鎖（tryLock()）罕袋。
初始化槽: ensureSegment
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// 這里看到為什么之前要初始化 segment[0] 了，
// 使用當(dāng)前 segment[0] 處的數(shù)組長(zhǎng)度和負(fù)載因子來(lái)初始化 segment[k]
// 為什么要用“當(dāng)前”碍岔，因?yàn)?segment[0] 可能早就擴(kuò)容過(guò)了
Segment<K,V> proto = ss[0];
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
// 初始化 segment[k] 內(nèi)部的數(shù)組
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
// 再次檢查一遍該槽是否被其他線程初始化了浴讯。
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
// 使用 while 循環(huán)，內(nèi)部用 CAS蔼啦，當(dāng)前線程成功設(shè)值或其他線程成功設(shè)值后榆纽，退出
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
通過(guò)之前初始化好的Segment[0]獲取基本信息，建立新的Segment[k]捏肢。并發(fā)操作使用 CAS 進(jìn)行控制奈籽，樂(lè)觀鎖，while循環(huán)獲取鎖猛计。
獲取寫(xiě)入鎖: scanAndLockForPut
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // negative while locating node
// 循環(huán)獲取鎖
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
// 進(jìn)到這里說(shuō)明數(shù)組該位置的鏈表是空的唠摹，沒(méi)有任何元素
// 當(dāng)然，進(jìn)到這里的另一個(gè)原因是 tryLock() 失敗奉瘤，所以該槽存在并發(fā)勾拉，不一定是該位置
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
// 順著鏈表往下走
e = e.next;
}
// 重試次數(shù)如果超過(guò) MAX_SCAN_RETRIES（單核1多核64）煮甥，那么不搶了，進(jìn)入到阻塞隊(duì)列等待鎖
// lock() 是阻塞方法藕赞，直到獲取鎖后返回
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
else if ((retries & 1) == 0 &&
// 這個(gè)時(shí)候是有大問(wèn)題了成肘，那就是有新的元素進(jìn)到了鏈表，成為了新的表頭
// 所以這邊的策略是斧蜕，相當(dāng)于重新走一遍這個(gè) scanAndLockForPut 方法
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
這個(gè)方法有兩個(gè)出口双霍，一個(gè)是 tryLock() 成功了，循環(huán)終止批销，另一個(gè)就是重試次數(shù)超過(guò)了 MAX_SCAN_RETRIES洒闸，進(jìn)到 lock() 方法，此方法會(huì)阻塞等待均芽，直到成功拿到獨(dú)占鎖丘逸。
擴(kuò)容: rehash
CuncurrentHashMap擴(kuò)容主要是指Segment內(nèi)部的數(shù)組HashEntry[] 擴(kuò)容，每次擴(kuò)容2倍
// 方法參數(shù)上的 node 是這次擴(kuò)容后掀宋，需要添加到新的數(shù)組中的數(shù)據(jù)甩牺。
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
// 2 倍
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
// 創(chuàng)建新數(shù)組
HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
// 新的掩碼城看，如從 16 擴(kuò)容到 32，那么 sizeMask 為 31，對(duì)應(yīng)二進(jìn)制 ‘000...00011111’
int sizeMask = newCapacity - 1;
// 遍歷原數(shù)組镐躲，老套路祠肥，將原數(shù)組位置 i 處的鏈表拆分到 新數(shù)組位置 i 和 i+oldCap 兩個(gè)位置
for (int i = 0; i < oldCapacity ; i++) {
// e 是鏈表的第一個(gè)元素
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
// 計(jì)算應(yīng)該放置在新數(shù)組中的位置枪汪，
// 假設(shè)原數(shù)組長(zhǎng)度為 16悉尾，e 在 oldTable[3] 處，那么 idx 只可能是 3 或者是 3 + 16 = 19
int idx = e.hash & sizeMask;
if (next == null) // 該位置處只有一個(gè)元素唆途，那比較好辦
newTable[idx] = e;
else {
// Reuse consecutive sequence at same slot
// e 是鏈表表頭
HashEntry<K,V> lastRun = e;
// idx 是當(dāng)前鏈表的頭結(jié)點(diǎn) e 的新位置
int lastIdx = idx;
// 下面這個(gè) for 循環(huán)會(huì)找到一個(gè) lastRun 節(jié)點(diǎn)富雅，這個(gè)節(jié)點(diǎn)之后的所有元素是將要放到一起的
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// 將 lastRun 及其之后的所有節(jié)點(diǎn)組成的這個(gè)鏈表放到 lastIdx 這個(gè)位置
newTable[lastIdx] = lastRun;
// 下面的操作是處理 lastRun 之前的節(jié)點(diǎn)，
// 這些節(jié)點(diǎn)可能分配在另一個(gè)鏈表中肛搬，也可能分配到上面的那個(gè)鏈表中
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 將新來(lái)的 node 放到新數(shù)組中剛剛的 兩個(gè)鏈表之一 的 頭部
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
get 過(guò)程分析
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
// 1. hash 值
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// 2. 根據(jù) hash 找到對(duì)應(yīng)的 segment
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null
&& (tab = s.table) != null) {
// 3. 找到segment 內(nèi)部數(shù)組相應(yīng)位置的鏈表没佑，遍歷
for (HashEntry<K,V> e = (HashEntry<K,V>)
UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
- 計(jì)算 hash 值，找到 segment 數(shù)組中的具體位置温赔，或我們前面用的“槽”
- 槽中也是一個(gè)數(shù)組蛤奢，根據(jù) hash 找到數(shù)組中具體的位置
- 到這里是鏈表了，順著鏈表進(jìn)行查找即可
并發(fā)問(wèn)題分析
CuncurrentHashMap使用了CAS和volatite陶贼，使得雖然get()操作沒(méi)有加鎖啤贩，但是依然不會(huì)影響到多線程時(shí)，get拜秧、put痹屹、remove時(shí)的線程安全性。
具體分析來(lái)源于：Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
- 添加節(jié)點(diǎn)的操作 put 和刪除節(jié)點(diǎn)的操作 remove 都是要加 segment 上的獨(dú)占鎖的枉氮，所以它們之間自然不會(huì)有問(wèn)題志衍，我們需要考慮的問(wèn)題就是 get 的時(shí)候在同一個(gè) segment 中發(fā)生了 put 或 remove 操作暖庄。
- put 操作的線程安全性
- 初始化槽：這個(gè)我們之前就說(shuō)過(guò)了，使用了 CAS 來(lái)初始化 Segment 中的數(shù)組楼肪。
- 添加節(jié)點(diǎn)到鏈表的操作是插入到表頭的培廓，所以，如果這個(gè)時(shí)候 get 操作在鏈表遍歷的過(guò)程已經(jīng)到了中間春叫，是不會(huì)影響的肩钠。當(dāng)然，另一個(gè)并發(fā)問(wèn)題就是 get 操作在 put 之后暂殖，需要保證剛剛插入表頭的節(jié)點(diǎn)被讀取价匠，這個(gè)依賴(lài)于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject
- 擴(kuò)容：擴(kuò)容是新創(chuàng)建了數(shù)組，然后進(jìn)行遷移數(shù)據(jù)央星，最后面將 newTable 設(shè)置給屬性 table霞怀。所以，如果 get 操作此時(shí)也在進(jìn)行莉给，那么也沒(méi)關(guān)系，如果 get 先行廉沮，那么就是在舊的 table 上做查詢(xún)操作颓遏；而 put 先行，那么 put 操作的可見(jiàn)性保證就是 table 使用了 volatile 關(guān)鍵字
- remove 操作的線程安全性
- 如果 remove 破壞的節(jié)點(diǎn) get 操作已經(jīng)過(guò)去了滞时，那么這里不存在任何問(wèn)題
- 如果 remove 先破壞了一個(gè)節(jié)點(diǎn)叁幢，分兩種情況考慮。 1坪稽、如果此節(jié)點(diǎn)是頭結(jié)點(diǎn)曼玩，那么需要將頭結(jié)點(diǎn)的 next 設(shè)置為數(shù)組該位置的元素，table 雖然使用了 volatile 修飾窒百，但是 volatile 并不能提供數(shù)組內(nèi)部操作的可見(jiàn)性保證黍判，所以源碼中使用了 UNSAFE 來(lái)操作數(shù)組，請(qǐng)看方法 setEntryAt篙梢。2顷帖、如果要?jiǎng)h除的節(jié)點(diǎn)不是頭結(jié)點(diǎn)，它會(huì)將要?jiǎng)h除節(jié)點(diǎn)的后繼節(jié)點(diǎn)接到前驅(qū)節(jié)點(diǎn)中渤滞，這里的并發(fā)保證就是 next 屬性是 volatile 的
Java8 HashMap
Java 7中的HashMap是由數(shù)組+鏈表構(gòu)成的贬墩，先根據(jù)hashCode定位到數(shù)組具體下標(biāo)，然后再鏈表中一個(gè)一個(gè)按順序查找妄呕，所以時(shí)間復(fù)雜度是O(n)陶舞。
而Java 8中的HashMap利用了紅黑樹(shù)，由數(shù)組+鏈表+紅黑樹(shù)組成绪励，當(dāng)鏈表的長(zhǎng)度超過(guò)8個(gè)后肿孵，會(huì)將鏈表轉(zhuǎn)化為紅黑樹(shù)论咏，所以時(shí)間復(fù)雜度為O(logN)。
Java 7中HashMap的數(shù)據(jù)節(jié)點(diǎn)是Entry颁井，而Java 8中使用Node（鏈表）和TreeNode（紅黑樹(shù)）來(lái)代表節(jié)點(diǎn)厅贪。因此，可以根據(jù)當(dāng)前節(jié)點(diǎn)是Node還是TreeNode來(lái)判斷當(dāng)前使用的是鏈表還是紅黑樹(shù)雅宾。
put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 第三個(gè)參數(shù) onlyIfAbsent 如果是 true养涮，那么只有在不存在該 key 時(shí)才會(huì)進(jìn)行 put 操作
// 第四個(gè)參數(shù) evict 我們這里不關(guān)心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的時(shí)候，會(huì)觸發(fā)下面的 resize()眉抬，類(lèi)似 java7 的第一次 put 也要初始化數(shù)組長(zhǎng)度
// 第一次 resize 和后續(xù)的擴(kuò)容有些不一樣贯吓，因?yàn)檫@次是數(shù)組從 null 初始化到默認(rèn)的 16 或自定義的初始容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具體的數(shù)組下標(biāo)，如果此位置沒(méi)有值蜀变，那么直接初始化一下 Node 并放置在這個(gè)位置就可以了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {// 數(shù)組該位置有數(shù)據(jù)
Node<K,V> e; K k;
// 首先悄谐，判斷該位置的第一個(gè)數(shù)據(jù)和我們要插入的數(shù)據(jù)，key 是不是"相等"库北，如果是爬舰，取出這個(gè)節(jié)點(diǎn)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果該節(jié)點(diǎn)是代表紅黑樹(shù)的節(jié)點(diǎn)，調(diào)用紅黑樹(shù)的插值方法寒瓦，本文不展開(kāi)說(shuō)紅黑樹(shù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 到這里情屹，說(shuō)明數(shù)組該位置上是一個(gè)鏈表
for (int binCount = 0; ; ++binCount) {
// 插入到鏈表的最后面(Java7 是插入到鏈表的最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 為 8，所以杂腰，如果新插入的值是鏈表中的第 9 個(gè)
// 會(huì)觸發(fā)下面的 treeifyBin垃你，也就是將鏈表轉(zhuǎn)換為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在該鏈表中找到了"相等"的 key(== 或 equals)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 此時(shí) break，那么 e 為鏈表中[與要插入的新值的 key "相等"]的 node
break;
p = e;
}
}
// e!=null 說(shuō)明存在舊值的key與要插入的key"相等"
// 對(duì)于我們分析的put操作喂很，下面這個(gè) if 其實(shí)就是進(jìn)行 "值覆蓋"惜颇，然后返回舊值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入這個(gè)值導(dǎo)致 size 已經(jīng)超過(guò)了閾值，需要進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize() 擴(kuò)容：2倍大小
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) { // 對(duì)應(yīng)數(shù)組擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 將數(shù)組大小擴(kuò)大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 將閾值擴(kuò)大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 對(duì)應(yīng)使用 new HashMap(int initialCapacity) 初始化后少辣，第一次 put 的時(shí)候
newCap = oldThr;
else {// 對(duì)應(yīng)使用 new HashMap() 初始化后凌摄，第一次 put 的時(shí)候
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;
// 用新的數(shù)組大小初始化新的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 如果是初始化數(shù)組，到這里就結(jié)束了毒坛，返回 newTab 即可
if (oldTab != null) {
// 開(kāi)始遍歷原數(shù)組望伦，進(jìn)行數(shù)據(jù)遷移。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果該數(shù)組位置上只有單個(gè)元素煎殷，那就簡(jiǎn)單了屯伞，簡(jiǎn)單遷移這個(gè)元素就可以了
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹(shù)，具體我們就不展開(kāi)了
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 這塊是處理鏈表的情況豪直，
// 需要將此鏈表拆成兩個(gè)鏈表劣摇，放到新的數(shù)組中，并且保留原來(lái)的先后順序
// loHead弓乙、loTail 對(duì)應(yīng)一條鏈表末融，hiHead钧惧、hiTail 對(duì)應(yīng)另一條鏈表，代碼還是比較簡(jiǎn)單的
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;
// 第二條鏈表的新的位置是 j + oldCap勾习，這個(gè)很好理解
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get()
- 計(jì)算 key 的 hash 值浓瞪，根據(jù) hash 值找到對(duì)應(yīng)數(shù)組下標(biāo): hash & (length-1)
- 判斷數(shù)組該位置處的元素是否剛好就是我們要找的，如果不是巧婶，走第三步
- 判斷該元素類(lèi)型是否是 TreeNode乾颁，如果是，用紅黑樹(shù)的方法取數(shù)據(jù)艺栈，如果不是英岭，走第四步
- 遍歷鏈表，直到找到相等(==或equals)的 key
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) {
// 判斷第一個(gè)節(jié)點(diǎn)是不是就是需要的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判斷是否是紅黑樹(shù)
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;
}
Java8 ConcurrentHashMap
Java 8中ConcurrentHashMap的結(jié)構(gòu)與HashMap相同湿右，不過(guò)由于需要考慮線程安全诅妹，所以邏輯實(shí)現(xiàn)更復(fù)雜。
初始化
// 這構(gòu)造函數(shù)里毅人，什么都不干
public ConcurrentHashMap() {
}
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
sizeCtl = 【 (1.5 * initialCapacity + 1)吭狡，然后向上取最近的 2 的 n 次方】。如 initialCapacity 為 10堰塌，那么得到 sizeCtl 為 16赵刑，如果 initialCapacity 為 11，得到 sizeCtl 為 32场刑。
