Personal blog welcome to visit

Dunk is a search program on wechat. Follow our official account and get the source of the blog

The serial number	content
1	Java basic interview questions
2	The JVM interview questions
3	Java concurrent programming interview
4	Computer network knowledge summary
5	MySQL interview questions
6	Mybatis source code analysis + interview
7	Spring interview questions
8	For SpringMVC interview questions
9	SpringBoot interview questions
10	SpringCloud interview questions
11	Redis interview questions
12	Elasticsearch interview questions
13	Docker learning
14	The message queue
15	Continuously updated…

A HashMap (1.7)

Source code analysis

attribute

The table a hash table

transient Entry<K,V>[] table;
Copy the code

Number of elements in the current hash table

transient int size;
Copy the code

Number of changes to the HashMap

transient int modCount;
Copy the code

A constructor

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(a) {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}
Copy the code

Entry

static class Entry<K.V> implements Map.Entry<K.V
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    /** * Creates new entry. */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
Copy the code

Put method

public V put(K key, V value) {
    // If key is null, the operation is performed
    if (key == null)
        return putForNullKey(value);
    // Find the address of the inserted value (routing addressing)
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // Loop the single linked list of the current bucket level
    for(Entry<K,V> e = table[i]; e ! =null; e = e.next) {
        Object k;
        // Hash is equal and key is equal, find the same node
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            // Change the key value, return the original value
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // The same node as the inserted node was not found
    addEntry(hash, key, value, i);
    return null;
}
Copy the code

hash

final int hash(Object k) {
   	//hashSeed
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }
    //h = 0 0 ^ n = n
    h ^= k.hashCode();
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
Copy the code

putForNullKey

private V putForNullKey(V value) {
    //key == null fixed at 0
    // find the node whose key is null and change the value to return the original value
    for (Entry<K,V> e = table[0]; e ! =null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            returnoldValue; }}// Not found
    modCount++;
    addEntry(0.null, value, 0);
    return null;
}
Copy the code

indexFor

static int indexFor(int h, int length) {
    return h & (length-1);
}
Copy the code

addEntry

void addEntry(int hash, K key, V value, int bucketIndex) {
    // If the number of elements reaches the capacity expansion threshold and the bucket bit is not empty, expand the capacity
    if ((size >= threshold) && (null! = table[bucketIndex])) { resize(2 * table.length);
        hash = (null! = key) ? hash(key) :0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
Copy the code

createEntry

void createEntry(int hash, K key, V value, int bucketIndex) {
    //e Specifies the head node of the current bucket
    Entry<K,V> e = table[bucketIndex];
    // Set the successor node of the new node to e
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
Copy the code

The resize method

resize

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // If the original capacity is equal to the maximum capacity, the capacity expansion threshold is equal to the maximum number of operations
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // Create a new table with the capacity newCapacity
    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    // Set JVM environment variables -> change hash seeds -> change hash values
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the code

transfer

void transfer(Entry[] newTable, boolean rehash) {
    / / head interpolation
    int newCapacity = newTable.length;
    // Traverses the singly linked list of each bucket bit
    for (Entry<K,V> e : table) {
        while(null! = e) { Entry<K,V> next = e.next;// Usually false
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // reroute addressing
            inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

The get method

public V get(Object key) {
    //key is the air conditioner method getForNullKey
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
Copy the code

getForNullKey

private V getForNullKey(a) {
    // Search at bucket bit 0
    for (Entry<K,V> e = table[0]; e ! =null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
Copy the code

getEntry

final Entry<K,V> getEntry(Object key) {
    // Computes the hash value
    int hash = (key == null)?0 : hash(key);
    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

The remove method

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}
Copy the code

removeEntryForKey

final Entry<K,V> removeEntryForKey(Object key) {
    // Determine the bucket location
    int hash = (key == null)?0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;
    // Loop through the bucket bit
    while(e ! =null) {
        Entry<K,V> next = e.next;
        Object k;
        // Find the current deleted node
        if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
            modCount++;
            size--;
            // Delete the header of the list and the list
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            // Delete the record
            e.recordRemoval(this);
            return e;
        }
        / / was not found
        prev = e;
        e = next;
    }
    // Returns to delete the node
    return e;
}
Copy the code

The following code throw ConcurrentModificationException, reason: modCount traverse iterator when need to decide! = expectedModCount, and remove changes modCount

public static void main(String[] args) {
    Map<Integer,Object> map = new HashMap<>();
    map.put(1.new Object());
    map.put(2.new Object());
    for (int key : map.keySet()) {
        if (key == 2) { map.remove(key); }}}Copy the code

public final boolean hasNext(a) {
    returnnext ! =null;
}
final Entry<K,V> nextEntry(a) {
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
    Entry<K,V> e = next;
    if (e == null)
        throw new NoSuchElementException();
    if ((next = e.next) == null) {
        Entry[] t = table;
        while (index < t.length && (next = t[index++]) == null); } current = e;return e;
}
Copy the code

The mechanism of Fail – Fast We know Java. Util. HashMap is not thread safe, so if you have any other in the process of using the iterator thread modifies the map, then throw ConcurrentModificationException, This is known as the Fail-fast strategy. This strategy is implemented in the source code via the modCount field, which as the name implies is the number of changes. Any changes to the HashMap content will increase this value, which is then assigned to the expectedModCount of the iterator during initialization. During iteration, test whether modCount and expectedModCount are equal. If they are not equal, it indicates that other threads have modified the Map. Note that modCount is declared volatile to make changes visible between threads. In JDK7 and JDK8, this is no longer stated ！！！！！

Note that this exception does not always indicate that the object has been modified by another thread at the same time. If a single thread makes a series of method calls that violate the convention of the object, the object may throw this exception. For example, if a thread modifies the collection while iterating over it using an iterator with fail-fast, the iterator will throw this exception.

ConcurrentHashMap (1.7)

The internal structure

ConcurrentHashMap uses a Segment structure to improve its concurrency. A Segment is actually a Hashtable structure, which maintains a linked list array

Source code analysis

attribute

DEFAULT_CONCURRENCY_LEVEL Indicates the number of segments

private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
Copy the code

DEFAULT_CAPACITY Number of Hashentries

private static final int DEFAULT_CAPACITY = 16;
Copy the code

MIN_SEGMENT_TABLE_CAPACITY Minimum number of Hashentries in each segment

static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
Copy the code

MAX_SCAN_RETRIES obtains the number of spins of the lock

static final int MAX_SCAN_RETRIES =
            Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
Copy the code

A constructor

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;
    InitialCapacity Indicates the number of hashentries
    //sssize indicates the number of segments
    //sshift indicates the number of left shifts
    // The lowest power of 2 greater than concurrencyLevel
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    // The number of digits to be right-shifted for the hash value
    this.segmentShift = 32 - sshift;
    // calculate segment subscript
    this.segmentMask = ssize - 1;
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // Number of hashentries in each segment
    int c = initialCapacity / ssize;
    if (c * ssize < initialCapacity)
        ++c;
    // The number of hashentries (greater than or equal to c to the power of 2)
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    while (cap < c)
        cap <<= 1;
    // create segments and segments[0]
    Segment<K,V> s0 =
        new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                         (HashEntry<K,V>[])new HashEntry[cap]);
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}
Copy the code

segment

Once the segment length is specified, it does not change

Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
    this.loadFactor = lf;
    this.threshold = threshold;
    this.table = tab;
}
Copy the code

unsafe

UnSafe operates on array elements

static {
    int ss, ts;
    try {
        UNSAFE = sun.misc.Unsafe.getUnsafe();
        Class tc = HashEntry[].class;
        Class sc = Segment[].class;
        TBASE = UNSAFE.arrayBaseOffset(tc);
        SBASE = UNSAFE.arrayBaseOffset(sc);
        ts = UNSAFE.arrayIndexScale(tc);
        ss = UNSAFE.arrayIndexScale(sc);
        HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
            ConcurrentHashMap.class.getDeclaredField("hashSeed"));
    } catch (Exception e) {
        throw new Error(e);
    }
    if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
        throw new Error("data type scale not a power of two");
    SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
    TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
}
Copy the code

1.unsafe = Util.getUnsafe(); // Initialize unsafe

2.final int base = unsafe.arrayBaseOffset(long[].class); // Get the array header position

3.final int scale = unsafe.(long[].class); // Get a single array size

4.valueOffset = base + (scale * N); // Get the offset of the element

So you can manipulate the elements of the array as much as you want

Put method

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    //segment.length = 16
    //segmentMask = 15 1111
    //hash >>> segmentShift takes the high four digits of the hash value
    int j = (hash >>> segmentShift) & segmentMask;
    // The internal search key uses the lower four digits of the hash
    // Check whether the current segment is empty before putting it. If it is empty, create the segment first
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         //ss = UNSAFE.arrayIndexScale(sc); // The number of elements
         //SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
         //ss = 32 
         //31 - Integer.numberOfLeadingZeros(ss) = 31 - 26 = 5
         // j << SSHIFT == j << 5 = j * 32
         // j << SSHIFT) + SBASE = j * 32 + SBASE
         (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}
Copy the code

NumberOfLeadingZeros returns the number of zeros (leading zeros) before the first left digit of the I binary.

public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16= =0) { n += 16; i <<= 16; }
    if (i >>> 24= =0) { n +=  8; i <<=  8; }
    if (i >>> 28= =0) { n +=  4; i <<=  4; }
    if (i >>> 30= =0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}
Copy the code

EnsureSegment Creates segments and ensures thread-safe creation without modification by other threads

Create a template from segment[0]

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;
    // Prevent other threads from completing the segment
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        // Check again
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
            == null) { // recheck
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // Seg is assigned successfully.
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break; }}}return seg;
}
Copy the code

Segment put method

Put is equivalent to put in hashMap

Different from a HashMap put:

ReentrantLock is added to the entire process
Instead of pointing directly to node, table[index] uses the Unsafe putOrderedObject thread-safe reference

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    //node Specifies the node to be inserted
    // Use ReentrantLock to keep threads safe
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        // Route address (find bucket)
        int index = (tab.length - 1) & hash;
        // The first node of the current bucket
        HashEntry<K,V> first = entryAt(tab, index);
        // Loop the single linked list of the current bucket level
        for (HashEntry<K,V> e = first;;) {
            if(e ! =null) {
                K k;
               // If a node with the same key value is found, overwrite it directly
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    //onlyIfAbsent = false Indicates that the vlaue value can be changed if the same key exists
                    if(! onlyIfAbsent) { e.value = value; ++modCount; }break;
                }
                e = e.next;
            }
            else {// Not found
                // The current node is not empty
                if(node ! =null)
                    node.setNext(first);
                else
                    // Create a new hashEntry for null
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                // If the value is greater than the capacity expansion threshold, rehash the value
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                // Otherwise put the new hashEntry list into the current segment array
                else
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break; }}}finally {
        unlock();
    }
    return oldValue;
}
Copy the code

