preface

Reading Suggestions: Java7 HashMap > Java7 ConcurrentHashMap > Java8 HashMap > Java8 ConcurrentHashMap The reading threshold can be lowered appropriately.

Prerequisite: This article is looking at source code, so you should at least be familiar with its interfaces. For concurrency, you should also know the CAS, ReentrantLock, and UNSAFE operations, which are not covered here. Java8 uses red-black trees, but this article will not expand on them, so please find out for yourself.

1. Java7 HashMap

HashMap is the simplest, both because it is familiar and because it does not support concurrent operations, so the source code is very simple.

First, let’s use the following diagram to illustrate the structure of a HashMap.

This is just a schematic diagram, because it does not take into account the expansion of the array. More on this later.

In general, the inside of a HashMap is an array, and each element in the array is a one-way list.

In the figure above, each green entity is an instance of the nested class Entry, which contains four attributes: key, Value, Hash value, and Next for a one-way linked list.

Capacity: Indicates the current array capacity. The capacity is always 2^n and can be expanded. After the array capacity is expanded, the array size is twice that of the current one.

LoadFactor: loadFactor. The default value is 0.75.

Threshold: capacity expansion threshold, equal to capacity x loadFactor

1.1 PUT Process Analysis

Or relatively simple, follow the code to go through.

public V put(K key, V value) {
    // When inserting the first element, initialize the array size
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // If the key is null, interested parties can look inside and eventually place the entry in table[0]
    if (key == null)
        return putForNullKey(value);
    // 1. Hash the key
    int hash = hash(key);
    // 2. Find the corresponding array subscript
    int i = indexFor(hash, table.length);
    // 3. Run the list at the corresponding index to see if duplicate keys already exist.
    // If so, override it, and the put method returns the old value
    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. There is no duplicate key. Add this entry to the linked list
    addEntry(hash, key, value, i);
    return null;
}
Copy the code

1.1.1 Array Initialization

Initialize the array when the first element is inserted into the HashMap. Determine the initial array size and calculate the threshold for array expansion.

private void inflateTable(int toSize) {
    // Make sure the array size is 2 ^ n.
    New HashMap(20), then the initial array size is 32
    int capacity = roundUpToPowerOf2(toSize);
    // Calculate the capacity expansion threshold: capacity x loadFactor
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // Initialize the array
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity); //ignore
}
Copy the code

There is a way to keep the array size to the power of 2. Java7 and Java8 require HashMap and ConcurrentHashMap, but the implementation code is slightly different, as you’ll see later.

1.1.2 Calculate the specific array location

This is easy enough to imagine ourselves: modulo the array length using the hash value of the key.

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);
}
Copy the code

This method is very simple, simply take the lowest n bits of the hash value. For example, if the array length is 32, the lower 5 bits of the hash value of the key are used as its subscript position in the array.

1.1.3 Adding a Node to a Linked List

Once the array subscript is found, the key is evaluated first, and if there are no duplicates, the new value is ready to be placed in the head of the list.

void addEntry(int hash, K key, V value, int bucketIndex) {
    // If the current HashMap size has reached the threshold and there are already elements in the array where the new value will be inserted, expand it
    if ((size >= threshold) && (null! = table[bucketIndex])) {// Expand capacity, which will be explained later
        resize(2 * table.length);
        // Recalculate the hash value after capacity expansion
        hash = (null! = key) ? hash(key) :0;
        // Recalculate the new index after expansion
        bucketIndex = indexFor(hash, table.length);
    }
    / / to look down
    createEntry(hash, key, value, bucketIndex);
}
// put the new value in the head of the list and 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++;
}
Copy the code

The main logic of this method is to determine whether to expand, expand if necessary, and then insert the new data into the head of the linked list at the corresponding location of the expanded array.

1.1.4 Array Expansion

If the size of the array to be inserted has reached the threshold and there are already elements in the array to be inserted, then the array size will be doubled.

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // A new array
    Entry[] newTable = new Entry[newCapacity];
    // Migrate the values from the original array to the new, larger array
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the code

Expansion is replacing the original small array with a new large array and moving the values from the original array to the new array.

Due to the double expansion, all the nodes of the linked list in the original table[I] will be split into newTable[I] and newTable[I + oldLength] of the new array during the migration. If the original array length is 16, all elements in the linked list at table[0] will be allocated to newTable[0] or newTable[16] in the new array after expansion. The code is a little bit simpler, so I won’t expand it here.

1.2 GET process analysis

