Java collection ConcurrentHashMap What is the difference between how to use each method and HashMap through source code analysis?

Table of Contents

Hello friends, today I will analyze the thread-safe hashmap.

The main features of ConcurrentHashMap include:

ConcurrentHashMap example

Let’s take a look at the source code of the size(), containsKey(), and replace() methods.

Okay, let’s continue to look at the replace method. The first thing is to check whether a null pointer exception is thrown, and then call replaceNode(), the base slot, click to take a look, oh oh, let’s analyze it step by step

Hello friends, today I will analyze the thread-safe hashmap

ConcurrentHashMap is a thread-safe hash table implementation in Java. It provides better concurrency performance than HashMap and is especially suitable for use in multi-threaded environments. ConcurrentHashMap supports highly concurrent read operations, and has also been optimized for write operations. Partial concurrent writes can be achieved through segment locks (Segment).

The main features of ConcurrentHashMap include:

Segment lock: ConcurrentHashMap uses segment locks (Segments) internally to control concurrent access. Each Segment is actually a small HashMap, and they are independent of each other, thus reducing the granularity of the lock and improving the degree of concurrency.
Concurrent reading: ConcurrentHashMap allows multiple threads to perform reading operations at the same time without blocking, and ensures that the read data is consistent.
No support for null values: ConcurrentHashMap does not allow storing null keys and null values. This should be noted.

Using ConcurrentHashMap can ensure data consistency under concurrent access by multiple threads and provide better performance. It is often used in scenarios that require high concurrent read and write operations, such as cache implementation in multi-threaded environments.

ConcurrentHashMap Example

public static void main(String[] args) {
        ConcurrentHashMap<Integer, String > map = new ConcurrentHashMap<>();
        map.put(104,"value_4");
        map.put(103,"value_3");
        map.put(101,"value_1");
        map.put(102,"value_2");
        System.out.println("The size of map is:" + map.size());
        System.out.println("--------------------------------------------- ----");
        System.out.println("whether map contains key:104" + map.containsKey(104));
        System.out.println("--------------------------------------------- ----");
        map.replace(104,"new Value_4");
        System.out.println("The value of 104 after map change: " + map.get(104));
    }

Let’s take a look at the source code of the methods size(), containsKey(), and replace()

This method is used to get the current number of key-value pairs in ConcurrentHashMap and returns an integer indicating the size.

First, the sumCount() method (which is a private method) is called to obtain the count value inside ConcurrentHashMap, which may be an estimate.

Ternary expression, judged according to the size of n: if n is less than 0, return 0; if n is greater than 0 and greater than Integer.MAX_VALUE, return Integer.MAX_VALUE; otherwise, cast n to int and return.

The main function is to ensure that the returned size is within the legal range and to handle possible overflow situations. In this way, it is guaranteed that the returned size value is a reasonable integer and no exceptions will occur even in extreme cases.

Inside the containsKey method, the get method is called to determine whether the key exists and returns a Boolean value.

Let’s look at get() again. Hey, what the hell is spread()? spread? diffusion? Click in to take a look

Huo Mingxingwen, translated as

First, it right-shifts the hash value h by 16 bits and XORs the result with the original hash value.

Then, it performs a bitwise AND operation on the XOR result with a HASH_BITS, and finally returns the processed result.

In short, the function of spread() is to increase the randomness of the hash code, reduce hash conflicts, and improve the effect of hashing.

Find the method and click in to see

Node e = this; This line of code assigns the current node to the temporary variable e, indicating that the search starts from the current node.

