Wish you all become stronger ~

  • ConcurrentHashMap source code parsing _01 member attributes, inner classes, constructor analysis
  • ConcurrentHashMap source code parsing _02 preheat (internal some small methods analysis)
  • ConcurrentHashMap source parsing _03 PUT method source analysis
  • Transfer method source code analysis (difficult)
  • ConcurrentHashMap source code parsing _05 Get and remove methods
  • ConcurrentHashMap (TreeBin)

ConcurrentHashMap a brief summary of concurrent hashmaps in the complete section

Conclusion:

(1) ConcurrentHashMap is a thread-safe version of HashMap;

(2) ConcurrentHashMap uses the structure of array + linked list + red-black tree to store elements;

(3) ConcurrentHashMap is much more efficient than thread-safe HashTable;

(4) ConcurrentHashMap adopts synchronized, CAS, spin lock, segmental lock, volatile, etc.

(5) There are no threshold and loadFactor fields in ConcurrentHashMap, but sizeCtl is used to control.

SizeCtl = -1, indicating that initialization is in progress.

SizeCtl = 0, default value, indicating that the default size will be used in subsequent real initialization.

(8) sizeCtl > 0: Incoming capacity is stored before initialization, and threshold of next expansion is stored after initialization or expansion;

SizeCtl = (resizeStamp << 16) + (1 + nThreads), indicating that capacity expansion is in progress.

(10) If capacity expansion is in progress during the update operation, the current thread assists capacity expansion;

(11) The update operation adopts synchronized to lock the first element of the current bucket, which is the idea of segmental locking;

(12) CAS controls the sizeCtl field in the entire capacity expansion process, which is critical;

(13) A ForwardingNode node will be placed to mark the bucket migration completion.

(14) The storage of the number of elements is also segmented, similar to the implementation of LongAdder;

(15) Updating the number of elements will hash different threads into different segments, reducing resource contention;

If multiple threads update a segment at the same time, the segment (CounterCell) will be expanded;

The number of elements is obtained by adding all segments (including baseCount and CounterCell);

(18) Query operations are not locked, so ConcurrentHashMap is not strongly consistent;

ConcurrentHashMap cannot store elements whose key or value is NULL.

  • What are some techniques worth learning from ConcurrentHashMap?

    • (1) CAS + spin, the idea of optimistic locking, reduce the time of thread context switch;
    • (2) The idea of segmental lock can reduce the low efficiency caused by the contention of the same lock;
    • (3) CounterCell: stores the number of elements in segments to reduce the inefficiency caused by multi-threading updating a field at the same time;
    • (4)@sun.misc.Contended(Comments on CounterCell) to avoid pseudo-sharing;
    • (5) Multi-threaded cooperation for capacity expansion;