In contrast to the PUT process, the GET process is very simple.

  1. Computes the hash value based on the key.
  2. Find the corresponding array subscript: hash & (length — 1).
  3. Iterate through the list at the array location until you find keys that are equal (== or equals).
public V get(Object key) {
    // If the key is null, it will be placed in table[0]
    if (key == null)
        return getForNullKey();
    // 
    Entry<K,V> entry = getEntry(key);
 
    return null == entry ? null : entry.getValue();
}
Copy the code

getEntry(key):

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
 
    int hash = (key == null)?0 : hash(key);
    // Determine the array subscript, and then iterate through the list from the beginning until it is found
    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;
}
Copy the code

2. Java7 ConcurrentHashMap

ConcurrentHashMap has the same idea as HashMap, but is more complex because it supports concurrent operations.

The entire ConcurrentHashMap consists of segments that stand for “part” or “Segment”, and are often described as segmented locks. Notice how many places I used “slots” to represent a segment.

ConcurrentHashMap is an array of segments. A Segment is locked by inheritingReentrantLock. As long as each Segment is thread-safe, global thread-safe is achieved.

ConcurrencyLevel: concurrencyLevel, number of concurrent sessions, number of segments. The default value is 16, which means that ConcurrentHashMap has 16 Segments, so in theory up to 16 concurrent writes can be supported at this point, as long as their operations are distributed over different Segments. This value can be set to another value at initialization, but it cannot be expanded once initialized.

Each Segment looks like a HashMap, but it’s thread safe, so it’s a bit more difficult to handle.

2.1 the initialization

InitialCapacity: indicates the initialCapacity of the entire ConcurrentHashMap. This value should be evenly allocated to each Segment.

The Segment array cannot be expanded, so the loadFactor is for internal use within each 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;
    // Calculate the parallelism level ssize, because keep the parallelism level 2 ^ n
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    ConcurrencyLevel is 16 and sshift is 4
    // Then calculate the segmentShift to 28 and the segmentMask to 15, which will be used later
    this.segmentShift = 32 - sshift;
    this.segmentMask = ssize - 1;
 
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
 
    InitialCapacity is the initial size of the entire map.
    // Calculate the size of each Segment based on initialCapacity
    // If initialCapacity is 64, then each Segment or "slots" can be divided into 4 segments
    int c = initialCapacity / ssize;
    if (c * ssize < initialCapacity)
        ++c;
    // MIN_SEGMENT_TABLE_CAPACITY is 2 by default. This value is also important because then, for specific slots,
    // Insert one element and it will not expand. Insert a second element and it will expand
    int cap = MIN_SEGMENT_TABLE_CAPACITY; 
    while (cap < c)
        cap <<= 1;
 
    // Create Segment array,
    // Create the first element of the array 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];
    // Write segment[0] to array
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}
Copy the code

After initialization, we have an array of segments.

The new ConcurrentHashMap() constructor does not take any arguments.

  • The Segment array is 16 in length and cannot be expanded
  • Segment[I] default size = 2; load factor = 0.75; initial threshold = 1.5
  • Initialize segment[0]; null segment[0]
  • The current Value of segmentShift is 32 — 4 = 28, and segmentMask is 16 — 1 = 15. Let’s simply translate these into shift numbers and masks, which will be needed soon

2.2 PUT Process analysis

Let’s take a look at the main process of PUT, with some key details described later.

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    // 1. Compute the hash value of the key
    int hash = hash(key);
    // 2. Locate position J in Segment array according to hash value
    // Hash is 32 bits, unsigned right segmentShift(28) bits, leaving 4 bits lower,
    // Then do an and with the segmentMask(15), which means j is the last four bits of the hash value, which is the array subscript of the slot
    int j = (hash >>> segmentShift) & segmentMask;
    Int segment[0]; // Initialize segment[0];
    // ensureSegment(j) initializes segment[j]
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
        s = ensureSegment(j);
    // 3. Insert the new value into slot S
    return s.put(key, hash, value, false);
}
Copy the code

The first layer is very simple: you can quickly find the Segment based on the hash value, and then put operations inside the Segment.

The Segment consists of an array and a linked list.

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // Obtain the exclusive lock on this segment before writing to it
    // Take a look at the main process
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        // This is an array inside the segment
        HashEntry<K,V>[] tab = table;
        // Use the hash value to find the array index that should be placed
        int index = (tab.length - 1) & hash;
        // First is the head of the list at that position in the array
        HashEntry<K,V> first = entryAt(tab, index);
 
        // This is a long for loop, but it's easy to understand if there are no elements at all and if there is already a list
        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) {// Overwrite the old value
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                // Continue to follow the list
                e = e.next;
            }
            else {
                // Whether node is null depends on how the lock is acquired, but it doesn't matter here.
                // If not null, set it directly to the linked list header; If null, initialize and set to the linked list header.
                if(node ! =null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
 
                int c = count + 1;
                // If the segment exceeds the threshold, the segment needs to be expanded
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node); // This will be discussed later
                else
                    // If the threshold is not reached, place node at the index position of the array TAB,
                    // Set the new node to the head of the original list
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break; }}}finally {
        / / unlock
        unlock();
    }
    return oldValue;
}
Copy the code