if (k != null) { Here it is judged whether the incoming key k is non-null, and if it is null, null will be returned directly.

Enter the do-while loop:

do { ... } while ((e = e.next) != null); In the loop, first determine whether the hash value and key value of the current node are equal to the target value, and if they are equal, then Return the current node.

Then point e to the next node via e = e.next, and continue the comparison until a matching node is found or the end of the linked list is traversed (e.next is null).

If no matching node is found after traversing the linked list, null is returned, indicating that the corresponding key-value pair is not found.

In general, the find method searches for a given hash value and key value in a linked list or tree node. If a matching node is found, the node is returned, otherwise null is returned.

Summary: The process of containsKey method is

Node[] tab; Node e, p; int n, eh; K ek; Some local variables are defined here, including the array tab used to store ConcurrentHashMap The node array, and e and p are used for the storage of temporary nodes, n represents the length of the array, eh represents the hash value of the node, and ek represents the key of the node.

int h = spread(key.hashCode()); This line of code calculates the hash value of the incoming key and processes the hash value through the spread method to better display it in the array position.

if ((tab = table) != null & amp; & amp; (n = tab.length) > 0 & amp; & amp; (e = tabAt(tab, (n - 1) & amp; h )) != null) This code first determines whether the array table inside ConcurrentHashMap is not empty, the array length is greater than 0, and there is a node at the position after hash positioning.

Then enter the conditional judgment:

if ((eh = e.hash) == h) If the hash value of the located node is equal to the hash value of the incoming key, continue to determine whether the keys are equal, and return if they are equal. The value of the corresponding node.

else if (eh < 0) If the hash value is less than 0, it means that this is a tree node (red-black tree), and the find method is called to find the corresponding node.

Finally, there is a process of looping through the linked list or tree nodes, comparing the hash value and key value one by one, and returning the corresponding value if a matching node is found.

If none of the above conditions are met, null is returned, indicating that the corresponding key-value pair is not found.

Okay, Let’s continue to look at the replace method. The first thing is to check whether a null pointer exception is thrown, and then call replaceNode(), the base slot, click to take a look, oh oh, let’s analyze it step by step

final V replaceNode(Object key, V value, Object cv) {
        int hash = spread(key.hashCode());
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & amp; hash)) == null)
                break;
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                boolean validated = false;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            validated = true;
                            for (Node<K,V> e = f, pred = null;;) {
                                K ek;
                                if (e.hash == hash & amp; & amp;
                                    ((ek = e.key) == key ||
                                     (ek != null & amp; & amp; key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                        (ev != null & amp; & amp; cv.equals(ev))) {
                                        oldVal = ev;
                                        if (value != null)
                                            e.val = value;
                                        else if (pred != null)
                                            pred.next = e.next;
                                        else
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
                        else if (f instanceof TreeBin) {
                            validated = true;
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> r, p;
                            if ((r = t.root) != null & amp; & amp;
                                (p = r.findTreeNode(hash, key, null)) != null) {
                                V pv = p.val;
                                if (cv == null || cv == pv ||
                                    (pv != null & amp; & amp; cv.equals(pv))) {
                                    oldVal = pv;
                                    if (value != null)
                                        p.val = value;
                                    else if (t.removeTreeNode(p))
                                        setTabAt(tab, i, untreeify(t.first));
                                }
                            }
                        }
                    }
                }
                if (validated) {
                    if (oldVal != null) {
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }

Come up and spread first, followed by an infinite loop. Take a look inside the method body.

Inside the loop body:

First, determine whether the current table is empty, or the length is 0, or there is no node at the calculated index position. If so, jump out of the loop.
If the hash value of the node is MOVED, it means that the expansion operation is in progress, and the helpTransfer method is used to assist in data migration and update the table.
Otherwise, enter the logic of node replacement:
Create a variable oldVal to store the original value, validated indicates whether the validity of the node has been verified.
Use the synchronized keyword to lock the current node to ensure that operations on the node are atomic. (Supports multi-thread concurrent operations to a certain extent)
If the hash value of the node is greater than or equal to 0, it means that it is an ordinary node (non-tree node), then traverse the linked list, find matching key-value pairs, and perform value replacement or deletion operations.
If the node is a tree node (TreeBin), search for matching key-value pairs in the tree and perform value replacement or deletion operations.
Finally, according to the results and conditions of the operation, the corresponding count adjustment, return of the old value and other operations are performed.

Finally, null is returned, indicating that the corresponding key-value pair was not found or the replacement operation was unsuccessful.

In general, this replaceNode method is the core logic for node replacement operations in ConcurrentHashMap, including handling ordinary nodes and tree nodes, ensuring concurrency safety and efficient performance.

(In the future, friends can openly nest if-else in a chain, and the bosses have agreed to use it ）

Okay, let’s see this first. Reading the source code is probably a beautiful thing~

No journey can be achieved without taking small steps

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57518 people are learning the system