The introduction
I didn’t plan to write ConcurrentHashMap, but when I talked with a friend about it by chance, I thought I should write it. After all, it is much simpler than synchronized. I’ve read a lot of sutras and I’ve asked to talk about ConcurrentHashMap. So, you have to learn it sooner or later, so take this opportunity to write it down.
The body of the
attribute
private static final int MAXIMUM_CAPACITY = 1 << 30;
// Hash table default value
private static final int DEFAULT_CAPACITY = 16;
// Load factor
private static final float LOAD_FACTOR = 0.75 f;
// Tree threshold. If the bucket list length reaches 8, tree operation may occur
static final int TREEIFY_THRESHOLD = 8;
// The threshold for red-black tree conversion to the linked list
static final int UNTREEIFY_THRESHOLD = 6;
// combine TREEIFY_THRESHOLD with TREEIFY_THRESHOLD to control whether the bucket bit is treed, only when the table array length reaches 64 and a bucket bit
// If the length of the list is 8, treification will occur
static final int MIN_TREEIFY_CAPACITY = 64;
// Minimum step size of thread migration data, a value that controls the minimum range of thread migration tasks
private static final int MIN_TRANSFER_STRIDE = 16;
// For capacity expansion, calculate an identifier generated during capacity expansion
private static int RESIZE_STAMP_BITS = 16;
// Maximum number of threads for concurrent expansion
private static final int MAX_RESIZERS = (1< < (32 - RESIZE_STAMP_BITS)) - 1;
// When the hash value of node is -1, it indicates that the node is FWD
static final int MOVED = -1;
// When the hash value of node is -2, the current node is treed. The current node is a TreeBin object.
// Treebin Object agent operates red-black trees
static final int TREEBIN = -2;
static final int RESERVED = -3; / / can't use
// You can turn a negative number into a positive number, but not the absolute value
static final int HASH_BITS = 0x7fffffff;
// The number of cpus in the current system
static final int NCPU = Runtime.getRuntime().availableProcessors();
// During capacity expansion, the new table in capacity expansion will be referenced to nextTable and set to NULL after capacity expansion
private transient volatile Node<K,V>[] nextTable;
Copy the codeSome of the properties that aren’t really useful aren’t written, don’t matter. But you’ll notice that all of this code is final, which means ConcurrentHashMap doesn’t want you to change it.
// Hash table must be a power tree of length 2
transient volatile Node<K,V>[] table;
// When the baseCount in LongAdder is not contended or the current LongAdder is locked, increments are added to baseCount
private transient volatile long baseCount;
// cellsBusy in LongAdder 0 indicates that the LongAdder is currently unlocked, and 1 indicates that the LongAdder is currently locked
private transient volatile int cellsBusy;
// Array of cells in LongAdder, which is created when baseCount is contended
// The thread computs the hash value to its own cell and adds increments to the specified cell
// Total = sum(cells) + baseCount
private transient volatile CounterCell[] counterCells;
/** * sizeCtl < 0 * 1. -1 indicates that the current table is being initialized (a thread is creating an array of tables). * 2. Indicates that the current table array is being expanded. 16 bits higher indicates that the identifier of the expansion is 16 bits lower. SizeCtl = 0, indicating that the DEFAULT_CAPACITY of the table array is set to size > 0 * * 1. If the table is not initialized, it indicates the initialization size * 2. If the table is initialized, it indicates the triggering condition (threshold) for the next capacity expansion */
private transient volatile int sizeCtl;
/** * Record the current progress during capacity expansion. All threads need to assign interval tasks from transferIndex to perform their own tasks. * /
private transient volatile int transferIndex;
Copy the codeSmall methods
// Get a positive hash value
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
// Get the element specified in table and return it
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);
}
// Use CAS to set the value at the specified location in the array
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
// return >= c to the lowest power of 2
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;
}
Copy the codePut method
Calculates how many buckets each thread can process. Default 16. Initialize the temporary variable nextTable and expand by 2 times. Infinite loop, compute the subscript. Complete the interval and step size judgment. If there is data in the bucket, the data is transferred synchronously. It’s usually split into two pieces like a linked list
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
//binCount Indicates the subscript position of the linked list in the bucket after the current K-V is encapsulated as node and inserted into the specified bucket
//0 indicates that the current bucket bit is null and node can be directly placed
//2 Indicates that the bucket bit may be a red-black tree
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
// the head of the f bucket
// n indicates the array length of the hash table
// I indicates the bucket bit index obtained after the key is addressed
// fh indicates the hash value of the bucket head node
Node<K,V> f; int n, i, fh;
// If the condition is true, it indicates that the table in the map is not initialized and is loaded lazily
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// I indicates the key. The routing addressing algorithm is used to obtain the corresponding key
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
Table [I] == null
// Set the specified array I bucket as the creation Node Node using cas
// Exit the loop on success, and spin the other logic on failure
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// If the condition is true, the head node of the current bucket is FWD, and the map is being expanded.
else if ((fh = f.hash) == MOVED)
// After seeing the FWD node, the current node has the obligation to help the current map to complete the migration of data.
tab = helpTransfer(tab, f);
// The current bucket bit can be either a linked list or a red-black tree agent node treebin
else {
// When the insert key exists, the old value is assigned to oldVal and returns
V oldVal = null;
// Use sync to lock the "head node", which is the theoretical head node, because it will be checked below
synchronized (f) {
// Check whether the current header and tail are the same as the previously obtained header
// To prevent other threads from modifying the head node of the bucket, the current thread sync lock problem
if (tabAt(tab, i) == f) {
// The bucket level is an ordinary linked list
if (fh >= 0) {
//1. If the current insert key is inconsistent with the key of all elements in the linked list, the current insert operation is appended to the end of the linked list. BinCount indicates the length of the linked list
//2. If the current insert key is inconsistent with the key of an element in the linked list, the current insert may be a replacement. BinCount specifies the conflicting position (bincoun-1)
binCount = 1;
// Loop over the map
for (Node<K,V> e = f;; ++binCount) {
K ek;
// If the key of a bucket element in the map is the same as the current key to be inserted, replace it
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
// Prerequisite: The key in the traversal map is not the same as the key of the element being inserted
// 1. The update loop processes the node as the next node of the current node
Check whether the next node is null. If it is null, the current node is at the end of the queue, and data needs to be appended to the end node.
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}// The bucket bit must not be a linked list
// The current bucket bit is the red-black tree agent node treeBin
else if (f instanceof TreeBin) {
Node<K,V> p;
// Set binCount to 2. AddCount () is useful
binCount = 2;
// return a reference
if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}// Indicates that the bucket bit is not null and may be a red-black tree or a linked list
if(binCount ! =0) {
// If binCount >= 8, the bucket bit must be a linked list
if (binCount >= TREEIFY_THRESHOLD)
// Tree operation
treeifyBin(tab, i);
// The data key inserted by the current thread conflicts with the original k-v, and the original data v needs to be returned to the caller.
if(oldVal ! =null)
return oldVal;
break; }}}//1. Count the number of data in the table
//2. Check whether the capacity expansion threshold is reached.
addCount(1L, binCount);
return null;
}
Copy the codeInitialization method
private final Node<K,V>[] initTable() {
// TAB indicates the map.table reference
// sc stands for temporary local sizeCtl values
Node<K,V>[] tab; int sc;
// The hash table is not initialized yet..
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
// < 0: either the current TBALE is being initialized (another thread is creating the table array) and the current thread needs to spin wait;
// The current table array is expanding and the current thread participates in the concurrent expansion
Thread.yield(); // lost initialization race; just spin
SizeCtl = 0, sizeCtl = 0, sizeCtl = 0, sizeCtl = 0. If the table is not initialized, it indicates the initialization size * 3. If the table is initialized, it indicates the triggering condition (threshold) for the next capacity expansion */
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// Prevent the current thread from being initialized again after another thread has completed initialization
// If this condition is true, no other thread has entered the if block, and the current thread is entitled to initialize the table
if ((tab = table) == null || tab.length == 0) {
// Set the array size
int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n];// Finally assign to map.table
table = tab = nt;
// n>>>2 is 1/4 n. Sc = 3/4 N = 0.75*n Indicates the trigger condition for next capacity expansion (threshold).
sc = n - (n >>> 2); }}finally {
// If the current thread is the thread that created the map.table for the first time, sc represents the threshold for the next expansion
// If map.table is not created for the first time and the current thread enters the else if block,
// Set sizeCtl to -1, then change it to the entry value.
sizeCtl = sc;
}
break; }}return tab;
}
Copy the codeStride means the step size assigned to a thread task. What does that mean? To put this in plain English: first we know that if we expand the array, we need to recalculate the indices of the elements in the array. If you do it one by one, it’s too slow. So we’re going to do it interval by interval, and it’s going to be faster. So this interval right here is the step size. Bound indicates the lower bound of the step size (if the step size is 5, then it is 10). General process of capacity expansion thread:
- Check whether the current thread triggers capacity expansion. If yes, the current thread creates a new table. If no, go to the next step
- If the task is allocated successfully, the subscript of the task will be updated. (If the migration is not completed, the data will be migrated. If the migration is successful, the task will be reassigned.
- If is not the last exit: Exit the expansion method if is: Then check that all tasks are completed
- If all tasks are complete: Exit if no FWD node: Yes: update task subscript No: Migrate data
Expansion method
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
// n indicates the length of the table array before capacity expansion
// stride represents the step size assigned to a thread task
int n = tab.length, stride;
// Calculate the step size according to the CPU, but do not read the source code, it is fixed 16 can be ok
if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// Conditional: The current thread is the thread that triggers the capacity expansion.
// Condition not true: the current thread is assisting capacity expansion
if (nextTab == null) { // initiating
try {
// Create an array twice the size of the original array
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n <<1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
/ / the new table
nextTable = nextTab;
// A marker to record the overall location of the migrated data. The index count starts at 1.
transferIndex = n;
}
// Represents the length of the new array
int nextn = nextTab.length;
// FWD node. After a bucket is processed, set the bucket to FWD node.
// Other writer or reader threads will see different logic.
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// Advance the mark
boolean advance = true;
// Complete the tag
boolean finishing = false; // to ensure sweep before committing nextTab
// I indicates the bucket bit assigned to the current thread
// bound represents the lower bound assigned to the current thread task
for (int i = 0, bound = 0;;) {
// f bucket head node. Fh indicates the hash value of the bucket head node
Node<K,V> f; int fh;
/* * What does this loop do? * 1. Assign a task range to the current thread * 2. Maintain the current thread task progress (I represents the bucket bit currently being processed) * 3. Maintains the progress of the map object globally */
while (advance) {
int nextIndex, nextBound;
// Condition 1 is true: indicates that the current thread task has not been completed, there is a corresponding range of buckets to be processed,
// -- I lets the current thread process the next bucket bit.
// Failed: Indicates that the current thread task is completed or not assigned
if (--i >= bound || finishing)
advance = false;
// Preconditions: Indicates that the current thread task is completed or unassigned
// If bucket bits are allocated globally, no buckets can be allocated.
// Set the I variable of the current thread to -1, and execute the procedures related to exit migration task after exiting the loop
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// Prerequisites: 1. The current thread needs to allocate a task range. 2
// If yes, the task is successfully assigned to the current thread
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false; }}// I < 0: no task has been assigned to the current thread
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
// n << 1 = 2 * n, n >>> 1 = n / 2
/ / (n < < 1) - (n > > > 1) = 2 n - n / 2 = 3 n / 2 * 0.75 = 1.5 n = 2 n
// The next expansion threshold.
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit}}// Go to the following logical precondition: the current task is not finished, in progress
// Conditional: No data is stored in the bucket. You only need to set this bucket to FWD
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// If the condition is true, the bucket has been migrated.
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
// The current bucket has data, and node is not a FWD node, which needs to be migrated
else {
// Lock the head node of the current bucket
synchronized (f) {
// If you lock it wrong, someone else will beat you to it
if (tabAt(tab, i) == f) {
// ln: low list reference
// hn: high level list references
// Let's talk about high and low. When we expand, we're definitely going to recalculate buckets with linked lists
// Then the list elements can be divided into high (first 1) and low (first 0) by calculation.
// Then the list is broken up, the lower part is the original bucket number, and the higher part is the new bucket number
Node<K,V> ln, hn;
// The bucket level is a linked list
// The rest of the process is disgusting
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
for(Node<K,V> p = f.next; p ! =null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// Create a low list
if (runBit == 0) {
ln = lastRun;
hn = null;
}
// High list forming
else {
hn = lastRun;
ln = null;
}
for(Node<K,V> p = f; p ! = lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
// Indicates that the current bucket bit is the red-black treeBin agent
else if (f instanceof TreeBin) {
// The head node is converted to teebin
TreeBin<K,V> t = (TreeBin<K,V>)f;
//h: high, L: low
// Start and end of the list
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
// Loop the bidirectional list in treebin
for(Node<K,V> e = t.first; e ! =null; e = e.next) {
// h handles the hash value of the current element
int h = e.hash;
// Built using the current node
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null.null);
// Indicates that the current node is a low-chain node
// High and low linked lists use tail interpolation
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
// Indicates that the current node is a high-chain node
else {
if ((p.prev = hiTail) == null)
hi = p;
elsehiTail.next = p; hiTail = p; ++hc; }}// Check whether the current list node is less than or equal to 6.
// Convert the treebin list to a Node listln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc ! =0)?newTreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc ! =0)?new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Copy the codeThe get method
public V get(Object key) {
/ / TAB reference map. The table
//e The current element
//p target node
//n Table array length
//eh Current element hash
//ek Current element key
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
//条件一：(tab = table) != null
//true-> Indicates that data has been put and the table inside the map has been initialized
//false-> Indicates that no data is put after the map is created. The table inside the map is delayed initialization and the creation logic is triggered only when data is written for the first time.
// condition two :(n = tab.length) > 0 true-> indicates that the table is initialized
(e = tabAt(TAB, (n-1) &h))! = null
//true-> The bucket bit addressed by the current key has a value
//false-> If the bucket is null, return null
if((tab = table) ! =null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) ! =null) {
// Compare the hash value of the element and the bucket element
if ((eh = e.hash) == h) {
if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
return e.val;
}
// Conditional:
-1 FWD Indicates that the table is being expanded and the data of the bucket queried has been migrated
2.-2 The TreeBin node is queried using the find method provided by TreeBin.
else if (eh < 0)
return(p = e.find(h, key)) ! =null ? p.val : null;
// Buckets form linked lists
while((e = e.next) ! =null) {
if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
returne.val; }}return null;
}
/* * Let's take a look at eh < 0 * * let's talk about FWD first, which treeBin will cover later
static final class ForwardingNode<K.V> extends Node<K.V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null.null.null);
this.nextTable = tab;
}
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
// true -> 1
// -> 2. It was later set to null
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (;;) {
// Eh and EK are elements in the new table
int eh; K ek;
// Returns if the element to be searched matches the bucket element.
if((eh = e.hash) == h && ((ek = e.key) == k || (ek ! =null && k.equals(ek))))
return e;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
// eh < 0 is not FWD yet, so it is treebin
else
return e.find(h, k);
}
/ / list
if ((e = e.next) == null)
return null; }}}}Copy the codeThe remove method
public V remove(Object key) {
// The element corresponding to the key is set to null, equivalent to deleting.
return replaceNode(key, null.null);
}
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
//f indicates the bucket header
//n indicates the length of the current table array
// I indicates that the hash matches the bucket subscript
//fh indicates the hash of the bucket header
Node<K,V> f; int n, i, fh;
// Return null if table is empty or has no elements
// If the element is not null in the hash bucket, then null is returned
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// If the condition is true, the map is being expanded
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// The current bucket bit is normal and not null
else {
V oldVal = null;
boolean validated = false;
// Lock the head node of the current bucket
synchronized (f) {
if (tabAt(tab, i) == f) {
// fh > 0 indicates that the current element is a normal element or a linked list
if (fh >= 0) {
validated = true;
for (Node<K,V> e = f, pred = null;;) {
K ek;
// success: indicates that the element of the loop is the same as that of the checked element
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
V ev = e.val;
if (cv == null|| cv == ev || (ev ! =null && cv.equals(ev))) {
oldVal = ev;
if(value ! =null)
e.val = value;
else if(pred ! =null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break; }}// The current node is a red-black tree node
// Conditional: TreeBin node.
else if (f instanceof TreeBin) {
validated = true;
// Convert to the actual type TreeBin t
TreeBin<K,V> t = (TreeBin<K,V>)f;
//r represents the root of a red-black tree
//p indicates that nodes with the same key are found in the red-black tree
TreeNode<K,V> r, p;
// (r = t.oot)! = null theoretically true
Treenode.findtreenode searches for the key (including its own node) from the current node.
// true-> The node corresponding to the key is found. Will be assigned to p
if((r = t.root) ! =null &&
(p = r.findTreeNode(hash, key, null)) != null) {
// save p.val to pv
V pv = p.val;
// CV == null
/ / condition 2: CV = = pv | | (pv! = null && cv.equals(pv)) : Indicates that the value of the pair is the same as that of the current p node
if (cv == null|| cv == pv || (pv ! =null && cv.equals(pv))) {
// Replace or delete operations
oldVal = pv;
// Replace the operation
if(value ! =null)
p.val = value;
// Delete operation
else if (t.removeTreeNode(p))
// There is no judgment here. confused
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// If the wrong object is locked, then "validated" is false and the next spin is entered
if (validated) {
if(oldVal ! =null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break; }}}return null;
}
Copy the codeTreeBin
static final class TreeBin<K.V> extends Node<K.V> {
TreeNode<K,V> root;
// The first node of the list
volatile TreeNode<K,V> first;
// wait thread (current lockState is read lockState)
volatile Thread waiter;
The write lock state is exclusive. In terms of the hash, only one writer thread actually enters the TreeBin at a time. * lockState = 1 * 2. Read lockState read lock is shared, multiple threads can access the TreeBin object at the same time. * Each thread gives the lockStat + 4 * 3. The wait state (the writer thread is waiting), while a reader thread in the TreeBin is currently reading data, the writer thread cannot modify the data, so the lowest 2 bits of the lockState are set to 0b 10 */
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
TreeBin(TreeNode<K,V> b) {
// Setting hash to -2 indicates that the node is a TreeBin node
super(TREEBIN, null.null.null);
// Use first to reference the treeNode list
this.first = b;
//r red black tree root reference
TreeNode<K,V> r = null;
//x represents the current node traversed
for(TreeNode<K,V> x = b, next; x ! =null; x = next) {
next = (TreeNode<K,V>)x.next;
// Forces the left and right subtrees of the currently inserted node to be null
x.left = x.right = null;
// If this condition is true, the current red-black tree is an empty tree, so set the inserted element to the root node
if (r == null) {
// The parent of the root node must be null
x.parent = null;
// Change the color to black
x.red = false;
// let r refer to the object to which x points.
r = x;
}
else {
// If it's not the first time, the else branch will be added, and the red-black tree will already have data
//k indicates the key of the node to be inserted
K k = x.key;
//h indicates the hash of the node to be inserted
int h = x.hash;
//kc indicates the class type of the key of the inserted nodeClass<? > kc =null;
//p represents a temporary node to find the parent of the inserted node
TreeNode<K,V> p = r;
for (;;) {
//dir (-1, 1)
//-1 indicates that the hash value of the inserted node is greater than that of the current node P
//1 indicates that the hash value of the inserted node is smaller than that of the current node P
//ph p represents a hash for a temporary node that looks for the parent node of the inserted node
int dir, ph;
// Temporary node key
K pk = p.key;
// The hash value of the inserted node is smaller than that of the current node
if ((ph = p.hash) > h)
// Inserting a node may require inserting it into the left child of the current node or continuing the search in the left child tree
dir = -1;
// The hash value of the inserted node is greater than that of the current node
else if (ph < h)
// To insert a node, you may need to insert it into the right child of the current node or continue searching in the right child tree
dir = 1;
// If CASE3 is executed, the hash of the current inserted node is the same as that of the current node, and the final hash will be sorted in CASE3. In the end
// Get dir not 0, (-1, 1)
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// XP wants to represent the parent of the inserted node
TreeNode<K,V> xp = p;
// If the condition is true, node P is the parent node of the node to be inserted
// If the condition is not true, it indicates that there are layers under the p node. You need to point P to the left or right child node of P to continue the search.
if ((p = (dir <= 0)? p.left : p.right) ==null) {
// Set the parent of the node to be the current node
x.parent = xp;
// It is smaller than the P node and needs to be inserted into the left child of the P node
if (dir <= 0)
xp.left = x;
// It is larger than P and needs to be inserted into the right child of P
else
xp.right = x;
// After inserting nodes, the red-black tree nature may be broken, so you need to call the balancing method
r = balanceInsertion(r, x);
break; }}}}// Assign r to the root reference of the TreeBin object.
this.root = r;
assert checkInvariants(root);
}
Copy the codeconclusion
Almost all updated source code is very tired, broken heart want to sleep. In fact, there is no need to do so, if you can read my last article for an interview. It’s also very well written.
Standing on the shoulders of giants
Notes from B station Xiao Liu speak source. Very good teacher, you can sign up to see.