The overall process is relatively simple, because the segment is protected by an exclusive lock, so the operation inside the segment is not complicated. We’ll cover the concurrency problem later.

That’s the end of the PUT operation, and let’s talk about a few of the key operations.

2.2.1 Initializing slots: ensureSegment

The ConcurrentHashMap initializes the first slot segment[0]. For other slots, the ConcurrentHashMap initializes the first slot segment when the first value is inserted.

Concurrency needs to be considered here because it is possible for multiple threads to initialize the same segment[k] at the same time, but only one of them succeeds.

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) {
        // Initialize segment[0]
        // Initialize segment[k] with array length and load factor at segment[0]
        // Segment [0] may have already been expanded
        Segment<K,V> proto = ss[0];
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);
 
        // Initialize the array inside segment[k]
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
            == null) { // Check again if the slot is initialized by another thread.
 
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // Use the while loop, internal CAS, the current thread successfully set the value or another thread successfully set the value, exit
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break; }}}return seg;
}
Copy the code

In general, ensureSegment(int k) is simple, and CAS is used to control concurrent operations.

2.2.2 Obtaining a write lock: scanAndLockForPut

As we saw earlier, when putting to a segment, node = tryLock() is called first. Null: scanAndLockForPut(key, hash, value), which means that a tryLock() is performed to quickly acquire the exclusive lock on the segment. If that fails, go to scanAndLockForPut to obtain the lock.

Now let’s analyze how to control locking in this method.

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
 
    // Loop to get the lock
    while(! tryLock()) { HashEntry<K,V> f;// to recheck first below
        if (retries < 0) {
            if (e == null) {
                if (node == null) // speculatively create node
                    // The list at that position in the array is empty without any elements
                    // Of course, another reason to enter here is that tryLock() failed, so there is concurrency in the slot, not necessarily in that position
                    node = new HashEntry<K,V>(hash, key, value, null);
                retries = 0;
            }
            else if (key.equals(e.key))
                retries = 0;
            else
                // Go down the list
                e = e.next;
        }
        // If the number of retries exceeds MAX_SCAN_RETRIES (single-core, multi-core, 64), the lock is stopped and the queue is blocked
        // lock() is a blocking method until it returns after acquiring the lock
        else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        }
        else if ((retries & 1) = =0 &&
                 // A new element is added to the list as a new header
                 // So the strategy here is to iterate over the scanAndLockForPut method
                 (f = entryForHash(this, hash)) ! = first) { e = first = f;// re-traverse if entry changed
            retries = -1; }}return node;
}
Copy the code

The method has two exits, either when tryLock() succeeds and the loop terminates, or when MAX_SCAN_RETRIES exceeds its attempts to enter the lock() method, which blocks and waits until the exclusive lock succeeds.

This method may seem complicated, but it actually does one thing: get the exclusive lock on the segment and instantiate Node if necessary.

2.2.3 Capacity Expansion: Rehash

The size of the segment array is doubled by the size of the HashEntry[] array inside the segment array.

Insert the segment in a way that will cause the number of elements in the segment to exceed the threshold. Insert the segment in a way that will cause the number of elements in the segment to exceed the threshold.

This method doesn’t need to worry about concurrency because at this point, the exclusive lock on the segment is held.

