Vector
The thread-safe version of ArrayList has synchronized all modification methods. It is suitable for scenarios where data consistency requirements are high, read and write operations are relatively balanced, and does not require very high concurrency performance. Since all operations are synchronized, performance is relatively poor in high concurrency environments
Hashtable
The thread-safe version of HashMap has synchronized and synchronized processing for each key method. In a multi-threaded environment, a thread-safe key-value pair storage structure is required, and the read and write frequency of data is relatively balanced. Poor performance under high concurrency and no key or value is allowed
ConcurrentHashMap
1. Data structure
In JDK1.7, the underlying data structure of ConcurrentHashMap consists of multiple segments, which are inherited from ReentrantLock and are essentially a reentrant lock. Each segment manages part of the data independently, which is equivalent to a small hash table. Each Segment contains an array of HashEntry to store key-value pairs. HashEntry is a linked list structure used to resolve hash conflicts, and new key-value pairs will be inserted into the header of the linked list.
In JDK1.8, the underlying data structure of ConcurrentHashMap is a Node array, and the Node node uses a linked list or a red-black tree to resolve hash conflicts. When the length of the linked list is less than or equal to 8, the linked list is used to store data. When the length of the linked list is greater than 8 and the length of the array is greater than 64, the linked list is converted into a red and black tree
2. Reading principle
In JDK1.7, the value and next pointers of HashEntry are declared as volatile types to ensure memory visibility. Different segments can be accessed concurrently, and multiple threads can read data from different segments at the same time.
In JDK1.8, the value and next pointers of the Node node are declared as volatile types to ensure memory visibility. Multiple threads can read elements at different locations at the same time, improving concurrent reading performance
3. Write principle
In JDK1.7, you need to first locate the corresponding Segment according to the hash value of the key, and then obtain the lock of the Segment. After obtaining the lock, find the appropriate location in the HashEntry array of the corresponding Segment and insert the new key-value pair into the header of the linked list.
In JDK1.8, first you need to locate the corresponding Node array index according to the hash value of the key. If this position is empty, use the CAS operation to insert the new node, and the insertion is completed if it is successful. If CAS insertion fails, a hash collision occurs. When a hash conflict occurs, if it is a linked list, the head node of the linked list will be locked, and the linked list will be inserted or updated. If it is a red and black tree, the root node of the red and black tree will be locked, and the red and black tree rules will be inserted or updated.
4. Capacity expansion mechanism
In JDK1.7, when the number of elements in a HashEntry array of a Segment reaches the threshold, the Segment will lock and expand. When scaling, a new larger HashEntry array is created, and the elements in the original array are rehashed and copied to the new array. Different segments can be expanded independently and will not affect the normal operation of other segments.
In JDK1.8, when the number of elements reaches the threshold, the capacity expansion is triggered. First, use the CAS operation to create a larger Node array, then use the CAS operation to update the Node node reference in the array, and then use the synchronized keyword to lock the head node of the Node node or the root node of the red and black tree to perform data migration operations. ConcurrentHashMap uses multi-threaded segmented migration to migrate the original array elements to the new array. Different threads can be responsible for the migration of different segments.
CopyOnWriteArrayList / CopyOnWriteArraySet
CopyOnWriteArrayList is a thread-safe List implementation that allows concurrent read and write operations in a multi-threaded environment. Its core idea is "copy on write", that is, when writing operations are performed, a copy of the original data structure will be created, modified on the copy, and then the copy will be replaced with the original data structure after completion. The role and implementation of CopyOnWriteArraySet and CopyOnWriteArrayList are similar to each other.
When performing a write operation, CopyOnWriteArrayList will first create a copy of the current array and write to the copy. Since operating on a copy, it will not affect the read operation of the original array by other threads, thus ensuring the concurrency between read and write. After completing the write operation to the replica, the reference to the original array will be replaced by a reference to the new replica array through atomic operations. During this replacement process, the array reference is modified using the volatile keyword to ensure that other threads can see the updated array in time. The entire process above uses ReentrantLock lock to ensure that only one thread can write at the same time
ConcurrentLinkedQueue
ConcurrentLinkedQueue is a thread-safe queue based on linked lists, and uses CAS algorithm to achieve lock-free concurrent access. For example, when multiple threads perform dequeuing operations at the same time, each thread can independently try to update the reference of the head node. Through CAS operations, it ensures that only one thread can be updated successfully, thus achieving lock-free concurrent access.
BlockingQueue
BlockingQueue is a blocking queue, and the locking mechanism is used internally to achieve thread safety. When the queue is full, the thread trying to add elements to the queue will be blocked until the queue has space available. When the queue is empty, the thread trying to get elements from the queue will be blocked until the queue has elements to get
Specific reference:/Yee-Q/p/
Synchronous wrapper
Java synchronization wrapper refers to converting non-thread-safe collections into thread-safe collections through the static method of the Collections class, mainly including the following:
- synchronizedList: Convert ordinary List into thread-safe list. By adding synchronization locks to all operations of List, we ensure that only one thread can access the list at the same time, avoiding data inconsistency during concurrent access, such as
List<String> synchronizedList = (new ArrayList<>()); - synchronizedMap: converts ordinary Map into thread-safe mapping. When operating Map, it will be processed synchronously to ensure the operational safety of Map in a multi-threaded environment, such as:
Map<String, Integer> synchronizedMap = (new HashMap<>()); - synchronizedSet: converts ordinary Set into thread-safe collection. Through the synchronization mechanism, we ensure that when multi-threaded access to Set, there will be no concurrency problems in adding, deleting and other operations of elements, such as:
Set<String> synchronizedSet = (new HashSet<>());