HashMap
hashMap1.7的數(shù)據(jù)結(jié)構(gòu)
1.7的結(jié)構(gòu)如下圖，底層是一個(gè)大的Entry數(shù)組，每個(gè)數(shù)組元素為一個(gè)鏈表。圖中同時(shí)可以看出put和get的流程。下面對put和get的部分代碼用圖示方式展示，同時(shí)可以參考源碼自己分析。
HashMap1.7.png
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<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++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
// 此處擴(kuò)容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 創(chuàng)建鍵值對并加入map中
createEntry(hash, key, value, bucketIndex);
}
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++;
}
get方法源碼
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
hashMap1.8的數(shù)據(jù)結(jié)構(gòu)
1.8的數(shù)據(jù)結(jié)構(gòu)如下圖，同時(shí)跟1.7一樣，put個(gè)get操作的大體流程也繪制在圖中了。朋友們可以對照著源碼和圖自行消化一下。
HashMap 1.8 的數(shù)據(jù)結(jié)構(gòu).png
老規(guī)矩，源碼說話。
put方法
public V put(K key, V value) {
// 先計(jì)算hashcode，key為0時(shí)直接返回0
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;
// 創(chuàng)建Map時(shí)并未初始化table，第一次put時(shí)先進(jìn)行初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化也是通過resize來實(shí)現(xiàn)的
n = (tab = resize()).length;
// 根據(jù)hashcode和table長度計(jì)算index，確定對應(yīng)index下是否已經(jīng)有值。
if ((p = tab[i = (n - 1) & hash]) == null只
// 為空時(shí)直接創(chuàng)建Node并插入
tab[i] = newNode(hash, key, value, null);
else {
// 否則先判斷key是否與表頭元素相同，相同則直接返回node節(jié)點(diǎn)
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 不同時(shí)判斷是否為樹節(jié)點(diǎn)，若為樹節(jié)點(diǎn)則通過紅黑樹插入元素
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 不是樹節(jié)點(diǎn)說明還是鏈表，遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 判斷是否為鏈尾，鏈尾的話直接插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 插入元素后判斷元素個(gè)數(shù)是否超過閾值，超過則將鏈表轉(zhuǎn)成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 不是鏈尾就繼續(xù)判斷是否和key相同，相同則將node返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果改key已經(jīng)存在，則根據(jù)onlyIfAbsent參數(shù)或舊值是否為空判斷是否要覆蓋元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 修改modCount
++modCount;
// 修改map的size并判斷是否需要擴(kuò)容
if (++size > threshold)
// 擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
get方法
public V get(Object key) {
Node<K,V> e;
// 同樣還是先計(jì)算hashcode，然后通過getNode返回的節(jié)點(diǎn)獲取value
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;
// 當(dāng)map不為空且根據(jù)hash與table.length計(jì)算得到的index處元素不為空時(shí)
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 這里判斷頭元素是否與給定key相同，相同就返回該node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果不是尾節(jié)點(diǎn)
if ((e = first.next) != null) {
// 為紅黑樹時(shí)調(diào)用紅黑樹的方法獲取元素
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否則遍歷鏈表獲取指定key的元素
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap 1.7和1.8的區(qū)別
主要有如下幾點(diǎn)區(qū)別：
1.7與1.8在數(shù)據(jù)結(jié)構(gòu)上來說底層都是一個(gè)大數(shù)組來存儲(chǔ)，唯一的區(qū)別是數(shù)組的每個(gè)元素類型不同，1.7下是一個(gè)鏈表。1.8為了優(yōu)化鏈表的檢索速度將數(shù)組其結(jié)構(gòu)改成了鏈表+紅黑樹。默認(rèn)情況下在鏈表長度大于等于8時(shí)會(huì)將鏈表轉(zhuǎn)成紅黑樹，在長度小于等于6時(shí)會(huì)退回鏈表。
在put時(shí)1.7采用的是頭插法，而1.8采用的是尾插法。感興趣的朋友可以繼續(xù)深入看看為什么會(huì)有這種修改。
1.7的擴(kuò)容發(fā)生在addEntry之前，而1.8的擴(kuò)容發(fā)生在put結(jié)束之后。
如果還有其他的區(qū)別還請大家和我聯(lián)系，我會(huì)補(bǔ)充上去。
ConcurrentHashMap
ConcurrentHashMap1.7的數(shù)據(jù)結(jié)構(gòu)
1.7中ConcurrentHashMap采用了分段鎖+Entry數(shù)組的結(jié)構(gòu)，每個(gè)Segment其實(shí)是ReentrantLock的子類。因此天然擁有加鎖的功能，其數(shù)據(jù)結(jié)構(gòu)如下圖。
ConcurrentHashMap1.7.png
1.7中的put和get流程如上圖所示。其實(shí)并不復(fù)雜，由于表示數(shù)據(jù)的幾個(gè)關(guān)鍵變量都被volatile修飾。因此大部分操作不需要加鎖，僅在put時(shí)對所操作的分段加鎖。get操作不加鎖，size方法視具體情況而定，下面單獨(dú)分析。
ConcurrentHashMap1.7的幾處關(guān)鍵代碼
初始化ConcurrentHashMap時(shí)確定分段大小即其他分段參數(shù)。
public ConcurrentHashMap(){
// ...省略其他代碼
int sshift = 0;
// 分段大小
int ssize = 1;
// 默認(rèn)concurrencyLevel是16，這里ssize每次 * 2，即循環(huán)可以執(zhí)行4次，此時(shí)sshift=4，ssize = 16
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 從上方計(jì)算結(jié)果可以得到，segmentShift = 28
this.segmentShift = 32 - sshift;
// segmentMark = 15
this.segmentMask = ssize - 1;
// ...省略其他代碼
// create segments and segments[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];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
segments數(shù)組的大小僅在上述初始化創(chuàng)建代碼中確定，一旦map創(chuàng)建成功后分段個(gè)數(shù)不會(huì)改變，每次擴(kuò)容也只針對某個(gè)分段內(nèi)的桶進(jìn)行擴(kuò)容。
put方法
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
// 通過segmentShift和segmentMask計(jì)算key所在的分段位置
int j = (hash >>> segmentShift) & segmentMask;
// 如果分段尚未初始化(==null),則初始化該分段(即使用第一分段為原型創(chuàng)建新對象)
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
// 委托給分段的put方法
return s.put(key, hash, value, false);
}
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) {
// 使用第一個(gè)分段作為原型
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 嘗試獲取鎖，這里肯定能拿到鎖，否則會(huì)掛起，直到拿到鎖為止
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
// scanAndLockForPut方法中獲取node節(jié)點(diǎn)時(shí)bucket的index計(jì)算方法與此處計(jì)算方法不同，下面對node進(jìn)行操作時(shí)有什么影響？
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
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;
}
e = e.next;
}
else {
// node不為null說明獲取鎖的時(shí)候創(chuàng)建了node對象，直接將node插入表頭即可
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 判斷是否需要擴(kuò)容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 釋放鎖
unlock();
}
return oldValue;
}
get方法
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
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;
}
size方法
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
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 (;;) {
// RETRIES_BEFORE_LOCK默認(rèn)為2，說明先嘗試3次，如果其中連續(xù)兩次結(jié)果一樣則直接返回。如果沒有則對所有分段加鎖，在計(jì)算。隨后解鎖
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;
// 如果大小溢出的話標(biāo)識(shí)位設(shè)為true
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
// last用來記錄上次循環(huán)的計(jì)算結(jié)果，sum為本次循環(huán)的計(jì)算結(jié)果。如果連續(xù)兩次結(jié)果一致則退出循環(huán)
if (sum == last)
break;
last = sum;
}
} finally {
// 如果重試次數(shù)超過加鎖所需的次數(shù)，則對所有分段解鎖
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
// 如果溢出則返回Integer.MAX_VALUE，否則返回正確size
return overflow ? Integer.MAX_VALUE : size;
}
ConcurrentHashMap1.8的數(shù)據(jù)結(jié)構(gòu)
未完待續(xù)
ConcurrentHashMap與hashtable的區(qū)別
未完待續(xù)