// Node is the data that needs to be added to the new array after the expansion.
private void rehash(HashEntry<K,V> node) {
    HashEntry<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    / / 2 times
    int newCapacity = oldCapacity << 1;
    threshold = (int)(newCapacity * loadFactor);
    // Create a new array
    HashEntry<K,V>[] newTable =
        (HashEntry<K,V>[]) new HashEntry[newCapacity];
    // If the new mask is expanded from 16 to 32, then the size of the mask is 31, corresponding to binary '000... 00011111 '
    int sizeMask = newCapacity - 1;
 
    // Split the list at position I into position I and I +oldCap
    for (int i = 0; i < oldCapacity ; i++) {
        // e is the first element in the list
        HashEntry<K,V> e = oldTable[i];
        if(e ! =null) {
            HashEntry<K,V> next = e.next;
            // Calculate the position to be placed in the new array,
            // If the array length is 16 and e is at oldTable[3], then idx can only be 3 or 3 + 16 = 19
            int idx = e.hash & sizeMask;
            if (next == null)   // There is only one element in this position, which is easier to handle
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                // e is the list header
                HashEntry<K,V> lastRun = e;
                // idx is the new position of the current list header e
                int lastIdx = idx;
 
                // The following for loop finds a lastRun node, after which all elements are to be grouped together
                for(HashEntry<K,V> last = next; last ! =null;
                     last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                // Place the list of lastRun and all subsequent nodes at lastIdx
                newTable[lastIdx] = lastRun;
                // Handle the node before lastRun,
                // These nodes may be assigned to another list, or to the list above
                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] = newHashEntry<K,V>(h, p.key, v, n); }}}}// Place the new node at the head of one of the two lists in the new array
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}
Copy the code

The expansion here is a bit more complicated than the previous HashMap, and the code is a bit more difficult to understand. There are two for loops right next to each other, so what’s the use of the first for?

A closer look shows that it would have worked without the first for loop, but if there were more nodes after the lastRun, it would have been worth it. Because we only need to clone the nodes in front of lastRun, the following string of nodes will follow lastRun without doing anything.

I think Doug Lea’s idea is also interesting, but the worst case scenario is that every lastRun is the last or very last element in the list, and the loop is a bit wasted. However, Doug Lea also stated that according to the statistics, if the default threshold is used, only about 1/6 nodes need to be cloned.

2.3 GET process analysis

Compared to put, get is really not that easy.

  1. Compute the hash value to find the exact location in the Segment array, or the “slot” we used earlier.
  2. Slot is also an array, using the hash to find the specific location in the array
  3. So here’s the list, and you can just follow the list
public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    / / 1. Hash value
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // 2. Find the corresponding segment based on the hash
    if((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) ! =null&& (tab = s.table) ! =null) {
        // 3. Select * from the list where the segment resides
        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)))
                returne.value; }}return null;
}
Copy the code

2.4 Analysis of concurrency problems

Now that we’ve talked about put and GET, we can see that there is no lock in get, so naturally we need to worry about concurrency.

The operation put to add nodes and the operation remove to remove nodes both need to add exclusive locks on the segment, so there is no problem between them naturally. What we need to consider is that put or remove operations occur in the same segment when we get.

  1. Thread safety of put operations.

    • The initialization slot, which we talked about earlier, uses CAS to initialize the array in the Segment.
    • Adding a node to the list is inserted into the header, so it doesn’t matter if the GET operation is already in the middle of the list traversal. Another concurrency problem, of course, is that after put, the get operation needs to ensure that the node just inserted into the header is read, depending on the unsafe. putOrderedObject used in the setEntryAt method.
    • Expansion. Expansion creates a new array, migrates the data, and finally sets newTable to the property table. So, if the get operation is also running, then it doesn’t matter. If the get operation is running first, then the query will be performed on the old table. If put comes first, the visibility guarantee for put is that the table uses volatile.
  2. Thread-safety of the remove operation.

    Remove operation we did not analyze the source code, so here said readers interested in the source code or need to check.

    The get operation traverses the list, but the remove operation “breaks” the list.

    If the node get operation broken by remove has already passed, then there is no problem.

    If remove destroys a node first, consider two cases. If the node is a header, you need to set the next of the header to the element at that position in the array. Even though table is volatile, volatile does not guarantee the visibility of operations inside the array. Therefore, the source code uses UNSAFE to manipulate arrays. Look at the method setEntryAt. 2. If the node to be deleted is not a header, it will connect the successor node of the deleted node to the precursor node. The concurrency guarantee here is that the next attribute is volatile.

3. Java8 HashMap

Java8 makes some changes to HashMap, but the big difference is that it leverages red-black trees, so it consists of arrays, linked lists, and red-black trees.

Java7 HashMap can quickly locate the index of the array based on the hash value, but then we need to go down the list to find the index. The time complexity depends on the length of the list, O(n).

To reduce this overhead, in Java8, when the list has more than eight elements, the list is converted to a red-black tree, reducing the time complexity of lookups at these locations to O(logN).

Here’s a simple illustration:

Note that the diagram above is a schematic, mainly describing the structure, which will not reach this state, because so much data has already been expanded.

Below, we still use the code to introduce it, personal feeling, Java8 source code is less readable, but a little more concise.

Java7 uses Entry to represent each data Node in a HashMap. Java8 uses Node, which is basically the same, with key, Value, Hash, and next attributes. However, Node can only be used for linked lists. The red-black tree case requires TreeNode.

