解析ConcurrentHashMap: 預(yù)熱(內(nèi)部一些小方法分析)
更新時間：2021年06月10日 15:43:48 作者：興趣使然の草帽路飛
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)，今天給大家普及java面試常見問題---ConcurrentHashMap知識，一起看看吧
前面一篇文章中介紹了并發(fā)HashMap的主要成員屬性，內(nèi)部類和構(gòu)造函數(shù)：
下面在正式分析并發(fā)HashMap成員方法之前，先分析一些內(nèi)部類中的字方法函數(shù)：
首先來看下ConcurrentHashMap內(nèi)部類Node中的hash成員屬性值的計算方法spread(int h)：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// 該屬性是通過spread(int h)方法計算得到~
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
...
}
1、spread(int h)方法
/**
* 計算Node節(jié)點hash值的算法：參數(shù)h為hash值
* eg:
* h二進(jìn)制為 --> 1100 0011 1010 0101 0001 1100 0001 1110
* (h >>> 16) --> 0000 0000 0000 0000 1100 0011 1010 0101
* (h ^ (h >>> 16)) --> 1100 0011 1010 0101 1101 1111 1011 1011
* 注：(h ^ (h >>> 16)) 目的是讓h的高16位也參與尋址計算，使得到的hash值更分散，減少hash沖突產(chǎn)生~
* ------------------------------------------------------------------------------
* HASH_BITS --> 0111 1111 1111 1111 1111 1111 1111 1111
* (h ^ (h >>> 16)) --> 1100 0011 1010 0101 1101 1111 1011 1011
* (h ^ (h >>> 16)) & HASH_BITS --> 0100 0011 1010 0101 1101 1111 1011 1011
* 注： (h ^ (h >>> 16))得到的結(jié)果再& HASH_BITS，目的是為了讓得到的hash值結(jié)果始終是一個正數(shù)
*/
static final int spread(int h) {
// 讓原來的hash值異或^原來hash值的右移16位，再與&上HASH_BITS(0x7fffffff: 二進(jìn)制為31個1)
return (h ^ (h >>> 16)) & HASH_BITS;
}
下面介紹tabAt(Node<K,V>[] tab, int i)方法：獲取 tab(Node[]) 數(shù)組指定下標(biāo) i 的Node節(jié)點。
2、tabAt方法
/**
* 獲取 tab(Node[]) 數(shù)組指定下標(biāo) i 的Node節(jié)點
* Node<K,V>[] tab：表示Node[]數(shù)組
* int i：表示數(shù)組下標(biāo)
*/
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
// ((long)i << ASHIFT) + ABASE 的作用：請看下面的分析描述~
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
在分析((long)i << ASHIFT) + ABASE時，先復(fù)習(xí)一下上一篇文章：ConcurrentHashMap源碼解析_01 成員屬性、內(nèi)部類、構(gòu)造方法分析中介紹到的一些屬性字段的含義：
// Node數(shù)組的class對象 Class<?> ak = Node[].class; // U.arrayBaseOffset(ak)：根據(jù)as獲取Node[]數(shù)組第一個元素的偏移地址ABASE ABASE = U.arrayBaseOffset(ak); // scale：表示數(shù)組中每一個單元所占用的空間大小，即scale表示Node[]數(shù)組中每一個單元所占用的空間 int scale = U.arrayIndexScale(ak);// scale必須為2的次冪數(shù) // numberOfLeadingZeros(scale) 根據(jù)scale，返回當(dāng)前數(shù)值轉(zhuǎn)換為二進(jìn)制后，從高位到地位開始統(tǒng)計，統(tǒng)計有多少個0連續(xù)在一塊：eg, 8轉(zhuǎn)換二進(jìn)制=>1000 則 numberOfLeadingZeros(8)的結(jié)果就是28，為什么呢？因為Integer是32位，1000占4位，那么前面就有32-4個0，即連續(xù)最長的0的個數(shù)為28個 // 4轉(zhuǎn)換二進(jìn)制=>100 則 numberOfLeadingZeros(8)的結(jié)果就是29 // ASHIFT = 31 - Integer.numberOfLeadingZeros(4) = 2 那么ASHIFT的作用是什么呢？其實它有數(shù)組尋址的一個作用： // 拿到下標(biāo)為5的Node[]數(shù)組元素的偏移地址(存儲地址)：假設(shè)此時 根據(jù)scale計算得到的ASHIFT = 2 // ABASE + (5 << ASHIFT) == ABASE + (5 << 2) == ABASE + 5 * scale(乘法運(yùn)算效率低)，就得到了下標(biāo)為5的數(shù)組元素的偏移地址 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
由上面的幾個屬性字段的復(fù)習(xí)介紹，不難得出：
((long)i << ASHIFT) + ABASE 就是得到當(dāng)前Node[] 數(shù)組下標(biāo)為i的節(jié)點對象的偏移地址。
然后再通過(Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE) 方法，根據(jù)Node[]和目標(biāo)節(jié)點Node的偏移地址兩個參數(shù)，得到下標(biāo)為i的Node節(jié)點對象。
雖然這樣很繞，不如，但是直接根據(jù)偏移地址去尋找數(shù)組元素效率較高~
3、casTabAt方法
/**
* 通過CAS的方式去向Node數(shù)組指定位置i設(shè)置節(jié)點值，設(shè)置成功返回true，否則返回false
* Node<K,V>[] tab：表示Node[]數(shù)組
* int i：表示數(shù)組下標(biāo)
* Node<K,V> c：期望節(jié)點值
* Node<K,V> v：要設(shè)置的節(jié)點值
*/
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
// 調(diào)用Unsafe的比較并交換去設(shè)置Node[]數(shù)組指定位置的節(jié)點值，參數(shù)如下：
// tab：Node[]數(shù)組
// ((long)i << ASHIFT) + ABASE：下標(biāo)為i數(shù)組桶的偏移地址
// c：期望節(jié)點值
// v：要設(shè)置的節(jié)點值
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
4、setTabAt方法
/**
* 根據(jù)數(shù)組下標(biāo)i，設(shè)置Node[]數(shù)組指定下標(biāo)位置的節(jié)點值：
* Node<K,V>[] tab：表示Node[]數(shù)組
* int i：表示數(shù)組下標(biāo)
* Node<K,V> v：要設(shè)置的節(jié)點值
*/
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
// ((long)i << ASHIFT) + ABASE：下標(biāo)為i數(shù)組桶的偏移地址
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
5、resizeStamp方法
/**
* table數(shù)組擴(kuò)容時，計算出一個擴(kuò)容標(biāo)識戳，當(dāng)需要并發(fā)擴(kuò)容時，當(dāng)前線程必須拿到擴(kuò)容標(biāo)識戳才能參與擴(kuò)容：
*/
static final int resizeStamp(int n) {
// RESIZE_STAMP_BITS：固定值16，與擴(kuò)容相關(guān)，計算擴(kuò)容時會根據(jù)該屬性值生成一個擴(kuò)容標(biāo)識戳
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
=
舉例子分析一下：
當(dāng)我們需要table容量從16 庫容到32時：Integer.numberOfLeadingZeros(16) 會得到，怎么得來的呢？
numberOfLeadingZeros(n)根據(jù)傳入的n，返回當(dāng)前數(shù)值轉(zhuǎn)換為二進(jìn)制后，從高位到地位開始統(tǒng)計，統(tǒng)計有多少個0連續(xù)在一塊：- eg：16 轉(zhuǎn)換二進(jìn)制 => 1 0000 則
numberOfLeadingZeros(16)的結(jié)果就是27，因為Integer是32位，1 0000占5位，那么前面就有(32 - 5)個0，即連續(xù)最長的0的個數(shù)為27個。 (1 << (RESIZE_STAMP_BITS - 1))：其中RESIZE_STAMP_BITS是一個固定值16，與擴(kuò)容相關(guān)，計算擴(kuò)容時會根據(jù)該屬性值生成一個擴(kuò)容標(biāo)識戳。
下面就來計算一下：
// 從16擴(kuò)容到32 16 -> 32 // 用A表示： numberOfLeadingZeros(16) => 1 0000 => 27 => 0000 0000 0001 1011 // 用B表示： (1 << (RESIZE_STAMP_BITS - 1)) => (1 << (16 - 1) => 1000 0000 0000 0000 => 32768 // A | B Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)) ----------------------------------------------------------------- 0000 0000 0001 1011 ---> A 1000 0000 0000 0000 ---> B ------------------- ---> | 按位或 1000 0000 0001 1011 ---> 計算得到擴(kuò)容標(biāo)識戳
6、tableSizeFor方法
/**
* 根據(jù)c,計算得到大于等于c的，最小2的次冪數(shù)，該方法在HashMap源碼中分析過~
* eg：c = 28 ，則計算得到的返回結(jié)果為 32
* c = 28 ==> n=27 => 0b 11011
*
* 11011 | 01101 => 11111 ---- n |= n >>> 1
* 11111 | 00111 => 11111 ---- n |= n >>> 2
* ....
* => 11111 + 1 = 100000 = 32
*/
private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
7、構(gòu)造方法(復(fù)習(xí))
復(fù)習(xí)一下上一篇文章中的并發(fā)HashMap的構(gòu)造方法：
// 無慘構(gòu)造
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));
/**
* sizeCtl > 0
* 當(dāng)目前table未初始化時，sizeCtl表示初始化容量
*/
this.sizeCtl = cap;
}
// 根據(jù)一個Map集合來初始化
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
// sizeCtl設(shè)置為默認(rèn)容量值
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
// 指定初始化容量，和負(fù)載因子
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
// 指定初始化容量，和負(fù)載因子，并發(fā)級別
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// 當(dāng)指定的初始化容量initialCapacity小于并發(fā)級別concurrencyLevel時
if (initialCapacity < concurrencyLevel)
// 初始化容量值設(shè)置為并發(fā)級別的值。
// 即，JDK1.8以后并發(fā)級別由散列表長度決定
initialCapacity = concurrencyLevel;
// 根據(jù)初始化容量和負(fù)載因子，去計算size
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
// 根據(jù)size重新計算數(shù)組初始化容量
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
/**
* sizeCtl > 0
* 當(dāng)目前table未初始化時，sizeCtl表示初始化容量
*/
this.sizeCtl = cap;
}
8、總結(jié)
預(yù)熱結(jié)束后，下一篇文章就是并發(fā)Map比較重點的地方了，即put()寫入操作原理~
也希望大家多多關(guān)注腳本之家的其他內(nèi)容！
相關(guān)文章
這篇文章主要介紹了Java文件操作之按行讀取文件和遞歸遍歷目錄的方法,遍歷目錄文中分別舉了遞歸和非遞歸的例子,需要的朋友可以參考下2016-03-03
本篇文章主要介紹了詳解spring切面使用傳遞給被通知方法的參數(shù)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
JAVA對象中使用?static?和?String?基礎(chǔ)探究
這篇文章主要介紹了JAVA對象中使用static和String基礎(chǔ)探究,文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了Springbean的幾種注入方式都了解嗎，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01
這篇文章主要為大家詳細(xì)介紹了java模擬實現(xiàn)銀行ATM機(jī)操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
java快速解析路徑中的參數(shù)(&與=拼接的參數(shù))
這篇文章主要介紹了java快速解析路徑中的參數(shù)(&與=拼接的參數(shù)),本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧2024-02-02
本篇文章主要介紹了SpringMVC前端和后端數(shù)據(jù)交互總結(jié)，具有一定的參考價值，感興趣的小伙伴們可以參考一下。希望能給你帶來幫助2021-07-07
這篇文章主要介紹了springboot swagger2注解使用，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05
這篇文章主要為大家詳細(xì)介紹了java數(shù)據(jù)庫唯一id生成工具類，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-04-04
這篇文章主要介紹了Java中Retry方法的簡單實現(xiàn),Retry主要是利用Java的lambda表達(dá)式和線程接口實現(xiàn)有返回值和無返回值的重試,思考了下就寫了一個簡易Retry功能分享出來,需要的朋友可以參考下2024-01-01