EntryAt retrieves the ith hashEntry object in the current segment (directly from memory)

static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
    return (tab == null)?null :
        (HashEntry<K,V>) UNSAFE.getObjectVolatile
        (tab, ((long)i << TSHIFT) + TBASE);
}
Copy the code

SetEntryAt (perform assignment directly in memory)

static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
                                   HashEntry<K,V> e) {
    UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
}
Copy the code

scanAndLockForPut

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
    // Try to get the lock
    while(! tryLock()) { HashEntry<K,V> f;// to recheck first below
        if (retries < 0) {// The current linked list is iterated on each attempt to acquire the lock
            if (e == null) {
                if (node == null) // speculatively create node
                    node = new HashEntry<K,V>(hash, key, value, null);
                retries = 0;
            }
            else if (key.equals(e.key))
                retries = 0;
            else
                e = e.next;
        }
        else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        }
        //retries is even
        // Retrieve the head node of the current hashEntry
        // If there are changes, try again
        else if ((retries & 1) = =0 &&
                 (f = entryForHash(this, hash)) ! = first) { e = first = f;// re-traverse if entry changed
            retries = -1; }}return node;
}
Copy the code

EntryForHash retrieves the head node of the current hashEntry

static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
    HashEntry<K,V>[] tab;
    return (seg == null || (tab = seg.table) == null)?null :
        (HashEntry<K,V>) UNSAFE.getObjectVolatile
        (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
}
Copy the code

To sum up:

What operations were performed when the segment was put to attempt to acquire the lock

Retries less than 0: Spins through all the linked lists of the current hashEntry. If a node with the same key is found until retries sets the value to 0, a new node is created
Retries increments until (64 if the CPU has more than one) the spin ends at 1 and the lock fails to be acquired
If retries is even, the current HashEntry is obtained and the HashEntry is changed or not. If retries is -1, the HashEntry continues to spin

rehash

private void rehash(HashEntry<K,V> node) {
    // Calculates the parameters of the new hashEntry
    HashEntry<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    int newCapacity = oldCapacity << 1;
    threshold = (int)(newCapacity * loadFactor);
    HashEntry<K,V>[] newTable =
        (HashEntry<K,V>[]) new HashEntry[newCapacity];
    int sizeMask = newCapacity - 1;
    // Loop through old hashEntry
    for (int i = 0; i < oldCapacity ; i++) {
        HashEntry<K,V> e = oldTable[i];
        if(e ! =null) {
            HashEntry<K,V> next = e.next;
            int idx = e.hash & sizeMask;
            // The current list has only one node
            if (next == null)   // Single node on list
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                // Fragment transfer
                HashEntry<K,V> lastRun = e;
                int lastIdx = idx;
                for(HashEntry<K,V> last = next; last ! =null;
                     last = last.next) {
                    int k = last.hash & sizeMask;
                    if(k ! = lastIdx) { lastIdx = k; lastRun = last; } } newTable[lastIdx] = lastRun;// Clone remaining nodes
                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); }}}}int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}
Copy the code

The remove method

remove

public V remove(Object key) {
    int hash = hash(key);
    Segment<K,V> s = segmentForHash(hash);
    return s == null ? null : s.remove(key, hash, null);
}
Copy the code

remove

final V remove(Object key, int hash, Object value) {
    if(! tryLock()) scanAndLock(key, hash); V oldValue =null;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> e = entryAt(tab, index);
        HashEntry<K,V> pred = null;
        while(e ! =null) {
            K k;
            HashEntry<K,V> next = e.next;
            if ((k = e.key) == key ||
                (e.hash == hash && key.equals(k))) {
                V v = e.value;
                if (value == null || value == v || value.equals(v)) {
                    if (pred == null)
                        setEntryAt(tab, index, next);
                    else
                        pred.setNext(next);
                    ++modCount;
                    --count;
                    oldValue = v;
                }
                break; } pred = e; e = next; }}finally {
        unlock();
    }
    return oldValue;
Copy the code

The size method

public int size(a) {
    // Try a few times to get accurate count. On failure due to
    // continuous async changes in table, resort to locking.
    final Segment<K,V>[] segments = this.segments;
    int size;
    boolean overflow; // true if size overflows 32 bits
    long sum;         // sum of modCounts
    long last = 0L;   // previous sum
    int retries = -1; // first iteration isn't retry
    try {
        for (;;) {
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    ensureSegment(j).lock(); // force creation
            }
            sum = 0L;
            size = 0;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if(seg ! =null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    if (c < 0 || (size += c) < 0)
                        overflow = true; }}if (sum == last)
                break; last = sum; }}finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j) segmentAt(segments, j).unlock(); }}return overflow ? Integer.MAX_VALUE : size;
}
Copy the code

ConcurrentHashMap (1.8)

The internal structure

Source code analysis

attribute

SizeCtl Capacity expansion threshold

private transient volatile int sizeCtl;
Copy the code

BASECOUNT Number of elements in the hash table

private static final long BASECOUNT;
Copy the code

counterCells

private transient volatile CounterCell[] counterCells;
Copy the code

A 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;
}

public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    this.sizeCtl = DEFAULT_CAPACITY;
    putAll(m);
}
Copy the code

TableSizeFor Returns a number greater than the current cap. The number must be a power of 2

static final int tableSizeFor(int cap) {
    int n = cap - 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 code

Set any binary number 0001 1101 1100 => 0001 1111 1111 Set all the digits after the first 1 of any binary number to 1

Put method

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());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            // Initialize the table
            tab = initTable();
        // If bucket bit is empty
        // Spin a Node into the current bucket
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //MOVED = -1;
        // If the hash value of the current bucket head node is -1, the current hashMap is being expanded by another thread
        else if ((fh = f.hash) == MOVED)
            // Help expand capacity
            tab = helpTransfer(tab, f);
        else {
            // The bucket head node exists
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
                                oldVal = e.val;
                                if(! onlyIfAbsent) e.val = value;break;
                            }
                            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) {
                        Node<K,V> p;
                        binCount = 2;
                        if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
                            oldVal = p.val;
                            if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! =0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if(oldVal ! =null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}
Copy the code

initTable

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            // Another thread successfully creates the table directly returns
            Thread.yield(); // lost initialization race; just spin
        // Change sc to -1, spin wait if failed, create Node if successful and return
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt;/ / 0.75 n
                    sc = n - (n >>> 2); }}finally {
                sizeCtl = sc;
            }
            break; }}return tab;
}
Copy the code

Here the red-black tree is encapsulated as a TreeBin object

Why do you do that?

During the insert operation, the tree rotates to maintain balance, causing the root node, the head node at the bucket level, to change the lock. To prevent the balance operation from changing the lock, a TreeBin object is encapsulated

treeifyBin

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if(tab ! =null) {
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        else if((b = tabAt(tab, index)) ! =null && b.hash >= 0) {
            synchronized (b) {
                if (tabAt(tab, index) == b) {
                    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;
                    }
                    setTabAt(tab, index, newTreeBin<K,V>(hd)); }}}}Copy the code

TreeNode

TreeBin(TreeNode<K,V> b) {
    super(TREEBIN, null.null.null);
    this.first = b;
    TreeNode<K,V> r = null;
    for(TreeNode<K,V> x = b, next; x ! =null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (r == null) {
            x.parent = null;
            x.red = false;
            r = x;
        }
        else {
            K k = x.key;
            inth = x.hash; Class<? > kc =null;
            for (TreeNode<K,V> p = r;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                    TreeNode<K,V> xp = p;
                if ((p = (dir <= 0)? p.left : p.right) ==null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    r = balanceInsertion(r, x);
                    break; }}}}this.root = r;
    assert checkInvariants(root);
}
Copy the code

AddCount method

// After calling putVal, we added a check parameter for general purpose, which specifies whether a capacity expansion is possible
//check >= 0 is a possible expansion case, such as the call in putVal
private final void addCount(long x, int check){... .if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        // Check whether the number of elements in the current set reaches the sizeCtl threshold. If sizeCtl is negative during the expansion, it will still be valid. At the same time, the array must be non-empty and the array length cannot be larger than the maximum allowed array length
        // The while loop is used to determine whether the threshold has been reached to perform the expansion operation. Another function of the while loop is that after a thread completes its migration task, if the set is still expanding, it will continue to loop and continue to join the expansion force to apply for the subsequent migration task
        while (s >= (long)(sc = sizeCtl) && (tab = table) ! =null && (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            // sc < 0 indicates that the set is being expanded
            if (sc < 0) {
                // Determine whether the expansion is complete or whether the number of concurrent expansion threads has reached the maximum. If so, terminate the while loop
                if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)
                    break;
                // The expansion is not complete and the expansion thread is allowed to join
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            // If the collection is not already in the expanded state, enter the expanded method and initialize the nextTab array first, that is, the new array
            //(rs << RESIZE_STAMP_SHIFT) + 2 The specific value set by the first expansion thread. Later expansion will determine whether it is the last thread according to this value
            else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null); s = sumCount(); }}}Copy the code

helpTransfer

// When other threads insert, modify, delete, merge, compute, etc., the ForwardingNode node will call this help method (ForwardingNode is described later).
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if(tab ! =null && (f instanceofForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! =null) {
        int rs = resizeStamp(tab.length);
        // The while loop here is a shorter version of the addCount method above
        while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
            if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break; }}return nextTab;
    }
    return table;
}
Copy the code

tryPresize

//putAll calls this method when a list length of 8 or more nodes is inserted, but the array length is less than 64
private final void tryPresize(int size) {
    int c = (size >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>>1) + 1);
    int sc;
    // If the sizeCtl < 0 condition is not met, there are other threads in the process of expanding, so there is no need to expand. End the method
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table; int n;
        // Initialize the array if it is initialized. This option is mainly provided for the bulk insert method putAll
        if (tab == null || (n = tab.length) == 0) {
            n = (sc > c) ? sc : c;
            // Set sizeCtl to -1 to ensure single-thread initialization
            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); }}finally {
                    // After initialization, sizeCtl records the load capacity of the current set, that is, the threshold that triggers the set expansionsizeCtl = sc; }}}else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        // When the list length reaches 8 or more, but the array length is less than 64, the expansion will go to the else if branch below
        else if (tab == table) {
            int rs = resizeStamp(n);
            // This is basically the same as the inside of the while loop of the addCount method
            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;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null); }}}Copy the code