We can determine whether it is a linked list or a red-black tree based on whether the first Node in the array element is a Node or a TreeNode.

3.1 PUT Process Analysis

public V put(K key, V value) {
    return putVal(hash(key), key, value, false.true);
}
 
// If the third argument onlyIfAbsent is true, the put operation is performed only when the key does not exist
// The fourth parameter evict we don't care about here
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // The first time a value is put, the following resize() is triggered. Java7-like first put also initializes the array length
    // The first resize is a bit different from the subsequent expansion, because this time the array is initialized from null to the default 16 or custom initial capacity
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Find the array index. If there is no value, initialize Node and place it there
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
 
    else {// There is data at this position in the array
        Node<K,V> e; K k;
        // First, determine whether the first data in the position is "equal" to the data we want to insert, if so, fetch the node
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // If the node represents a red-black tree, call the red-black tree interpolation method. This article does not expand the red-black tree
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // The array is a linked list at this position
            for (int binCount = 0; ; ++binCount) {
                // Insert to the back of the list (Java7 inserts to the front of the list)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD is 8, so if the newly inserted value is the ninth in the list
                    // Triggers the following treeifyBin, which converts the list to a red-black tree
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // If you find "equal" keys in the list (== or equals)
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    // break, then e is the node "equal" to the key of the new value to be inserted
                    break; p = e; }}// e! =null indicates that the old key is "equal" to the inserted key.
        // For the put we are analyzing, the following if is simply "overwriting" the value and then returning the old value
        if(e ! =null) {
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // If the HashMap has exceeded the threshold due to the insertion of this value, it needs to be expanded
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

A slight difference from Java7, where values are interpolated before values are inserted, is that Java8 interpolates before values are interpolated, but this is not important.

3.1.1 Expanding array Capacity

The resize() method is used to initialize an array or expand the array. After each expansion, the array capacity is doubled and data is migrated.

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) { // Expand the array
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // Double the array size
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // Double the threshold
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // It corresponds to the first put after initialization using new HashMap(int initialCapacity)
        newCap = oldThr;
    else {// corresponding to the first put after initialization with new HashMap()
        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;
 
    // Initialize the new array with the new array size
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; // If you're initializing an array, you're done here, return newTab
 
    if(oldTab ! =null) {
        // Start traversing the array for data migration.
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if((e = oldTab[j]) ! =null) {
                oldTab[j] = null;
                // If there is only one element in the array position, it is easy to simply migrate the element
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // If it is a red-black tree, we will not expand it
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // This is the case with the linked list,
                    // We need to split this list into two lists and put them in a new array, keeping the original order
                    // loHead and loTail correspond to one list, hiHead and hiTail correspond to another list
                    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;
                            elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
                    if(loTail ! =null) {
                        loTail.next = null;
                        // The first list
                        newTab[j] = loHead;
                    }
                    if(hiTail ! =null) {
                        hiTail.next = null;
                        // The new position of the second list is j + oldCap
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
Copy the code

3.2 GET process analysis

Get is really easy compared to put.

  1. Hash & (length-1) hash & (length-1)
  2. Determine if the element at that position in the array is exactly what we are looking for. If not, go to step 3
  3. Determine if the element type is TreeNode. If so, fetch the data using the red-black tree method. If not, go to step 4
  4. Iterate through the list until you find keys that are equal (== or equals)
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) {
        // Determine if the first node is needed
        if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        if((e = first.next) ! =null) {
            // Check if it is a red black tree
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
 
            // list traversal
            do {
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    return e;
            } while((e = e.next) ! =null); }}return null;
}
Copy the code

4. Java8 ConcurrentHashMap

The ConcurrentHashMap implemented in Java7 is quite complex to be honest, and Java8 has made major changes to the ConcurrentHashMap. You are advised to refer to the changes of The HashMap in Java8 compared to the HashMap in Java7. For ConcurrentHashMap, Java8 also introduces a red-black tree.

To tell the truth, Java8 ConcurrentHashMap source code is really not simple, the most difficult is expansion, data migration operation is not easy to understand.

Let’s first describe its structure with a schematic diagram:

The structure is basically the same as Java8’s HashMap, but it is a bit more complex in source code because it is thread-safe.

4.1 the initialization

// Do nothing in this constructor
public ConcurrentHashMap(a) {}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;
}
Copy the code

SizeCtl = (1.5 * initialCapacity + 1) and then take the nearest 2 to the NTH power. If initialCapacity is 10, sizeCtl is 16; if initialCapacity is 11, sizeCtl is 32.

The sizeCtl attribute is used in many different scenarios, but it will not confuse you if you follow the sizeCtl thread.

If you want to mess around, you can also look at another constructor that takes three arguments, which I won’t mention here. Most of the time, we’ll instantiate using the no-argument constructor, and we’ll do our source code analysis along the same lines.

4.2 PUT Process Analysis

Go through the code line by line carefully:

public V put(K key, V value) {
    return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    // Get the hash value
    int hash = spread(key.hashCode());
    // Record the length of the corresponding list
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // If the array is empty, initialize the array
        if (tab == null || (n = tab.length) == 0)
            // Initialize the array, more on that later
            tab = initTable();
 
        // find the array index corresponding to the hash value to get the first node f
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // If the position in the array is empty,
            // Add the new value with a CAS operation. The put operation is almost done, and can be pulled to the end
            // If the CAS fails, there is a concurrent operation, and the next loop is ready
            if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // Hash = 'MOVED' // Hash = 'MOVED
        else if ((fh = f.hash) == MOVED)
            // Help with data migration. This is easy to understand after reading the section on data migration
            tab = helpTransfer(tab, f);
 
        else { // This means that f is the head of this position and is not null
 
            V oldVal = null;
            // Get the monitor lock on the header at that position in the array
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // If the hash value of the header is greater than 0, it is a linked list
                        // Add the length of the list
                        binCount = 1;
                        // Iterate over the list
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // If the "equal" key is found, determine whether to override the value, and then break the value
                            if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
                                oldVal = e.val;
                                if(! onlyIfAbsent) e.val = value;break;
                            }
                            // At the end of the list, place the new value at the end of the list
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break; }}}else if (f instanceof TreeBin) { / / the red-black tree
                        Node<K,V> p;
                        binCount = 2;
                        // Call the red-black tree interpolation method to insert a new node
                        if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
                            oldVal = p.val;
                            if(! onlyIfAbsent) p.val = value; }}}}// binCount ! = 0 indicates that linked list operations are being performed
            if(binCount ! =0) {
                // Determine whether to convert the list to a red-black tree, the threshold is the same as for HashMap, also 8
                if (binCount >= TREEIFY_THRESHOLD)
                    // This method is slightly different from the HashMap method in that it does not necessarily perform a red-black tree conversion,
                    // If the current array length is less than 64, array expansion is selected instead of red-black tree conversion
                    // Add the following information to the file
                    treeifyBin(tab, i);
                if(oldVal ! =null)
                    return oldVal;
                break; }}}// 
    addCount(1L, binCount);
    return null;
}
Copy the code

