Take it directly? HashMap and ConcurrentHashMap

How to deal with it directly? HashMap and ConcurrentHashMap

https://blog.csdn.net/qq_45643467/article/details/133184856?spm=1001.2014.3001.5501

1HashMap structure (jdk8)

1 HashMap features

Stored unordered.
Both key and value positions can be null, but only one null can exist for a key position.
Key positions are unique and controlled by the underlying data structure.
The data structure before jdk1.8 is linked list + array, and after jdk1.8 it is linked list + array + red-black tree.
Threshold (boundary value) > 8 and the array length is greater than 64, then the linked list will be converted into a red-black tree. The purpose of turning into a red-black tree is for efficient query.
When the value of the linked list is less than 6, it will be converted from the red-black tree back to the linked list
table is used for initialization (must be the n power of two)
Initial size 16, loading factor 0.75 (A compromise value obtained through the Poisson distribution algorithm based on space and time), expansion resize() twice (copy of the array)
h = key.hashCode() ^ (h >>> 16) Makes the hash values of keys in HashMap evenly distributed throughout the array as much as possible, thereby reducing the probability of hash conflicts and improving the performance of HashMap
- key.hashCode(): Get the hash value of the key object;
- h >>> 16: Shift the hash value to the right by 16 bits, which is equivalent to dividing it by 2 raised to the 16th power, that is, compressing it into a smaller range;
- h = key.hashCode() ^ (h >>> 16): Perform an XOR operation on the compressed hash value and the original hash value to obtain the final hash value.

2 Core, put process of HashMap

First calculate which bucket the key is mapped to through the hash value—->Calculate through the tab=[(n – 1) & amp; hash] formula;
If there is no collision conflict on the bucket, insert it directly;
If a collision occurs, the conflict needs to be handled:
- If the bucket uses a red-black tree to handle conflicts, the method of the red-black tree is called to insert data;
- Otherwise, the traditional chain method is used for insertion. If the length of the chain reaches a critical value, the chain is converted into a red-black tree;
If there is a duplicate key in the bucket, replace the key with the new value value;
If size is greater than the threshold, expand the capacity;

3 Why the capacity of HashMap must be converted to an exponential power of 2

In Java, HashMap uses the modulo operation (%) internally to calculate the hash position. After converting to an exponential power of 2, bit operations ( & amp;) can be used to replace the modulo operation, and bit operations are more efficient.

4 How to traverse Map

Traverse Key and Values respectively
Iterate using Iterator
Through get method (not recommended)

According to the Alibaba development manual, this method is not recommended because it is iterated twice. keySet gets the Iterator once, and iterates again through get. Reduced performance

After jdk8, use the default method in the Map interface

default void forEach(BiConsumer<? super K,? super V> action)
Methods in BiConsumer interface:
    void accept?(T t, U u) performs this operation on the given arguments.
        parameters
            t - the first input parameter
            u - the second input parameter
    
public class Demo02 {
    public static void main(String[] args) {
        HashMap<String, String> m1 = new HashMap();
        m1.put("001", "zhangsan");
        m1.put("002", "lisi");
        m1.forEach((key, value)->{
            System.out.println(key + "---" + value);
        });
    }
}

5 The difference between HashMap and HashTable

HashMap and HashTable are both data structures used to store key-value pairs, but there are several key differences between them.

Synchronicity: HashTable is thread-safe, that is, synchronization is automatically performed when multiple threads access concurrently, while HashMap is not thread-safe. If multiple threads access HashMap at the same time, data inconsistency may occur or exceptions may be thrown.
Performance: Since HashTable is thread-safe, its performance in multi-threaded environments is usually lower than HashMap. Because HashTable requires additional overhead to ensure thread safety.
Null: HashMap allows storing null values as keys or values, while HashTable does not. In HashMap, null can be stored as a key or value, but storing null in HashTable will throw NullPointerException.
Inheritance relationship: HashTable is a subclass of the Dictionary class, and HashMap is a subclass of the AbstractMap class. Since the Dictionary class is an old class, it is recommended to use HashMap.
Iterator: The failure of the iterator – fast-fail mechanism: When performing an iterative operation on a HashMap, if other threads modify the structure of the HashMap (add or delete elements), a ConcurrentModificationException exception will occur. HashTable does not have a fast failure mechanism and can be modified concurrently.
Initial capacity and expansion: The default initial capacity of HashTable is 11. When expanding, the capacity becomes twice the original capacity plus one. The default initial capacity of HashMap is 16, and the capacity doubles when expanded. At the same time, HashMap can set the initial capacity and load factor through the constructor

6 ConcurrentHashMap

ConcurrentHashMap, which is a highly concurrent version of HashMap and thread-safe

ConcurrentHashMap consists of Segment array structure and HashEntry array structure;
Segment is a type of ReentrantLock, and HashEntry is used to store key-value pair data;
A ConcurrentHashMap contains an array composed of several Segment objects. Each Segment object guards several buckets of the entire hash map table. Each bucket is linked by several HashEntry objects Linked list, table is an array composed of HashEntry objects. Each array member of the table array is a bucket of the hash map table.