fullAddCount

fullAddCount

This method is a bit complicated, but the purpose is simple: the modification must be successful. Spin can be divided into three major branches:

If the array of counterCells is not empty, the hash map corresponds to the grid. If the conflict escalation triggers expansion after repeated failures, the hash map spins again.
If the counterCells array is empty, it is initialized.
Cas modifs baseCount if it has no access to initialization. Two variables need to be explained:
If the cas fails to put the corresponding grid in place, it will set it to “true”. If the hash loop fails to put it again, it will set it to “double”. Collide [] If the number of cores in the collide array is set to collide with the number of cores in the collide array (collide=false), it will not collide with the number of cores in the collide array (collide=false).
CellsBusy, equivalent to a spin lock, cellsBusy=1 to acquire the lock, cellsBusy=0 to release the lock. CellsBusy is used when expanding countercells in branches, adding new cells, or initializing CounterCell arrays.

private final void fullAddCount(long x, boolean wasUncontended) {
    int h; // h is similar to hash
    if ((h = ThreadLocalRandom.getProbe()) == 0) {
        // h = 0 initializes the rehash, and wasUncontended=true means no contention
        ThreadLocalRandom.localInit();      // force initialization
        h = ThreadLocalRandom.getProbe();
        wasUncontended = true;
    }
    // false: no collision occurred
    // True means to upgrade to severe competition level, which may trigger expansion
    boolean collide = false;                // True if last slot nonempty
    for (;;) {
        CounterCell[] as; CounterCell a; int n; long v;
        if((as = counterCells) ! =null && (n = as.length) > 0) {
            // 1. As is not equal to null and has CounterCell
            if ((a = as[(n - 1) & h]) == null) {
                If CounterCell=null, create a new one
                if (cellsBusy == 0) {            // Try to attach new Cell
                    CounterCell r = new CounterCell(x); // Optimistic create
                    if (cellsBusy == 0 &&
                        U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
                        // cellsBusy is equivalent to an optimistic lock, indicating that no other threads are competing
                        boolean created = false;
                        try {               // Recheck under lock
                            CounterCell[] rs; int m, j;
                            if((rs = counterCells) ! =null &&
                                (m = rs.length) > 0 &&
                                rs[j = (m - 1) & h] == null) {
                                // if j is still empty, r is assigned to j
                                rs[j] = r;
                                // The Settings were successfully created
                                created = true; }}finally {
                            / / releases the lock
                            cellsBusy = 0;
                        }
                        if (created)
                            // End the loop
                            break;
                        continue;           // Slot is now non-empty
                    }
                }
                collide = false;
            }
            // (2) The mapping position of CounterCell is not empty, hash conflict occurs
            else if(! wasUncontended)// CAS already known to fail
                // (2.1) wasUncontended=false
                WasUncontended =true
                wasUncontended = true;      // Continue after rehash
            WasUncontended =true; if there is no contest, try cas to add value+x to the CounterCell
            else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
                // Exit after successful modification
                break;
            // (2.3) The modification failed
            else if(counterCells ! = as || n >= NCPU)// (2.3.1) The ADDRESS of the AS is changed (other threads have expanded) or n indicates that the length of the AS array is greater than or equal to the number of CPU cores
                // (no more cores for other threads), no conflict escalation, go (5) hash again, loop again try
                collide = false;            // At max size or stale
            // （2.3.2）counterCells = as && n < NCPU
            else if(! collide)Collide = "keep me oncollide", keep me oncollide = "keep me oncollide", keep me oncollide
                collide = true;
            Keep me in mind: Keep me in mind: keep me in mind: keep me in mind: keep me in mind: keep me in mind: keep me in mind
            else if (cellsBusy == 0 &&
                     U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
                try {
                    if (counterCells == as) {// Expand table unless stale
                        // counterCells is expanded twice
                        // The trigger mechanism of this capacity expansion is that the counterCell mapped to is not null, and the cas operation +x failed several times.
                        // If the current counterCells address is not changed and the array length is smaller than NCPU (number of CPU cores), double expansion is triggered
                        CounterCell[] rs = new CounterCell[n << 1];
                        for (int i = 0; i < n; ++i) rs[i] = as[i]; counterCells = rs; }}finally {
                    cellsBusy = 0;
                }
                collide = false;
                continue;                   // Retry with expanded table
            }
            // (5) Generate a pseudo-random number and assign it to h for the next loop judgment
            / / to hash
            h = ThreadLocalRandom.advanceProbe(h);
        }
        // 2. As is null or as is null
        else if (cellsBusy == 0 && counterCells == as &&
                 U.compareAndSwapInt(this, CELLSBUSY, 0.1)) {
            boolean init = false;
            try {                           // Initialize table
                // Check counterCells == AS multiple times, not preventing AS change
                if (counterCells == as) {
                    // Initializes the CounterCell array with an initial capacity of 2
                    CounterCell[] rs = new CounterCell[2];
                    rs[h & 1] = new CounterCell(x);
                    counterCells = rs;
                    init = true; }}finally {
                cellsBusy = 0;
            }
            if (init)
                break;
        }
        BaseCount + x: baseCount + x: baseCount + x: baseCount + x: baseCount + x: baseCount + x: baseCount + x
        else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
            break;                          // Fall back on using base}}Copy the code

conclusion

After the addCount method is called to increase the count of elements in the collection, the expansion will be triggered when the number of elements in the current collection reaches the expansion threshold.
When other threads insert, modify, delete, merge, or compute into the collection during capacity expansion, the ForwardingNode node triggers capacity expansion.
PutAll inserts nodes in batches or if the linked list length reaches 8 or more but the array length is less than 64, capacity expansion is triggered.

Note: A bucket with 8 or more lists and an array length less than 64 will only trigger expansion and will not turn the list into a red-black tree.

capacity

The source code

// Call the expansion method:
. / / Java. Util. Concurrent ConcurrentHashMap# addCount to insert new data collection update capacity count after found reach capacity threshold and trigger the expansion
. / / Java. Util. Concurrent ConcurrentHashMap# helpTransfer expansion condition other threads to insert, modify, delete, merge the collection and compute operation triggered when encountered ForwardingNode node capacity
. / / Java. Util. Concurrent ConcurrentHashMap# tryPresize putAll bulk insert or inserted into the list length after found to 8 or more, but the array length 64 triggered when the expansion
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // Count the number of buckets processed by each thread. The number of buckets processed by each thread is the same. If the CPU is single-core, use one thread to process all buckets
    // Each thread processes at least 16 buckets. If the result is less than 16, each thread processes 16 buckets
    if ((stride = (NCPU > 1)? (n >>>3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // Initialize the new array (twice the size of the original array)
        try {
            @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;
        }
        nextTable = nextTab;
        // Set the transferIndex to the rightmost bucket with the largest index
        transferIndex = n;
    }
    int nextn = nextTab.length;
    // Create a placeholder object whose hash value is -1. If the placeholder object exists, it indicates that the collection is being expanded. The key, value, and next attributes are null
    // This placeholder object has two main uses:
    // 1. Placeholder function, used to indicate that the bucket at the location of the array has been migrated and is in the state of expansion.
    // 2. As a forwarding function, if a query operation is encountered during capacity expansion, the forwarding node will forward the query operation to the new array without blocking the query operation.
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    // This flag controls whether to continue processing the next bucket. If it is true, the current bucket is processed and data of the next bucket can be migrated
    boolean advance = true;
    // This flag is used to control when capacity expansion ends. Another use of this flag is that the last capacity expansion thread is responsible for rechecking the array to see if there are any missing buckets
    boolean finishing = false; // to ensure sweep before committing nextTab
    // This loop is used to process a task with the length of the stride. I is assigned the largest subscript in the stride, and bound is assigned the smallest subscript in the stride
    // Continuously decrease the value of "I" in a loop and migrate the data above the bucket from right to left until "I" is less than "bound"
    // After this task is completed, the while loop of the outer addCount, helpTransfer, and tryPresize methods will continue to retrieve other tasks
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            // Decrement bound by one after each hash bucket
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                //transferIndex <= 0 indicates that the hash bucket of the array has been allocated by the thread and there is no hash bucket to be allocated. Set I to -1 and the following code will exit the current line expansion operation based on this value
                i = -1;
                advance = false;
            }
            // Only the first time you enter the for loop will you enter the check. Set the values of bound and I
            else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false; }}if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            // After the expansion is complete, set nextTable to null to indicate that the expansion is complete, set table to the new array, and set sizeCtl to the expansion threshold
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            // The sizeCtl value is updated every time a thread is ready for capacity expansion
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                //(sc - 2) ! = resizeStamp(n) << RESIZE_STAMP_SHIFT is set up, indicating that this thread is not the last thread in the expansion army, and directly return to the upper while loop
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                //(SC-2) == resizeStamp(n) << RESIZE_STAMP_SHIFT indicates that this thread is the last one to expand capacity
                // We can use this to determine whether it is the last thread, because the first expansion thread does the following:
                // U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
                // Set I = n; In order to recheck the array, in case there are any missing buckets that did not migrate successfully
                finishing = advance = true;
                i = n; // recheck before commit}}else if ((f = tabAt(tab, i)) == null)
            // A placeholder object is placed directly in the space above the array to forward the query operation and identify the current expansion state
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            // The array has a hash value of MOVED (-1), indicating that the location has been MOVED by another thread. Set advance to true to move on to the next bucket
            advance = true; // already processed
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    // This node is a linked list structure
                    if (fh >= 0) {
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        // Run through the list to find the lastRun node
                        for(Node<K,V> p = f.next; p ! =null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        // lastRun is set to the last part of the ln or HN chain according to the high identifier (0 or 1) of the lastRun node
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        // Use the high and low list to migrate, and use the header method to join the list
                        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);
                        }
                        // The setTabAt method calls the putObjectVolatile method of the Unsafe class
                        // putObjectVolatile updates data directly back to main memory and invalidates variables in other threads' working memory
                        // Use volatile to set the ln chain to the subscript I of the new array
                        setTabAt(nextTab, i, ln);
                        // Use volatile to set the HN chain to the new array with subscript I + n(n is the original array length)
                        setTabAt(nextTab, i + n, hn);
                        // After the migration is complete, use volatile to set the placeholder object to the Hash bucket. The placeholder object is used to indicate that the Hash bucket has been processed and that query requests are forwarded
                        setTabAt(tab, i, fwd);
                        // Advance is set to true to indicate that the current hash bucket has been processed and the next hash bucket can be processed
                        advance = true;
                    }
                    // This node is a red-black tree structure
                    else if (f instanceof TreeBin) {
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        //lo is the low level list header, loTail is the low level list tail, hi and hiTail are the high level list header and tail
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        // Also use high and low lists for migration
                        // Use the for loop to traverse the entire red-black tree as a list, and use the tail interpolation method to join the LN and HN lists
                        for(Node<K,V> e = t.first; e ! =null; e = e.next) {
                            int h = e.hash;
                            // Create a list of TreeNode nodes
                            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 middle list needs to be converted to a red-black tree:
                        // If the TreeNode list meets the criteria, turn it into a red black tree and add it to the new array
                        //2. If the TreeNode does not meet the criteria, convert the TreeNode to a normal Node, and set the normal list to a new array
                        //(hc ! = 0)? New TreeBin
      
       (lo) : t The intent of this line is that if the original red-black tree is not split in two, it remains a red-black tree after migration and can be used directly with the original TreeBin object
      ,v>ln = (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;
                        // The setTabAt method calls the putObjectVolatile method of the Unsafe class
                        // putObjectVolatile updates data directly back to main memory and invalidates variables in other threads' working memory
                        // Use volatile to set the ln chain to the subscript I of the new array
                        setTabAt(nextTab, i, ln);
                        // Use volatile to set the HN chain to the new array with subscript I + n(n is the original array length)
                        setTabAt(nextTab, i + n, hn);
                        // After the migration is complete, use volatile to set the placeholder object to the Hash bucket. The placeholder object is used to indicate that the Hash bucket has been processed and that query requests are forwarded
                        setTabAt(tab, i, fwd);
                        // Advance is set to true to indicate that the current hash bucket has been processed and the next hash bucket can be processed
                        advance = true;
                    }
                }
            }
        }
    }
}
Copy the code