The main process of PUT is finished, but there are at least a few problems left. The first one is initialization, the second one is capacity expansion, and the third one is data migration assistance, which will be covered in the following sections.

4.2.1 Initializing an Array: initTable

So this is a little bit simpler, just initialize an array of the right size, and then set it to sizeCtl.

Concurrency issues in the initialization method are controlled by performing a CAS operation on sizeCtl.

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // The credit for initialization was taken by another thread
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // Set sizeCtl to -1, indicating lock capture
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    // DEFAULT_CAPACITY The default initial capacity is 16
                    int n = (sc > 0)? sc : DEFAULT_CAPACITY;// Initialize the array with a length of 16 or the length provided at initialization
                    Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n];// Assign this array to table, which is volatile
                    table = tab = nt;
                    // sc = 12 if n is 16
                    // This is 0.75 * n
                    sc = n - (n >>> 2); }}finally {
                // set sizeCtl to sc and let's call it 12
                sizeCtl = sc;
            }
            break; }}return tab;
}
Copy the code

4.2.2 Converting linked lists to red-black trees: treeifyBin

As mentioned in the put source code analysis, treeifyBin does not necessarily perform red-black tree conversions, but may only perform array expansion. Let’s do the source code analysis.

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if(tab ! =null) {
        / / MIN_TREEIFY_CAPACITY for 64
        So, if the array size is less than 64, which is 32 or 16 or less, the array size will be expanded
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            // We'll look at this method in more detail later
            tryPresize(n << 1);
        // b is the header
        else if((b = tabAt(tab, index)) ! =null && b.hash >= 0) {
            / / lock
            synchronized (b) {
 
                if (tabAt(tab, index) == b) {
                    // Create a red-black tree by iterating through the list
                    TreeNode<K,V> hd = null, tl = null;
                    for(Node<K,V> e = b; e ! =null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val,
                                              null.null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // Set the red-black tree to the appropriate location in the array
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}
Copy the code

4.3 Capacity Expansion: tryPresize

If the source code for Java8 ConcurrentHashMap is not simple, then it is the expansion operations and migration operations.

To fully understand this method, we also need to look at the subsequent transfer method, which readers should know in advance.

The capacity here is also doubled, the capacity of the array is doubled.

// The method parameter size is already doubled when passed in
private final void tryPresize(int size) {
    // c: size 1.5 times, then add 1, then take the nearest 2 to the n power.
    int c = (size >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>>1) + 1);
    int sc;
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table; int n;
 
        // The if branch is basically the same as the code we used to initialize the array, so we can leave it alone
        if (tab == null || (n = tab.length) == 0) {
            n = (sc > c) ? sc : c;
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if (table == tab) {
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = nt; sc = n - (n >>>2); / / 0.75 * n}}finally{ sizeCtl = sc; }}}else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        else if (tab == table) {
            // I don't understand what rs really means, but it doesn't matter
            int rs = resizeStamp(n);
 
            if (sc < 0) {
                Node<K,V>[] nt;
                if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                // 2. Add 1 to sizeCtl with CAS and transfer
                // nextTab is not null
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            // set sizeCtl to (rs << RESIZE_STAMP_SHIFT) + 2)
            // What is the real meaning of this value? But what you can calculate is that it's going to be a big negative number
            // Transfer is called with the nextTab parameter null
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null); }}}Copy the code