1 JDK1.7

Implemented in the form of array + linked list, ConcurrentHashMap uses lock segmentation technology to ensure thread safety.

Lock segmentation technology: First divide the data into segments for storage, and then assign a lock to each segment of data. When a thread occupies the lock When accessing data in one segment, data in other segments can also be accessed by other threads.
ConcurrentHashMap provides a lock mechanism that is different from Hashtable and SynchronizedMap. The locking mechanism (synchronized) used in Hashtable locks the entire table at one time, so that it can only be operated by one thread at the same time; while ConcurrentHashMap locks one Segment at a time. .
A large array Segment can be understood as a database, and each database (Segment) has many tables (HashEntry), and each HashEntry has many pieces of data. These data are connected using linked lists.
ConcurrentHashMapdivides the array into 16 Segments by default. Common operations such as get, put, remove and other only lock the Segment currently needed. In this way, originally only one thread could enter, but now 16 writing threads can be executed at the same time. The improvement in concurrency performance is obvious [the lock granularity is smaller]. Then locking is achieved by adding a ReentrantLock reentrant lock to Segment (other threads can only acquire the lock after waiting for the current thread to complete execution.)** to achieve thread safety.

2 JDK1.8

After JDK1.8, the method of array + linked list + red-black tree was used to optimize the problem of reduced query efficiency caused by the long linked list of ConcurrentHashMap. The specific implementation method is that the length of the linked list is greater than 8. And when the array length is greater than or equal to 64, the linked list will be upgraded to a red-black tree structure (query efficiency will be higher)

1 How does JDK1.8ConcurrentHashMap achieve thread safety?

In JDK1.8, ConcurrentHashMap uses Node + CAS + Synchronized to achieve thread safety. Specifically, each Node object contains a HashEntry array and a lock object. When multiple threads access the same node, they only need to operate on the HashEntry array on the node without locking the entire node. This improves concurrency.

In order to ensure thread safety, ConcurrentHashMap uses CAS (Compare And Swap) operation to ensure atomicity. Specifically,when multiple threads try to update the same node at the same time, they will first obtain the lock object on the node, and then use the CAS operation to update an element in the HashEntry array on the node to a new one. value. If the update is successful, release the lock object; otherwise try again until the update is successful. This ensures that data inconsistency will not occur when multiple threads update the same node at the same time.

In addition, in order to ensure thread safety, ConcurrentHashMap also uses the Synchronized keyword to lock some key operations. For example, when performing expansion and deletion operations, ConcurrentHashMap will lock the entire hash table to prevent other threads from modifying the data in the hash table at this time.

1 CAS operation

Compare-And-Swap (CAS) method. CAS will only update the variable value when the expected value and the actual value of the variable value are equal, and ensure that no conflicts occur when operating data in multi-threaded situations. In the implementation of CAS, each thread has the opportunity to perform its own operation and verify the correctness of the operation. If the operation is correct, it will proceed to the next step. This implementation method reduces the cost of locks compared to locks and greatly improves the concurrency of the system.

In summary, ConcurrentHashMap’s methods for achieving thread safety mainly include segmented lock design and CAS operations, and through these two methods, the correctness and concurrency efficiency of multi-threaded operations are guaranteed.

2 Introduction to CAS

Three basic operands are used in the CAS mechanism:Memory address V, old expected value A, and new value to be modified B.

When updating a variable, only when the expected value A of the variable is the same as the actual value in memory address V will the value corresponding to memory address V be modified to B.

7 The difference between HashMap and ConcurrentHashMap

1 The basic concepts are different

ConcurrentHashMap is a hash table that supports high concurrent updates and queries. Under the premise of ensuring security, no lock is required for retrieval.
HashMap is an implementation of the Map interface based on hash tables. This implementation provides all optional mapping operations and allows the use of null values and null keys.

2 The underlying data structure is different

The underlying data structure of HashMap is mainly: array + linked list, to be precise, it is an array with linked lists as elements.
The underlying data structure of ConcurrentHashMap is: Segments array + HashEntry array + linked list

3 Different thread safety attributes

ConcurrentHashMap is a thread-safe array that uses segmentation locks to ensure security. There are multiple locks in the container, and each lock locks a piece of data. This way, when multiple threads access different pieces of data, there will be no lock competition, which can effectively improve concurrency efficiency. ConcurrentHashMapmakes the lock granularity finer (not locking the entire array) and has better concurrency performance.
HashMap is not thread-safe and has no lock mechanism. In a multi-threaded environment, it will cause problems such as data overwriting. Therefore, using HashMap in multi-threads will throw an exception.

4 The entire bucket array is processed differently

ConcurrentHashMap segments the entire bucket array
HashMap does not segment the entire bucket array.