The illustration

Specifies the relationship between the number of CPU cores and the number of Hash buckets allocated by migration tasks

Task assignment and migration of a single thread

How do multithreading assign tasks?

We introduced a ForwardingNode class that changes sizeCtl when a thread initiates a capacity expansion, with the following implications:

SizeCtl: The default value is 0. It is used to control table initialization and capacity expansion operations. Specific applications will be described later. -1 Indicates that the table is being initialized. -n Indicates that N-1 threads are expanding the table. Other conditions: 1. 2. If the table is initialized, it indicates the capacity of the table. The default capacity is 0.75 times the size of the tableCopy the code

If the value exceeds the threshold, the capacity should be expanded. Firstly, the number of times to be traversed is obtained according to the operation, and then the element f at position I is obtained using tabAt method. Then, a forwardNode instance FWD is initialized, and if f == null, FWD is added to position I in table. Otherwise, migrate the data in the specified task range from the current old table array to the new array using the header method, and assign FWD to the original position of the old table. The replication is complete until all nodes are traversed, table is pointed to nextTable, and sizeCtl is updated to 0.75 times the size of the new array. During this period, if other threads have read or write operations, they will determine whether the head node is a forwardNode node. If so, they will help expand the capacity

How are normal linked lists migrated?

What are lastRun nodes?

How do red-black trees migrate?

How are access requests handled during and after a Hash bucket migration?

How do I perform read and write operations during capacity expansion

For the GET read operation, if the current node has data and the migration is not complete, the read operation does not affect the data. If the current list has been migrated, the head node is set to the FWD node, and the GET thread helps expand the list.
For put/remove writes, if the current list has been migrated, the head node will be set to FWD node, and the writer thread will help expand the list. If expansion is not completed, the head node of the current list will be locked, so the writer thread will be blocked until the expansion is complete.

Operation after multithreaded migration task is completed

Weak consistency for size and iterators

Volatile array references are strongly visible, but their elements are not, so size by sumCount is inaccurate.
Iteritor’s iterators, in the same way, do not accurately reflect the latest reality

Extension problem

1. Why is the size of a HashMap smaller than the array length?

A: HashMap is designed to compute the index from the hash value for the fastest access. If the capacity is greater than a lot of words, plus an array under the condition of hash algorithm is not very good list too long is easy to happen, although there is a red and black tree, but still not as good as direct positioning elements to an array position directly obtained faster, so ideally array of each position in an element, this location is the fastest, The reason why the set capacity is smaller than the array length is to try to disperse the distribution of elements, which is equivalent to extending the distribution range and minimizing the probability of clustering together, so as to improve the speed of access. At the same time, as long as the load factor is less than 1, there is no case that the capacity is equal to the array length.

2. What happens when data is inserted into hash buckets that are not migrated during capacity expansion?

A: It can be inserted as long as the insertion location has not been migrated to. When migrating to the insertion location, the migration will be blocked until the insertion operation is complete.

3. What happens when the Hash bucket being migrated encounters a GET operation?

A: The HN and LN chains formed during the expansion process are similar to copied references, that is to say, ln and HN chains are copied instead of the original list being migrated, so the original list on the Hash bucket is not affected. Therefore, the linked list on the hash bucket of the original array can be accessed normally from the beginning to the end of the migration. After the migration, FWD is placed, and subsequent access requests are directly forwarded to the expanded array.

4. If lastRun nodes happen to be on a list with all high or all low values, will there be an infinite loop?

An array length up to 64 results in continuous expansion, but after 64 or more it is converted to a red-black tree, so it does not loop forever. LastRun does not mean that the last node has a different runBit from the first node. LastRun means that the last node has a different runBit from the previous node. Notice that the runBit changes during the traversal comparison. If the h of the current node is different from that of the previous runbit, assign lastRun to the current node and runbit to the hash of the current node, so that the last found lastRun can split a list into two, one before lastRun and one after lastRun. LastRun will have the same hash as lastRun, so just copy lastRun into the new array, and lastRun will pass by. LastRun does not necessarily have the same hash value, so it needs to be copied to the new array one by one.
In 1.8, optimization was carried out to divide a linked list into two high and low linked lists on the basis of finding lastRun, so that only two linked lists need to be copied when replication migration. And why not looking for hi-lo, java1.7 here java1.7 is involved in solving the hash conflict, a new node is adopted for the first interpolation to replicate migration is the head of the interpolation, such a list to reverse migration, the new array is change the position of the placeholder nodes, but I think java1.7 force for high and low is also possible.

5. After expansion, the LN and HN chains are directly placed on the positions of I and N + I of the new array respectively without hash modulo operation, so how can we ensure that the position of the hash bucket can be correctly calculated using H & (n-1) in this way?

A: If fh&n-1 = I, the hash method after expansion should be fh&2n-1. Since n is a power of 2, if n=16, n-1 is 1111(binary), and 2n-1 is 11111 (binary). The difference between fh&2n-1 and fh&n-1 is that the extra 1 => fh&(10000). And 10,000 is n. So if the fifth bit of FH is not 1, fh&n = 0 => fh&2n-1 == fh&n-1 = I. If the fifth digit is 1. Fh&n = n => Fh&2n-1 = I +n.

We all know that in concurrent cases, the data in each thread may not be up to date, so why don’t get methods need to be locked?

A: Get does not need to be locked at all because the Node member val is volatile.

7. Is the operation of inserting nodes into the array of ConcurrentHashMap atomic? Why CAS is used?

A: To be resolved.

8. Why do I need to check again after capacity expansion?

A: In order to avoid missing hash buckets, as to why they are missing hash buckets.

ConcurrentHashMap1.7 and 1.8

The mark	JDK1.7	JDK1.8
The overall structure	Segment + HashEntry + CAS + ReentrantLock + Unsafe	synchronized + CAS + volatile + Node + TreeNode + ForwardNode + Unsafe + TreeBin
The object of the lock	The granularity of Segment locks is large	Node (head Node of bucket) locks have small granularity
put	The thread that does not acquire the lock finds the location of the bucket in advance, and spins up to 64 times (if the number of CPU cores is greater than 1, otherwise spins once) to acquire the lock. If the number of CPU cores exceeds 1, the lock will be suspended	Similar to HashMap, the bucket can be directly located and judged after getting the first node. 1. If it is empty, CAS is inserted. 2. If the value is -1, the capacity is being expanded. 3, else lock put (like 1.7)
get	You need to use Unsafe	Because value is declared volatile, the changes are visible, and therefore locks are not required
resize	(rehash) If the HashEntry array in the segment exceeds the threshold for expansion, only the HashEntry of the segment will be expanded.	In 1.8, HashMap expansion is performed by header insertion (to avoid infinite loops), ConcurrentHashmap expansion is performed by header insertion (to avoid infinite loops), ConcurrentHashmap expansion is performed by header insertion (to insert high and low linked lists), and ConcurrentHashmap migration is also performed from the tail. This allows another thread to determine if the bucket has already been processed by another thread.
size	If the Segment is not the same, return the result. If the Segment is not the same, lock all the segments and sum them.	Use baseCount to store the current number of nodes, which is designed to change the problem in baseCount concurrent environment

A HashMap (1.8)

1. What is hash

Core theory: Hash is also called Hash, and the corresponding English words are all Hash. The basic principle is to turn input of arbitrary length into output of fixed length through the Hash algorithm. The rules of this mapping are the corresponding Hash algorithm, and the mapped binary string of the original data is the Hash value.

The characteristics of the Hash

The original data cannot be derived backwards from the hash value
Minor changes in input data will result in a completely different hash value, and the same data will result in the same value
Hash algorithm to efficient execution, long text can also quickly calculate the hash value
The collision probability of the hash algorithm is low
- The principle of hash is to map the value of the input space into the hash space, and the hash value space is much smaller than the input space. According to the drawer principle, there must be cases where different inputs are mapped to the same outputs

Drawer principle: there are 10 apples on the desk, you should put these 10 apples in 9 drawers, no matter how you put them, there will be at least one drawer with no less than two apples

2. HashMap inheritance

3. Node data structure