The core of this method is the sizeCtl operation, first set it to a negative value, then transfer(TAB, NULL), then the next loop will add 1 to sizeCtl and transfer(TAB, nt), This may be followed by continuing with sizeCtl plus 1 and transferring (TAB, NT).

Therefore, the possible operation is to perform a transfer(TAB, NULL) + multiple transfer(TAB, NT), here how to end the loop need to read the transfer source code before it is clear.

4.3.1 Data Migration: Transfer

The following method, rather long, migrates elements from the original TAB array to the new nextTab array.

Although multiple calls to transfer in the tryPresize method don’t involve multithreading, the transfer method can be called elsewhere, typically, as we said before when we talked about put. Look up at put, Is there a place where helpTransfer is called? HelpTransfer will call Transfer.

This method supports multi-thread execution. When the peripheral calls this method, the nextTab parameter is guaranteed to be null for the first thread that initiates the data migration. When the peripheral calls this method, the nextTab parameter will not be null.

Before reading the source code, understand the mechanics of concurrent operations. The original array length is N, so we have n migration tasks. It is easiest for each thread to take charge of one small task at a time. After each task is completed, we can check whether there are other tasks that are not completed to help migration. Each thread is responsible for migrating one part at a time, for example, migrating 16 small tasks at a time. Therefore, we need a global scheduler to assign which threads to perform which tasks, which is what the property transferIndex does.

