Analysis of ConcurrentHashMap: Analysis of some small methods in preheating of
- 2021-09-12 01:20:35
- OfStack
Catalogue 1, spread (int h) Method 2, tabAt Method 3, casTabAt Method 4, setTabAt Method 5, resizeStamp Method 6, tableSizeFor Method 7, Construction Method (Review) 8, Summary
The main member properties, inner classes, and constructors of concurrent HashMap were described in the previous article:
Before formally analyzing concurrent HashMap member methods, let's analyze the word method functions in some inner classes:
First, let's look at the calculation method of hash member attribute value in ConcurrentHashMap inner class Node
spread(int h
):
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// This property is passed through the spread(int h) Calculated by the method ~
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) method
/**
* Calculation Node Node hash Algorithm of value: parameter h For hash Value
* eg:
* h2 The binary system is --> 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
* Note: (h ^ (h >>> 16)) The purpose is to make h The height of 16 Bits also participate in addressing calculation, so that the hash Values are more dispersed and reduced hash Conflict generation ~
* ------------------------------------------------------------------------------
* 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
* Note: (h ^ (h >>> 16)) The results obtained are then & HASH_BITS , the purpose is to get hash Value results are always 1 Positive number
*/
static final int spread(int h) {
// Let the original hash Value XOR ^ Original hash Right shift of value 16 Bit, and then with & Upper HASH_BITS(0x7fffffff: 2 The binary system is 31 A 1)
return (h ^ (h >>> 16)) & HASH_BITS;
}
tabAt (Node) is described below < K,V > [] tab, int i) Method: Gets the Node node of the tab (Node []) array that specifies the subscript i.
2. tabAt method
/**
* Get tab(Node[]) Array specified subscript i Adj. Node Node
* Node<K,V>[] tab : Indicates Node[] Array
* int i Represents an array subscript
*/
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
// ((long)i << ASHIFT) + ABASE The role of: Please see the following analysis description ~
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
In the analysis
((long)i << ASHIFT) + ABASE
First, review the meaning of some attribute fields introduced in the previous article: ConcurrentHashMap source code parsing _01 member attributes, internal classes and constructor analysis:
// Node Array of class Object
Class<?> ak = Node[].class;
// U.arrayBaseOffset(ak) : According to as Get Node[] Array number 1 Offset address of elements ABASE
ABASE = U.arrayBaseOffset(ak);
// scale Represents every 1 The size of space occupied by 10 cells, that is, scale Denote Node[] In the array, each 1 Space occupied by 10 units
int scale = U.arrayIndexScale(ak);// scale Must be 2 The second power of
// numberOfLeadingZeros(scale) According to scale Returns that the current numeric value is converted to 2 After the binary system, from the high position to the position, how many statistics are there 0 Continuous in 1 Block: eg, 8 Conversion 2 Binary system =>1000 Then numberOfLeadingZeros(8) The result is that 28 Why? Because Integer Yes 32 Bit, 1000 Account for 4 Bit, then there is 32-4 A 0 That is, the longest continuous 0 The number of is 28 A
// 4 Conversion 2 Binary system =>100 Then numberOfLeadingZeros(8) The result is that 29
// ASHIFT = 31 - Integer.numberOfLeadingZeros(4) = 2 Then ASHIFT What is the function of? In fact, it has array addressable 1 Functions:
// Get the subscript as 5 Adj. Node[] Offset address of array element ( Storage address ) Suppose at this time According to scale Calculated ASHIFT = 2
// ABASE + (5 << ASHIFT) == ABASE + (5 << 2) == ABASE + 5 * scale( The multiplication operation is inefficient ) You get the subscript 5 Offset address of array elements of
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
From the review of the above several attribute fields, it is not difficult to draw:
((long)i << ASHIFT) + ABASE
Is to get the current
Node[]
The offset address of the node object whose array subscript is i.
And then through
(Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE)
Method, according to
Node[]
And
目标节点Node的偏移地址
Two parameters, resulting in an Node node object subscript to i.
Although this is very round and inferior, it is more efficient to find array elements directly according to offset addresses ~
3. casTabAt method
/**
* Pass CAS The way to go Node Array specifies the position i Set the node value and return successfully true Otherwise, return false
* Node<K,V>[] tab : Indicates Node[] Array
* int i Represents an array subscript
* Node<K,V> c Expected node value
* Node<K,V> v Node value to set
*/
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
// Call Unsafe Compare and swap to set Node[] The node value at the specified position of the array, with the following parameters:
// tab : Node[] Array
// ((long)i << ASHIFT) + ABASE : Subscribed to i Offset address of array bucket
// c Expected node value
// v Node value to set
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
4. setTabAt method
/**
* According to array subscript i , setting Node[] Array specifies the node value at the subscript position:
* Node<K,V>[] tab : Indicates Node[] Array
* int i Represents an array subscript
* Node<K,V> v Node value to set
*/
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
// ((long)i << ASHIFT) + ABASE : Subscribed to i Offset address of array bucket
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
5. resizeStamp method
/**
* table When the array is expanded, calculate the 1 When concurrent expansion is needed, the current thread must get the expansion identification stamp to participate in expansion:
*/
static final int resizeStamp(int n) {
// RESIZE_STAMP_BITS Fixed value 16 Is related to expansion, and will be generated according to this attribute value when calculating expansion 1 Expansion identification stamp
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
=For example, sub-analysis 1:
When we need table capacity from 16 to 32:
Integer.numberOfLeadingZeros(16)
Will get it, how did you get it?
numberOfLeadingZeros(n)
According to the incoming
n
After the current value is converted to binary, start counting from high position to position, and count how many zeros are continuously in 1 block:
eg: 16 Conversion Binary =
>
1 000 0
((long)i << ASHIFT) + ABASE0
) The result is that
27
, because
Integer
Is 32 bits,
1 0000
Take 5 places, then there is in front of it
(32 - 5)
The number of zeros, that is, the number of consecutive longest zeros is 27.
(1 << (RESIZE_STAMP_BITS - 1))：
Among them
RESIZE_STAMP_BITS
Is a fixed value of 16, which is related to expansion. When calculating expansion, an expansion identification stamp will be generated according to this attribute value.
Let's calculate 1 below:
// From 16 Expand to 32
16 -> 32
// Use A Indicates:
numberOfLeadingZeros(16) => 1 0000 => 27 => 0000 0000 0001 1011
// Use B Indicates:
(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
------------------- ---> | Bitwise or
1000 0000 0001 1011 ---> Calculate and obtain the expansion identification stamp
6. tableSizeFor method
/**
* According to c, Calculate to be greater than or equal to c Of, the smallest 2 The second power of, the method is in the HashMap Analyzed in the source code ~
* eg : c = 28 The calculated return result is 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. Construction method (review)
Review the construction method of concurrent HashMap in the previous article under 1:
// Non-miserable structure
public ConcurrentHashMap() {
}
// Specify the initialization capacity
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
* When at present table When not initialized, sizeCtl Indicates initialization capacity
*/
this.sizeCtl = cap;
}
// According to 1 A Map Collection to initialize the
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
// sizeCtl Set to the default capacity value
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
// Specify the initialization capacity and load factor
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
// Specify initialization capacity, and load factor, concurrency level
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// When the specified initialization capacity initialCapacity Less than concurrency level concurrencyLevel Hour
if (initialCapacity < concurrencyLevel)
// The initialization capacity value is set to a value at the concurrency level.
// That is, JDK1.8 The later concurrency level is determined by the hash table length
initialCapacity = concurrencyLevel;
// According to the initialization capacity and load factor, calculate size
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
// According to size Recalculate array initialization capacity
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
/**
* sizeCtl > 0
* When at present table When not initialized, sizeCtl Indicates initialization capacity
*/
this.sizeCtl = cap;
}
8. Summary
After the warm-up, the next article is the focus of concurrent Map, that is, the principle of put () write operation ~
I also hope everyone will pay more attention to other contents of this site!