static class Node<K.V> implements Map.Entry<K.V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey(a)        { return key; }
    public final V getValue(a)      { return value; }
    public final String toString(a) { return key + "=" + val
    public final int hashCode(a) {
        return Objects.hashCode(key) ^ Objects.hashCode(val
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false; }}Copy the code

4. Low level storage structure

Array + linked list + red-black tree

5. Put data principle analysis

Routing addressing formula

(table.length - 1) & node.hash
Copy the code

N & m minus 1 is n % m.

6. What is a hash collision

When we hash an element, get a storage address, and then try to insert it, and it’s already occupied by another element, this is actually called a hash collision, also called a hash collision.

The design of the hash function is very important. A good hash function will ensure that the calculation is as simple as possible and the hash address is evenly distributed. However, we need to remember that the array is a contiguous fixed length of memory space, and no good hash function can guarantee that the resulting storage address will never collide. So how do hash conflicts get resolved? There are several solutions to hash conflicts:

Open address method (conflict, continue to find the next unoccupied storage address)
Rehash function
Chain address method, and HashMap is the use of chain address method, that is, array + linked list

Simply put, HashMap consists of array + linked list. Array is the body of HashMap, while linked list is mainly used to solve hash conflicts. If the array location does not contain a linked list (the next of the current entry points to NULL), search, add and other operations will be very quick and only need one address. If the array to be located contains a linked list, the time complexity of the add operation is O(n), and the linked list is first traversed. If it exists, it will be overwritten; otherwise, it will be added. For lookups, you still need to traverse the linked list and then compare lookups one by one through the Equals method of the key object. Therefore, for performance purposes, the fewer linked lists in a HashMap, the better the performance.

7. Source code analysis of HashMap

7.1, attributes,

Default table size

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
Copy the code

Table Maximum length

static final int MAXIMUM_CAPACITY = 1 << 30;
Copy the code

The load factor

static final float DEFAULT_LOAD_FACTOR = 0.75 f;
Copy the code

Tree threshold

static final int TREEIFY_THRESHOLD = 8;
Copy the code

Threshold value chain

static final int UNTREEIFY_THRESHOLD = 6;
Copy the code

Minimum number of elements to tree

static final int MIN_TREEIFY_CAPACITY = 64;
Copy the code

Capacity threshold

intthreshold; Threshold = capacity * loadFactor (capacity expansion threshold = current capacity * loadFactor)Copy the code

7.2. Construction method

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(a) {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
Copy the code

TableSizeFor Returns a number greater than the current cap. The number must be a power of 2

static final int tableSizeFor(int cap) {
    int n = cap - 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 code

Set any binary number 0001 1101 1100 => 0001 1111 1111 Set all the digits after the first 1 of any binary number to 1

Why is the underlying array length of a HashMap always 2 to the n

Make data evenly distributed, reduce collision
When length is 2 to the n power, h&(length-1) is equivalent to taking the modulus of length, and in the speed, efficiency is much faster than taking the modulus directly

7.3. Put method

public V put(K key, V value) {
	return putVal(hash(key), key, value, false.true);
}
Copy the code

The hash function

static final int hash(Object key) {
	int h;
	return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

Why xOR?

Because the probability of 0 and 1 after xOR of two binary numbers is 0.5, and the probability of region operation is different

Return value of hash result: the xor result 16 bits higher and 16 bits lower of the hashCode value of key

Why do you do that?

Because before the HashMap was expanded, the table size was very small (16,32,64…). In this case, according to the route addressing algorithm (table.length-1) & Node. hash, only the lower bits can be used. The reason why the higher 16 bits and lower 16 bits are xOR is that the higher 16 bits of the key are also involved in the route selection process. Reduce hash collisions.

Why use xOR operators?

Guarantees that the entire hash() return value will change if one bit of the object’s hashCode 32-bit value changes. Minimize collisions as much as possible.

PutVal method

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // TAB references the hash table of the current HashMap
    //p Elements of the current hash table
    //n Hash table length
    // I Result of route addressing
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // If the current hash table is not initialized (the hash table is empty or has a length of 0), the hash table is initialized
    // lazy loading, initialization only when put (save memory)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // Add k, V -> node to bucket
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        
        // The bucket bit is not empty
        //e Specifies the node equal to the current key
        Node<K,V> e; K k;
        // The head key of the current bucket is the same as the insert key
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // The current node is treed
        else if (p instanceof TreeNode)
            //e does not find a node with the same key for null
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // The current node is not treed
        else {
            // loop linked lists
            for (int binCount = 0; ; ++binCount) {
                // Loop to the end of the list and add nodes directly to the end
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Find a node equal to key
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break; p = e; }}// Find a node equal to key
        if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            returnoldValue; }}// No node is found equal to key
    ++modCount;
    // Whether to expand the capacity
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

putTreeVal

PutTreeVal Red-black tree version of the insert

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) { Class<? > kc =null;
    boolean searched = false;
    // Check whether the current node is the root node and fetch the current root nodeTreeNode<K,V> root = (parent ! =null)? root() :this;
    // Walk through the red black tree
    for (TreeNode<K,V> p = root;;) {
        //p current node
        //ph Hash of the current node
        //pk key of the current node
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        // The root node is equal to the insert node
        else if((pk = p.key) == k || (k ! =null && k.equals(pk)))
            return p;
       	/** * The next step is to check if there are hash identical and equals identical nodes when a conflict occurs (i.e. hash equal). * is a test to see if the key exists in the tree */
		Hash is the same but equal is different
		Comparable
      
        is not implemented or implemented and k is the same as PK Comparable
      
        else if ((kc == null &&
                  If the class of k is C and C implements the Comparable
      
        interface, then the class of k is returned, otherwise null is returned
      
                  (kc = comparableClassFor(k)) == null) | |//kc returns the same comparison value as pk, otherwise 0
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if(! searched) {//ch: the child node of p
                //kc is the current class of k
                //k Insert the key of the node
                TreeNode<K,V> q, ch;
                searched = true;
                // Find the same points in the left and right subtrees of the current node as the inserted node
                // Find return
                if(((ch = p.left) ! =null&& (q = ch.find(h, k, kc)) ! =null) || ((ch = p.right) ! =null&& (q = ch.find(h, k, kc)) ! =null))
                    return q;
            }
            // If there is no equal to equals in the red-black tree, an insert must be performed
			// The method of breaking balance has a split size of -1, 1
            dir = tieBreakOrder(k, pk);
        }
        // Perform the following operations to insert the node
		//xp saves the current node
        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0)? p.left : p.right) ==null) {
            Node<K,V> xpn = xp.next
            // Create a node;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
             // The new node is smaller than the parent node
             xp.left = x;
             else
         // Put the node larger than the parent in the right child position
                xp.right = x;
                    
                // Maintain double-linked list relationships
                xp.next = x;
				x.parent = x.prev = xp;
				if(xpn ! =null)
					((TreeNode<K,V>)xpn).prev = x;
				// Move root to the first node in position I of the table array
				// Rebalance after inserting through the red-black tree.
				moveRootToFront(tab, balanceInsertion(root, x));
				return null; }}}Copy the code

find

find

 /** * finds the node that specifies the hash value and key from the root node p ** when the first comparator is used to compare keys, the parameter kc stores the comparator class */ for the key
 final TreeNode<K,V> find(inth, Object k, Class<? > kc) {
     TreeNode<K,V> p = this;
     do {
         int ph, dir; K pk;
         TreeNode<K,V> pl = p.left, pr = p.right, q;
         if ((ph = p.hash) > h)			// Enter the left node if the given hash value is less than the current node's hash value
             p = pl;
         else if (ph < h)				// If greater than, enter the right node
             p = pr;
         else if((pk = p.key) == k || (k ! =null && k.equals(pk)))	// Returns the current node if the hash values are equal and the keywords are equal
             return p;
         else if (pl == null)		// If the left node is empty, the right node is entered
             p = pr;
         else if (pr == null)		// If the right node is empty, the left node is entered
             p = pl;
         else if((kc ! =null|| (kc = comparableClassFor(k)) ! =null) && (dir = compareComparables(kc, k, pk)) ! =0)		// If you sort by the comparator instead of the hash value, then the comparator returns the value to decide to enter the left and right nodes
             p = (dir < 0)? pl : pr;else if((q = pr.find(h, k, kc)) ! =null)		// If the keyword is found in the right node, return it directly
             return q;
         else
             p = pl;								// Enter the left node
     } while(p ! =null);
     return null;
 }
Copy the code

treeifyBin

TreeifyBin converts the current list to a double-linked list