The first thread that initiates the data migration will point the transferIndex to the last position of the original array, then the backward stride task belongs to the first thread, then the forward stride task belongs to the new position, and the next stride task belongs to the second thread, and so on. Of course, the second thread here does not necessarily refer to the second thread, but could also be the same thread, the reader should understand. This is essentially breaking up a large migration task into task packages.

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
 
    // The stride is directly equal to n in single-core mode, (n>>>3)/NCPU in multi-core mode, and the minimum value is 16
    // Stride can be understood as "step length", there are n positions that need to be transferred,
    // Divide the n tasks into multiple task packages, and each task package has stride tasks
    if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
 
    // If nextTab is null, initialize it first
    NextTab is null when this method is called by the first thread that initiates the migration
    NextTab will not be null when this method is called later by the participating thread
    if (nextTab == null) {
        try {
            // Double the capacity
            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;
        }
        // nextTable is an attribute in ConcurrentHashMap
        nextTable = nextTab;
        // transferIndex is also an attribute of ConcurrentHashMap, which controls the location of the migration
        transferIndex = n;
    }
 
    int nextn = nextTab.length;
 
    // ForwardingNode translates to Node being migrated
    // This constructor will generate a Node with null key, value, and next. The key is that the hash is MOVED
    // After the node at position I is migrated,
    // Position I is set to this ForwardingNode, which tells other threads that position has already been handled
    // So it's kind of a sign.
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
 
 
    // Advance refers to having completed the migration of a location and being ready for the next location
    boolean advance = true;
    boolean finishing = false; // to ensure sweep before committing nextTab
 
    /* */ * */ * */ * */ * */ * */ * */
 
    // I is the position index, and bound is the boundary
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
 
        // The following while is really confusing
        // Advance is true to indicate that the next location can be migrated
        // I points to transferIndex, bound points to transferIndex-stride
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
 
            // Assign transferIndex to nextIndex
            // If transferIndex is less than or equal to 0, all positions in the original array are processed by the corresponding thread
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                // Look at the code in parentheses. NextBound is the boundary of the migration task, from back to front
                bound = nextBound;
                i = nextIndex - 1;
                advance = false; }}if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                // All migration operations have been completed
                nextTable = null;
                // Assign the new nextTab to the table property to complete the migration
                table = nextTab;
                // recalculate sizeCtl: n is the size of the original array, so the sizeCtl value will be 0.75 times the size of the new array
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
 
            // As we said before, sizeCtl will be set to (RS << RESIZE_STAMP_SHIFT) + 2 before migration
            // Then add 1 to the sizeCtl for each thread participating in the migration,
            SizeCtl = 1; // The CAS operation is used to subtract 1 from sizeCtl
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                // The task ends, and the method exits
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
 
                (sc-2) == resizeStamp(n) << stamp_shift,
                // That is, all the migration tasks are done and the if(finishing){} branch is up
                finishing = advance = true;
                i = n; // recheck before commit}}// If position I is empty and there are no nodes, then place the ForwardingNode "empty node" that was just initialized.
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        // The location is a ForwardingNode, indicating that the location has been migrated
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        else {
            // Lock the node at the location of the array and start processing the migration of the array
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    // If the hash of the header is greater than 0, it is a linked Node
                    if (fh >= 0) {
                        // This is similar to the ConcurrentHashMap migration in Java7,
                        // We need to split the list in two,
                        // Find lastRun in the original list, then lastRun and its subsequent nodes are migrated together
                        // The nodes before lastRun need to be cloned and divided into two linked lists
                        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;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        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);
                        }
                        // One of the lists is placed at position I of the new array
                        setTabAt(nextTab, i, ln);
                        // Put another list at position I +n of the new array
                        setTabAt(nextTab, i + n, hn);
                        // Set the position of the original array to FWD, indicating that the position has been processed,
                        // Other threads will not migrate once they see that the hash value at this location is MOVED
                        setTabAt(tab, i, fwd);
                        // Advance is set to true to indicate that the location has been migrated
                        advance = true;
                    }
                    else if (f instanceof TreeBin) {
                        // Red black tree migration
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for(Node<K,V> e = t.first; e ! =null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null.null);
                            if ((h & n) == 0) {
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    loTail.next = p;
                                loTail = p;
                                ++lc;
                            }
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                elsehiTail.next = p; hiTail = p; ++hc; }}// If the number of nodes is less than 8, then the red-black tree is converted back to the linked 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;
 
                        // place ln at position I of the new array
                        setTabAt(nextTab, i, ln);
                        // Place hn at position I +n of the new array
                        setTabAt(nextTab, i + n, hn);
                        // Set the position of the original array to FWD, indicating that the position has been processed,
                        // Other threads will not migrate once they see that the hash value at this location is MOVED
                        setTabAt(tab, i, fwd);
                        // Advance is set to true to indicate that the location has been migrated
                        advance = true;
                    }
                }
            }
        }
    }
}
Copy the code

In the final analysis, the transfer method does not realize all migration tasks. Each call of this method only realizes the migration of the first step of the transferIndex, and the rest needs to be controlled by the periphery.

At this point, go back and look at the tryPresize method a little more clearly.

4.4 GET Process analysis

The get method is always the simplest, and this is no exception:

  1. Calculate the hash value
  2. Locate (n – 1) &h based on the hash value
  3. Search according to the properties of the junction point at this position
    • If the location is NULL, then simply return NULL
    • If the node at that location is exactly what we want, we simply return the value of that node
    • If the hash value of this node is less than 0, it indicates expansion or a red-black tree. We will describe the find method later
    • If none of the above three items are met, it is a linked list and can be traversed
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) ! =null) {
        // Determine if the header is the desired node
        if ((eh = e.hash) == h) {
            if((ek = e.key) == key || (ek ! =null && key.equals(ek)))
                return e.val;
        }
        // If the hash of the header is less than 0, expansion is under way, or the location is a red-black tree
        else if (eh < 0)
            Forwardingnode. find(int h, Object k) and treebin. find(int h, Object k)
            return(p = e.find(h, key)) ! =null ? p.val : null;
 
        // Iterate over the list
        while((e = e.next) ! =null) {
            if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
                returne.val; }}return null;
}
Copy the code

Forwardingnode. find(int h, Object k) forwardingNode. find(int h, Object k) forwardingNode. find(int h, Object k)