When applying HashMap in a java multi-threaded environment, there are mainly the following options: Use the thread-safe java.util.Hashtable as an alternative. Use the java.util.Collections.synchronizedMap method to wrap the existing HashMap object as thread-safe. Use the java.util.concurrent.ConcurrentHashMap class as an alternative, which has very good performance.
The above methods all use mutex locks more or less in the specific details of implementation. Mutex locks will cause thread blocking, reduce operating efficiency, and may cause a series of problems such as deadlock and priority flipping.
CAS (Compare And Swap) is a function provided by the underlying hardware, which can atomicize the operation of judging and changing a value.
Atomic operations in Java
In the java.util.concurrent.atomic package, Java provides us with many convenient atomic types, which are entirely based on CAS operations.
For example, if we want to implement a global public counter, we can:
Copy the code code as follows:
privateAtomicInteger counter =newAtomicInteger(3);
publicvoidaddCounter() {
for(;;) {
intoldValue = counter.get();
intnewValue = oldValue +1;
if(counter.compareAndSet(oldValue, newValue))
return;
}
}
Among them, the compareAndSet method checks whether the existing value of counter is oldValue. If so, it is set to the new value newValue. The operation is successful and true is returned; otherwise the operation fails and false is returned.
When calculating the new value of counter, if other threads change the value of counter, compareAndSwap will fail. At this point we only need to add a layer of looping outside and keep trying this process, then we will eventually successfully increase the counter value by 1. (In fact, AtomicInteger has already defined the incrementAndGet and decrementAndGet methods for the commonly used +1/-1 operations. We only need to simply call them in the future)
In addition to AtomicInteger, the java.util.concurrent.atomic package also provides AtomicReference and AtomicReferenceArray types, which represent atomic references and atomic reference arrays (arrays of references) respectively.
Implementation of lock-free linked list
Before implementing a lock-free HashMap, let us first take a look at the relatively simple implementation method of a lock-free linked list.
Take the insert operation as an example:
First we need to find the node A in front of the position to be inserted and the node B behind it.
Then create a new node C and make its next pointer point to node B. (See Figure 1)
Finally, make the next pointer of node A point to node C. (See Figure 2)
However, during the operation, it is possible that other threads directly inserted some nodes in A and B (assumed to be D). If we do not make any judgment, it may cause the loss of nodes inserted by other threads. (See Figure 3) We can use the CAS operation to determine whether the next pointer of node A still points to B when assigning a value. If the next pointer of node A changes, retry the entire insertion operation. The approximate code is as follows:
Copy the code code as follows:
privatevoidlistInsert(Node head, Node c) {
for(;;) {
Node a = findInsertionPlace(head), b = a.next.get();
c.next.set(b);
if(a.next.compareAndSwap(b,c))
return;
}
}
(The next field of the Node class is of type AtomicReference<Node>, which is an atomic reference pointing to the Node type)
The search operation of a lock-free linked list is no different from that of an ordinary linked list. The deletion operation requires finding the node A in front of the node to be deleted and the node B behind it, and using the CAS operation to verify and update the next pointer of node A so that it points to node B.
Difficulties and breakthroughs of lock-free HashMap
HashMap mainly has four basic operations: insertion, deletion, search and ReHash. A typical HashMap implementation uses an array, and each element of the array is a linked list of nodes. For this linked list, we can use the operation methods mentioned above to perform insertion, deletion and search operations, but the ReHash operation is more difficult.
As shown in Figure 4, during the ReHash process, a typical operation is to traverse each node in the old table, calculate its position in the new table, and then move it to the new table. During this period we need to manipulate the pointer three times:
Point A's next pointer to D
Point B's next pointer to C
Point C's next pointer to E
These three pointer operations must be completed at the same time to ensure the atomicity of the move operation. But it is not difficult to see that the CAS operation can only ensure that the value of one variable is atomically verified and updated at a time, and cannot meet the need to verify and update three pointers at the same time.
So we might as well change our thinking. Since the operation of moving nodes is so difficult, we can keep all nodes in an ordered state at all times, thus avoiding the moving operation. In a typical HashMap implementation, the length of the array always remains 2i, and the process of mapping the Hash value to the array subscript simply performs a modulo operation on the array length (that is, only the last i bits of the Hash binary are retained). When ReHash, the array length is doubled to 2i+1, and each node in the j-th necklace list of the old array is either moved to the j-th item in the new array, or moved to the j+2i-th item in the new array, and their The only difference lies in the i+1th bit of the Hash value (if the i+1th bit is 0, it is still the jth item, otherwise it is the j+2ith item).
As shown in Figure 5, we arrange all nodes in ascending order according to the inverted order of the Hash value (such as 1101->1011). When the array size is 8, 2 and 18 are in one group; 3, 11 and 27 are in another group. At the beginning of each group, a sentinel node is inserted to facilitate subsequent operations. In order to correctly arrange the sentinel node at the front of the group, we set the highest bit of the normal node Hash (which becomes the lowest bit after flipping) to 1, while the sentinel node does not set this bit.
When the array is expanded to 16 (see Figure 6), the second group is split into a group containing only 3 and a group containing 11 and 27, but the relative order between nodes has not changed. In this way, we do not need to move nodes during ReHash.
Implementation details
Since array copying takes up a lot of time during expansion, here we adopt the method of dividing the entire array into blocks and lazily creating it. In this way, when a certain subscript is accessed, it only needs to be judged whether the block where the subscript is located has been established (if not, then create it).
In addition, size is defined as the currently used subscript range, and its initial value is 2. When the array is expanded, the size only needs to be doubled; count is defined to represent the total number of nodes currently included in the HashMap (not counting sentinel nodes).
Initially, all items in the array except the 0th item are null. Item 0 points to a linked list with only one sentinel node, representing the starting point of the entire chain. The initial full picture is shown in Figure 7, in which the light green represents the currently unused subscript range, and the dotted arrows represent blocks that logically exist but are not actually established.
Initialize subscript operation
Null items in the array are considered to be in an uninitialized state. Initializing a certain subscript means establishing its corresponding sentinel node. Initialization is performed recursively, that is, if its parent subscript is not initialized, its parent subscript is initialized first. (The parent subscript of a subscript is the subscript obtained by removing the highest binary bit.) The approximate code is as follows:
Copy the code code as follows:
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
if(getBucket(parentIdx) ==null)
initializeBucket(parentIdx);
Node dummy =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
Among them, getBucket is an encapsulated method to obtain the content of a certain subscript in the array, and setBucket is the same. listInsert will insert the given node into a suitable position starting from the specified position. If a node with the same hash already exists in the linked list, it will return the existing node; otherwise, it will return the newly inserted node.
insert operation
First, use the size of the HashMap to modulo the hashCode of the key to obtain the array subscript that should be inserted.
Then determine whether the subscript is null, and if it is null, initialize the subscript.
Construct a new node and insert it into the appropriate position. Note that the hash value in the node should be the value of the original hashCode after bit flipping and setting the lowest position to 1.
Add 1 to the node number counter. If there are too many nodes after adding 1, you only need to change the size to size*2, which means expanding the array (ReHash).
Find operation
Find the index of the node to be found in the array.
Determine whether the subscript is null. If it is null, the search failure will be returned.
Enter the linked list from the corresponding position and search sequentially until the node to be found is found or exceeds the range of this group of nodes.
delete operation
Find the index of the node in the array that should be deleted.
Determine whether the subscript is null, and if it is null, initialize the subscript.
Find the node to be deleted and delete it from the linked list. (Note that due to the existence of the sentinel node, any normal element is only referenced by its only predecessor node. There is no situation where it is referenced by the predecessor node and the pointer in the array at the same time, so there is no need to modify multiple pointers at the same time.)
Decrement the node number counter by 1.