final void treeifyBin(Node<K,V>[] tab, int hash) {
    //e list the current node
    //index Indicates the result of route addressing
    / / n barrel length
    int n, index; Node<K,V> e;
    // If the bucket bit is empty or the bucket length is smaller than the minimum number of elements in the tree, expand the bucket first
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // The bucket bit is not empty
    else if ((e = tab[index = (n - 1) & hash]) ! =null) {
        //hd head node of the bidirectional list
        // The last node of the bidirectional list
        TreeNode<K,V> hd = null, tl = null;
        // Loop through the bucket list to create a bidirectional list
        do {
            // Create a TreeNode that is the same as p, with next, left, and right empty
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // Populate prev and next
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while((e = e.next) ! =null);
        if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code

replacementTreeNode

ReplacementTreeNode Returns a TreeNode parameter equal to the Node value

// Create a TreeNode that is the same as p, with next, left, and right empty
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
Copy the code

treeify

Treeify’s true tree operation inserts a bidirectional list into a red-black tree with root as the root node

/**
 * Forms tree of the nodes linked from this node.
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // Loop through the current TAB
    for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // If the current red-black tree is empty, assign the first node to the root node
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            //k Specifies the key currently inserted into the red-black tree node
            K k = x.key;
            int h = x.hash;
            //kc is the current type of k.Class<? > kc =null;
            for (TreeNode<K,V> p = root;;) {
                //ph Hash value of the current node
                //pk Key value of the current node
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          If the class of k is C and C implements the Comparable
      
        interface, then the class of k is returned, otherwise null is returned
      
                          (kc = comparableClassFor(k)) == null) | |// If pk belongs to kc, return k.compareTo(x) comparison result
							// Return 0 if pk is empty or its class is not KC
                         // The type of the inserted node PK is not the type of the current node KC
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // Compare the key of the inserted node with that of the current tree node
                    dir = tieBreakOrder(k, pk);
                TreeNode<K,V> xp = p;
                //dir less than or equal to 0 is inserted to the left of the red-black tree, and vice versa
                // Insert the current node x if the left or right side of p is empty
                if ((p = (dir <= 0)? p.left : p.right) ==null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // Insert balance to return the current root node
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}
Copy the code

comparableClassFor

ComparableClassFor determines whether the class implements the Comparable interface

If the class of object X is C and C implements the Comparable
      
        interface, then C is returned, otherwise NULL is returned
      
staticClass<? > comparableClassFor(Object x) {if (x instanceofComparable) { Class<? > c; Type[] ts, as; Type t; ParameterizedType p;// Why is c returned if x is a string? Because String implements the Comparable interface, see the definition of the String class below
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        // If c is not a string class, get the interface implemented directly by C (with generic information if it is a generic interface)
        if((ts = c.getGenericInterfaces()) ! =null) {
            for (int i = 0; i < ts.length; ++i) {
                // If t is a generic interface
                // If the primitive type p of the generic interface t is a Comparable interface
                // If the Comparable interface p defines only one generic parameter
                // If the generic parameter is of type C, return c
                if (((t = ts[i]) instanceofParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) ! =null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    returnc; }}}return null;
}
Copy the code

compareComparables

CompareComparables returns the comparison value if the type is the same, or 0 if the type is different

// If x belongs to kc, return k.compareTo(x)
// If x is empty, or if it belongs to a class other than KC, return 0
static int compareComparables(Class
        kc, Object k, Object x) {
    return (x == null|| x.getClass() ! = kc ?0 :
            ((Comparable)k).compareTo(x));
}
Copy the code

tieBreakOrder

TieBreakOrder forces a size comparison between two nodes (must return a comparison value)

Using this method to compare two objects, the return value is either greater than0, or less than0, not for0That is to say, this step will be sure to insert the node is either left node of the tree, are either right node, otherwise there is no continue to meet the binary tree structure To compare the two object class name, the name of the class is a string object, as a string of rules If two objects are the same type, then call native methods for two objects to generate hashCode values, If hashCode is equal, return -1
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;
}
Copy the code

balanceInsertion

BalanceInsertion balancing maintains the balance of red-black trees

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode
       
         root, TreeNode
        
          x)
        ,v>
       ,v> {
    x.red = true;
    // Parent node of XP X
    // XPP x's grandfather node
    // XPPL x left uncle node
    // XPPR x right uncle node
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // The parent of the inserted node is empty, an empty tree
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // The parent node is black and the grandfather node does not exist
        // Insert directly without doing any balancing
        else if(! xp.red || (xpp = xp.parent) ==null)
            return root;
        // The parent of the inserted node is the left node of the grandfather node
        if (xp == (xppl = xpp.left)) {
            // The right uncle node exists and is red
            // The uncle node and the parent node become black, and the grandfather node becomes red, setting the grandfather node to the current inserted node
            if((xppr = xpp.right) ! =null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {// The uncle node is empty or black
                // The inserted node is the parent's right node LR double red
                if (x == xp.right) {
                    // Left-rotate the parent node
                    root = rotateLeft(root, x = xp);
                    // reassign XPP
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                / / LL double red
                if(xp ! =null) {
                    // The parent node and the grandfather node are changed to red to right-rotate the grandfather node
                    xp.red = false;
                    if(xpp ! =null) {
                        xpp.red = true; root = rotateRight(root, xpp); }}}}// The parent of the inserted node is the right node of the grandfather node
        else {
            // The left uncle node is not empty and is red
            // The uncle node and the parent node become black, and the grandfather node becomes red, setting the grandfather node to the current inserted node
            if(xppl ! =null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {// The uncle node is empty or black
                // The inserted node is the left node of the parent node RL double red
                if (x == xp.left) {
                     // Rotate the parent node right
                    root = rotateRight(root, x = xp);
                    // reassign XPP
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                / / LL double red
                if(xp ! =null) {
                    // The parent node and the grandfather node are changed to red to right-rotate the grandfather node
                    xp.red = false;
                    if(xpp ! =null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}
Copy the code

rotateLeft

left-handedstatic <K,V> TreeNode<K,V> rotateLeft(TreeNode
       
         root, TreeNode
        
          p)
        ,v>
       ,v> {
    TreeNode<K,V> r, pp, rl;
    if(p ! =null&& (r = p.right) ! =null) {
        if((rl = p.right = r.left) ! =null)
            rl.parent = p;
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        r.left = p;
        p.parent = r;
    }
    return root;
Copy the code

rotateRight

Right handstatic <K,V> TreeNode<K,V> rotateRight(TreeNode
       
         root, TreeNode
        
          p)
        ,v>
       ,v> {
    TreeNode<K,V> l, pp, lr;
    if(p ! =null&& (l = p.left) ! =null) {
        if((lr = p.left = l.right) ! =null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}
Copy the code

moveRootToFront

MoveRootToFront ensures that the current red-black tree is still an ordered double-linked list

TreeNode is both a red-black tree and a double-linked list. What we're doing here is we're making sure that the root of the tree is also the first node in the liststatic <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if(root ! =null&& tab ! =null && (n = tab.length) > 0) { // The root node is not empty and the element array of the HashMap is not empty
        int index = (n - 1) & root.hash; // Get the root node position in the array based on the Hash value of the root node and the array length of the elements of the HashMap
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // Get the first node object at that position
        if(root ! = first) {// If the object is different from the root object
            Node<K,V> rn; // Define the next node of the root node
            tab[index] = root; // Replace the element at index position with the root node object
            TreeNode<K,V> rp = root.prev; // Get the previous node of the root node object
            if((rn = root.next) ! =null) // If the back node is not empty
                ((TreeNode<K,V>)rn).prev = rp; // The former node of the post-root node points to the former node of root, which is equivalent to removing root from the linked list
            if(rp ! =null) // If the former node of root is not empty
                rp.next = rn; // The back node of the root node points to the back node of root
            if(first ! =null) // If the original element at that position is not empty
                first.prev = root; // The former node of the original element points to root, which is currently at the top of the list
            root.next = first; // The original first node is now the next node of root and becomes the second node
            root.prev = null; // The first node has no previous node
        }
 
        /* * This step is defensive programming * verify that the TreeNode object meets the red-black tree and double-linked list properties * If this method fails: the user may have made a programming error and broken the structure (for example, in concurrent scenarios); There could be a problem with the TreeNode implementation (this is theoretical, just in case). * / 
        assert checkInvariants(root); }}Copy the code

checkInvariants

CheckInvariants verify the accuracy of red-black trees

Verifying the accuracy of red-black trees, checkInvariants (this method works by adding -AE to the priming parameter)static <K, V> boolean checkInvariants(HashMap.TreeNode<K, V> t) {
            // TP - parent, TL - left child, TR - right child, TP - precursor, TN - successor
            HashMap.TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right,
                    tb = t.prev, tn = (HashMap.TreeNode<K, V>) t.next;
            // The red-black tree or bidirectional linked list is incorrect when one of the following conditions occurs
            // 1. If the precursor node exists, but its successor is not the current node
            if(tb ! =null&& tb.next ! = t)return false;
            // 2. If the successor node exists, but its predecessor is not the current node
            if(tn ! =null&& tn.prev ! = t)return false;
            The parent node exists, but the left and right children of the parent node are not the current node
            if(tp ! =null&& t ! = tp.left && t ! = tp.right)return false;
            // The left child node exists. However, the parent of the left child node is not the current node or the hash value of the left child node is greater than the hash value of the current node
            if(tl ! =null&& (tl.parent ! = t || tl.hash > t.hash))return false;
            // The right child node exists. However, the parent of the right child node is not the current node or the hash value of the right child node is smaller than the hash value of the current node
            if(tr ! =null&& (tr.parent ! = t || tr.hash < t.hash))return false;
            // 6. The current node is red, and the child node is red
            if(t.red && tl ! =null&& tl.red && tr ! =null && tr.red)
                return false;
            // Recursively validate the left subtree
            if(tl ! =null && !checkInvariants(tl))
                return false;
            // Recursively validate the right subtree
            if(tr ! =null && !checkInvariants(tr))
                return false;
            // Return true if all are correct
            return true;
}
Copy the code

7.4. Resize method

final Node<K,V>[] resize() {
    //oldTab reference points to the hash table before expansion
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null)?0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    / * < = = = = = = = = = = = = = = = = = = = = = = = = newCap, newThr assignment = = = = = = = = = = = = = = = = = = = = = = = = = = > * /
    // There is initial capacity before capacity expansion
    if (oldCap > 0) {
        // If the initial capacity is greater than the maximum length of the table
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // The capacity of the table after expansion is smaller than the maximum length of the table, and the capacity of the table before expansion is larger than the default length of the table
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    / / calls
    //HashMap(int initialCapacity, float loadFactor)
    //HashMap(map)
    // Initial capacity expansion threshold is set but table is not initialized (first capacity expansion)
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // HashMap()
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // If newThr is zero, compute a newThr
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    / * < = = = = = = = = = = = = = = = = = = = = = = = = newCap, newThr assignment = = = = = = = = = = = = = = = = = = = = = = = = = = > * /
 
    
    / * < = = = = = = = = = = = = = = = = = = = = = = = = expansion = = = = = = = = = = = = = = = = = = = = = = = = = = > * /
    @SuppressWarnings({"rawtypes","unchecked"})
    	// Create a new hash table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // There was data in the original hash table before expansion
    if(oldTab ! =null) {
        for (int j = 0; j < oldCap; ++j) {	
            // The current node
            Node<K,V> e;
            // The current bucket bit has data
            if((e = oldTab[j]) ! =null) {
                // Facilitate JVM GC collection
                oldTab[j] = null;
                // In the first case, there is only one node at the current bucket level and the assignment is rerouted directly
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // In the second case, the current bucket level is already treed
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // In the third case, the current bucket level is already lotus chain
                else { // preserve order
                    // The bucket list can be divided into two lists, namely low and high
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        // Split the list into two lists sequentially using the tail interpolation method
                        next = e.next;
                        //oldCap = 16
                        //e.hash & 10000
                        // If the value is 0, the lowest bit is 0
                        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);
                    // Low level linked list
                    if(loTail ! =null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // High order list
                    if(hiTail ! =null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    / * < = = = = = = = = = = = = = = = = = = = = = = = = expansion = = = = = = = = = = = = = = = = = = = = = = = = = = > * /
    return newTab;
}
Copy the code

The node with 16 bucket bits is expanded to 32 bucket bits

The nodes at bucket 15 have a common feature, Hash = (11111) hash = (11111) hash = (11111) hash = (11111) hash = (11111) hash = (table. Length-1) hash = (11111) hash = (11111) hash = (11111) hash = (11111) hash = (table Hash shows that the 01111 readdressing bucket is 15 and the 11111 readdressing bucket is 31(15 + oldCap).

The jdk1.7 resize() method has a capacity expansion loop under multi-threaded access

split

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    / / new table TAB
    //index indicates the current bucket bit
    //bit Specifies the table size of the original array
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    // Low and high
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    // Loop the current bucket node (double linked list)
    for(TreeNode<K,V> e = b, next; e ! =null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        // end ()
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        // select * from ();
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            elsehiTail.next = e; hiTail = e; ++hc; }}if(loHead ! =null) {
        // The current list is less than the chain threshold
        if (lc <= UNTREEIFY_THRESHOLD)
            / / chain
            tab[index] = loHead.untreeify(map);
        else {
            // Re-tree the current double-linked list
            tab[index] = loHead;
            if(hiHead ! =null) // (else is already treeified)loHead.treeify(tab); }}if(hiHead ! =null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if(loHead ! =null) hiHead.treeify(tab); }}}Copy the code

untreeify

untreeify

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // loop double linked list
    for (Node<K,V> q = this; q ! =null; q = q.next) {
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}
Copy the code

replacementNode

Returns one that is exactly equal to the TreeNodeNode
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}
Copy the code

7.5. Get method

public V get(Object key) {
	Node<K,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code

GetNode () method

final Node<K,V> getNode(int hash, Object key) {
    // the TAB reference points to the current hash table
    //first specifies the first node of the bucket
    / / n table length
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // The hash table is not empty and the first node in the bucket addressed by the hash(key) route exists
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) ! =null) {
        // The first node is the desired node
        if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        // In the second case, the current node is already treed
        if((e = first.next) ! =null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // Third case: the current node is already linked
            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

7.6. Remove method

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null.false.true)) = =null ?
        null : e.value;
}
Copy the code

RemoveNode () method

//matchValue Deletes whether value needs to be matched
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // the TAB reference points to the current hash table
    //p The first node of the current bucket
    //index indicates the result of addressing
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // The hash table is not empty and the first node in the bucket addressed by the hash(key) route exists
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) ! =null) {
        // The node to be deleted
        Node<K,V> node = null, e; K k; V v;
        // If the current node happens to be the node to be deleted
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            node = p;
        // The current node is not the node to be deleted
        else if((e = p.next) ! =null) {
            // The node is already treed
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // The node is chained
            else {
                do {
                    // Find the specified node
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // The precursor of the current node
                    p = e;
                } while((e = e.next) ! =null); }}// The node to delete is found
        if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
            // If the tree is tree-like
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // The node to be deleted is the first node in the bucket
            else if (node == p)
                tab[index] = node.next;
            // The nodes to be deleted are other nodes in the list
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            returnnode; }}// Not found
    return null;
}
Copy the code

removeTreeNode

removeTreeNode

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    //n Specifies the length of the current table
    int n;
    // Returns if the current hash table is not initialized or the current length is 0
    if (tab == null || (n = tab.length) == 0)
        return;
    // The route addresses the bucket of the current former node
    int index = (n - 1) & hash;
    //first Specifies the head of the current double-linked list
    //root Indicates the root node of the current red-black tree
    // Rl root left node
    //succ the successor of the current node
    //pred Indicates the precursor of the current node
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    // If the precursor node is empty, the deleted node is the head node
    if (pred == null)
        tab[index] = first = succ;
    else
        // Delete the current node directly
        pred.next = succ;
    // The precursor node of suCC points to pred
    if(succ ! =null)
        succ.prev = pred;
    // The deleted node is returned directly from the head node
    if (first == null)
        return;
    // The parent of the root node is not empty
    if(root.parent ! =null)
        // Find the parent node and assign it to root
        root = root.root();
    // Judge --> chain
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    //p The node is being deleted
    //pl Deletes the left node of the node
    //pr deletes the right node of the node
    //replacement
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if(pl ! =null&& pr ! =null) {
        TreeNode<K,V> s = pr, sl;
        while((sl = s.left) ! =null) // find successor
            s = sl;
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if((p.parent = sp) ! =null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if((s.right = pr) ! =null)
                pr.parent = s;
        }
        p.left = null;
        if((p.right = sr) ! =null)
            sr.parent = p;
        if((s.left = pl) ! =null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        if(sr ! =null)
            replacement = sr;
        else
            replacement = p;
    }
    else if(pl ! =null)
        replacement = pl;
    else if(pr ! =null)
        replacement = pr;
    else
        replacement = p;
    if(replacement ! = p) { TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if(pp ! =null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null; }}if (movable)
        moveRootToFront(tab, r);
}
Copy the code

root

Root Returns the current root node

/** * Returns root of tree containing this node. */
final TreeNode<K,V> root(a) {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            returnr; r = p; }}Copy the code

7.7. Replace method

@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if((e = getNode(hash(key), key)) ! =null&& ((v = e.value) == oldValue || (v ! =null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}
@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if((e = getNode(hash(key), key)) ! =null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}
Copy the code

HashMap difference between JDK1.7 and 1.8

The mark	JDK1.7	JDK1.8
Different Hash methods	Returns the result if the key is a string. The hashCode of the key is unregulated and can be controlled by setting the hash seed in the environment variable	Key’s hashCode is 16 bits higher or 16 bits lower
Sequence of PUT and resize	Expand capacity and then insert	Insert before expanding
The data structure	Array + linked list	Array + linked list + red-black tree
Data is transferred differently after capacity expansion	Recalculation of subscripts with hash and NewCap-1, head interpolation (threaded to create an infinite loop when traversing the list) (prevented by controlling expansion)1.7 changes the hash value to decentralize by updating the hashSeed	Compute the highest bits 1 and 0 using hash and newCap
Expansion conditions	Size is greater than the capacity expansion threshold, and the current table[index] is not null	If the size is greater than the capacity expansion threshold, the current bucket bit is not empty, and the table length is less than or equal to 64 (not tree-like), expand the capacity directly
Table loading mode	The table is initialized directly in the constructor	Lazy loading, the first put is to initialize the table

Red and black tree

Why do you need a red black tree when you have a balanced tree?

Although the balanced tree solves the problem that binary tree degenerates into an approximate linked list and can control the search time within O(logn), it is not the best
Because the left child of each node is balanced tree request tree and the height of the right subtree is poor at most equal to 1, this request is too strict, lead to every time to insert/delete nodes, almost always destroy the balance tree second rule, then we need to be adjusted, left-handed and a right-handed for the balance of the once again become a meet the requirements of the tree.
Obviously, if the balance tree needs to be adjusted frequently in the scene of frequent insertion and deletion, the performance of the balance tree will be greatly compromised. To solve this problem, the red black tree was created.

Properties of red-black trees

Properties of red-black trees
Property 1: Each node is either black or red
Property 2: The root node is black
Property 3: Each leaf node (NIL) is black
Property 4: Two children of each red node must be black. Two red nodes cannot be connected
Property 5: The path from any node to each leaf node contains the same number of black nodes, commonly known asThe black high
From property 5, it can be inferred that if a node has sunspot nodes, the node must have two child nodes

Black perfectly balanced

The number of black node layers in the left and right subtrees is equal, that is, the path from any node to each leaf node contains the same number of black nodes.

How does a red-black tree guarantee homeostasis

Color change: Node color changes from red to black or from black to red.
Left-rotation: A node is used as the fulcrum to rotate the node. The right node becomes the parent node of the rotating node, and the left child node of the right child node becomes the right child node of the rotating node. The left child node remains unchanged.
Dextral: A node is used as the fulcrum to rotate the node. The left child becomes the parent of the node, the right child of the left child becomes the left child of the node, and the right child remains unchanged.

left-handed

public void leftRotate(a){
    Node newNode = new Node(val);
    newNode.left = left;
    newNode.right = right.left;
    val = right.val;
    right = right.right;
    left = newNode;
}
Copy the code

Right hand

public void rightRotate(a){
    Node newNode = new Node(val);
    newNode.right = right;
    newNode.left = left.right;
    val = left.val;
    left = left.left;
    right = newNode;
}
Copy the code

Red-black tree insertion

Insert operation steps:

Find where to insert
Self-balancing after insertion

Pay attention to

Insert node, must be red, the reason is simple: red when the parent node (if any) is black, the black balance of the red-black tree is not broken, there is no need to self-balance. However, if the insertion node is black, then the black node in the subtree where the insertion position is always one more, which needs to be self-balanced

Scenario 1

A red-black tree is an empty tree

Take the insert node directly as the root node

According to property 2 of red-black tree: the root node is black, you also need to set the inserted node to red

Scenario 2

The key of the node already exists

Update the value of the current node to the value of the inserted node

Scenario 3

The parent of the inserted node is a black node

Since the inserted node is red, if the parent node of the inserted node is black, it does not affect the balance of the red-black tree, and can be directly inserted

Scenario 4

The parent node of the inserted node is red

Property 2: The root node must be black. If the parent node of the inserted node is red, the parent node cannot be the root node, so the inserted node always has a grandfather node

The situation of 4.1

The uncle node exists and is red

According to property 4 of red-black tree: red nodes cannot be connected

Processing:

Change the P and U nodes to black
Change PP to red
Set the PP to the current node and perform subsequent operations

The situation of 4.2

The uncle node does not exist or is black, and the parent node of the inserted node is the left child node of the grandfather node

Scenario 2

Newly inserted node, the left child of its parent node (LL double red)

Processing:

Change P to black and PP to red
Right rotation of PP

Scene 4.2.2

Newly inserted node, which is the right child of its parent node (LR double red)

Processing:

I rotate P left
Setting P to the current node gives LL double red
According to LL double red treatment
1. Change P to black and PP to red
2. Right rotation of PP

The situation of 4.3

The uncle node does not exist or is black, and the parent node of the inserted node is the right child node of the grandfather node

Scene 4.3.1

Newly inserted node, the right child of its parent node (RR double red)

Processing:

Change P to black and PP to red
Left rotation of PP

Scene 4.3.2

Newly inserted node, the left child of its parent node (RL double red)

Processing:

Right rotation with respect to P
Setting P to the current node yields RR double red
RR double red treatment
1. Change P to black and PP to red
2. Left rotation of PP

Inserted into the case

Handwritten red black tree

Steps:

Create RBTree and define colors
Create RBNode
Helper methods: parentOf(node), isRed(), setRed(), setBlack(), inOrderPrint()
LeftRotate (node), rightRotate(node)
Public insert interface method definition: insert(K key, V value);
Internal insert interface method definition: insert(RBNode node);
Fixed insert method definition causing red-black tree imbalance: insertFlxUp(RBNode node);
test

package school.xauat.datastructres.rbtree;

/ * * *@author: zsy *@date: Created 2021/4/17 11:36 *@description: red black tree */

import java.util.Base64;

/** * step: ** 1. Create RBTree and define color * 2. ParentOf (node), isRed(), setRed(), setBlack(), inOrderPrint() * 4. LeftRotate (node), rightRotate(node) * 5. Public insert interface method definition: insert(K key, V value); Insert (RBNode node); InsertFlxUp (RBNode node); * 8. Test */
public class RBTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private RBNode root;

    public void insert(K key, V value) {
        RBNode newNode = new RBNode();
        newNode.setKey(key);
        newNode.setValue(value);
        newNode.setColor(RED);
        insert(newNode);
    }

    /** * Insert node *@param node
     */
    private void insert(RBNode node) {
        if (root == null) {
            root = node;
            setBlack(root);
            return;
        }
        // Find the parent node to insert
        RBNode tmp = root;
        RBNode parent = null;
        while(tmp ! =null) {
            parent = tmp;
            int cmp = node.key.compareTo(tmp.key);
            if (cmp == 0) {
                // The inserted node already exists in scenario 2
                tmp.setValue(node.getValue());
                return;
            }
            if (cmp < 0) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }
        node.parent = parent;
        if(parent ! =null) {
            int cmp = node.key.compareTo(parent.key);
            if (cmp > 0) {
                parent.right = node;
            } else{ parent.left = node; }}// Call the method to repair the red-black tree balance
        insertFlxUp(node);
    }

    /** * Fixed red-black tree balance *@param node
     */
    private void insertFlxUp(RBNode node) {
        // The root nodes are dyed black
        setBlack(root);
        RBNode parent = parentOf(node);
        RBNode pp = parentOf(parent);
        RBNode uncle = null;
        if(parent ! =null && isRed(parent)) { 4 / / sight
            // Find the uncle node
            if(pp.left ! =null && pp.left.key.equals(parent.key)) {
                uncle = pp.right;
            } else {
                uncle = pp.left;
            }

            if(uncle ! =null && isRed(uncle)) {// Situation 4.1: Uncle is present and red
                setBlack(parent);
                setBlack(uncle);
                setRed(pp);
                insertFlxUp(pp);
                return;
            } else { // Scenario 4.2: The uncle node does not exist or exists as a black node
                if(pp.left ! =null && pp.left == parent) { // Scenario 4.2: The parent of the inserted node is the left child of the grandfather node
                    if(parent.left ! =null && parent.left == node) {// Scenario 4.2.1LL Double red: Insert node as the left node of the parent
                        setBlack(parent);
                        setRed(pp);
                        rightRotate(pp);
                    } else { // Scenario 4.2.2LR double red
                        leftRotate(parent);
                        insertFlxUp(parent);
                        return; }}else { // Scenario 4.3: The parent node of the inserted node is the right child of the grandfather node
                    if(parent.right ! =null && parent.right == node) {Scenario 4.3.1RR double red: the newly inserted node is the right child of its parent node
                        setBlack(parent);
                        setRed(pp);
                        leftRotate(pp);
                        return;
                    } else { // Scenario 4.3.2: RL double red
                        rightRotate(parent);
                        insertFlxUp(parent);
                        return;
                    }
                }
            }
        }
    }

    / * * * l * * p p * | | * x * y / \ -- -- -- -- -- - > / / \ \ * ry lx y x * / \ * ly ry lx ly *@param x
     */
    private void leftRotate(RBNode x) {
        RBNode y = x.right;
        // Point the right child of x to the left child of y and update the parent of the left child to x
        x.right = y.left;
        if(y.left ! =null) {
            y.left.parent = x;
        }
        // When the parent of x is not empty, update the parent of y to the parent of x, and point the parent of x to y
        if(x.parent ! =null) {
            y.parent = x.parent;
            if (x == x.parent.left) {
                x.parent.left = y;
            } else{ x.parent.right = y; }}else { //x is the root node, update the root node
            this.root = y;
        }
        // Update the parent node of x to y and the left child node of y to x
        x.parent = y;
        y.left = x;
    }

    / p p * * * right * * * | | * x * y / \ -- -- -- -- -- - > / \ * y lx ly / \ \ x * * ly ry ry lx *@param x
     */
    private void rightRotate(RBNode x) {
        RBNode y = x.left;
        // Point the left child of x to the right child of y, and update the parent of the right child to x
        x.left = y.right;
        if(y.right ! =null) {
            y.right.parent = x;
        }
        // When the parent of x is not empty, update the parent of y to the parent of x, and point the parent of x to y
        if(x.parent ! =null) {
            y.parent = x.parent;
            if (x == x.parent.left) {
                x.parent.left = y;
            } else{ x.parent.right = y; }}else { //x is the root node, update the root node
            this.root = y;
        }
        // Update the parent node of x to y and the left child node of y to x
        x.parent = y;
        y.right = x;
    }

    public void inOrderPrint(a) {
        inOrderPrint(root);
    }

    public void preOrderPrint(a) {
        preOrderPrint(root);
    }

    /** * Print red black tree *@param node
     */
    private void inOrderPrint(RBNode node) {
        if (node == null)return;
        inOrderPrint(node.left);
        System.out.println(node);
        inOrderPrint(node.right);
    }

    /** * Print red black tree *@param node
     */
    private void preOrderPrint(RBNode node) {
        if (node == null)return;
        System.out.println(node);
        preOrderPrint(node.left);
        preOrderPrint(node.right);
    }

    /** * Get the parent node * of the node@param node
     * @return* /
    public RBNode parentOf(RBNode node) {
        if(node ! =null) {
            return node.parent;
        }
        return null;
    }

    /** * Check whether the node is red *@param node
     * @return* /
    private boolean isRed(RBNode node) {
        if(node ! =null) {
            return node.color == RED;
        }
        return false;
    }

    /** * Sets the current node to red *@param node
     */
    private void setRed(RBNode node) {
        if(node ! =null) { node.color = RED; }}/** * Sets the current node to black *@param node
     */
    private void setBlack(RBNode node) {
        if(node ! =null) { node.color = BLACK; }}/** * Check whether the node is black *@param node
     * @return* /
    private boolean isBlack(RBNode node) {
        if(node ! =null) {
            return node.color == BLACK;
        }
        return false;
    }

    static class RBNode<K extends Comparable<K>, V> {
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

         public RBNode(a) {}


         public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
             this.parent = parent;
             this.left = left;
             this.right = right;
             this.color = color;
             this.key = key;
             this.value = value;
         }

         public RBNode getParent(a) {
             return parent;
         }

         public void setParent(RBNode parent) {
             this.parent = parent;
         }

         public RBNode getLeft(a) {
             return left;
         }

         public void setLeft(RBNode left) {
             this.left = left;
         }

         public RBNode getRight(a) {
             return right;
         }

         public void setRight(RBNode right) {
             this.right = right;
         }

         public boolean isColor(a) {
             return color;
         }

         public void setColor(boolean color) {
             this.color = color;
         }

         public K getKey(a) {
             return key;
         }

         public void setKey(K key) {
             this.key = key;
         }

         public V getValue(a) {
             return value;
         }

         public void setValue(V value) {
             this.value = value;
         }

        @Override
        public String toString(a) {
            return "RBNode{" +
                    "color=" + color +
                    ", key=" + key +
                    ", value=" + value +
                    '} '; }}}Copy the code

A HashMap interview questions

What can go wrong with HashMap thread safety

In jdk1.7, in a multi-threaded environment, capacity expansion causes loop chains or data loss
In jdk1.8, data overwriting occurs in a multithreaded environment
- The main function of the put operation in HashMap in JDk1.8, which inserts elements directly if there is no hash collision. If thread A and thread B perform A put operation at the same time, the hash value of the two different data is the same, and the data is null, so thread A and thread B both go to line 6. Assume that thread A is suspended before data insertion after entering, thread B performs normally and inserts data normally. Then thread A obtains the CPU time slice, and thread A does not need to make hash judgment any more. The problem occurs: Thread A overwrites the data inserted by thread B, causing thread insecurity.

Why is the underlying array length of a HashMap always 2 to the NTH power

We can calculate the bucket position using h % length, which is fine if the length is arbitrary, but if you study it and design a reasonable value, the performance of the HashMap will change dramatically.

First: when length is 2 to the N of the time, h & (length-1) = h % length why & efficiency is higher? Because bitwise operations operate directly on memory data without converting to decimal, bitwise operations are more efficient than modulo operations
Second: when length is 2 to the N power, data distribution is uniform and conflict is reduced

HashMap, ConcurrentHashMap (1.7, 1.8) source code analysis + red-black tree

directory

A HashMap (1.7)

Source code analysis

A constructor

The resize method

The remove method

ConcurrentHashMap (1.7)

Source code analysis

A constructor

Put method

rehash

The size method

The internal structure

attribute

Put method

treeifyBin

AddCount method

tryPresize

conclusion

The source code

Specifies the relationship between the number of CPU cores and the number of Hash buckets allocated by migration tasks

How do multithreading assign tasks?

What are lastRun nodes?

How are access requests handled during and after a Hash bucket migration?

Operation after multithreaded migration task is completed

Extension problem

A HashMap (1.8)

2. HashMap inheritance

4. Low level storage structure

6. What is a hash collision

7.1, attributes,

7.3. Put method

find

replacementTreeNode

comparableClassFor

tieBreakOrder

moveRootToFront

7.4. Resize method

untreeify

7.6. Remove method

root

HashMap difference between JDK1.7 and 1.8

Properties of red-black trees

Right hand

Scenario 1

Scenario 3

The situation of 4.1

Scenario 2

The situation of 4.3

Scene 4.3.2

Handwritten red black tree

What can go wrong with HashMap thread safety

Related Posts