HasMap

  • HasMap is based on an array + linked list + red-black tree, which stores k-V key-value pairs
  • HasMap calculates the position in the array by the HasCode of the Key, which is calculated by the remainder of HasCode and the size of the array
  • Since HasMap determines the array position by taking the remainder, it is inevitable that two different keys will compute the same array position, which is called a HAS collision
  • When a Has collision occurs, HasMap puts the new value in the corresponding position in the array and generates a linked list with the new value as the head, with the old value pointing to the new value, known as the header
  • Due to the low efficiency of the random query of the list, in java8, when the length of the list exceeds 8, the list will be converted into a red-black tree to reduce the complexity of the query
  • HasMap defines a threshold LoadFactory to determine whether the HasMap array needs to be expanded. The default value is 0.75 (modifiable).
  • When the length of the HasMap array exceeds the LoadFactory limit, it will be expanded to twice the original length

HasMap is a non-thread-safe data structure, and there are two other options when considering multithreading:

HasTable

The implementation principle of HasTable is the same as that of HasMap. However, the keyword Synchronize is added to the key methods of HasTable (get, put, etc.), resulting in a full lock for each query or modification operation. As long as a thread accesses the HasTable, other threads must wait. Such an implementation makes HasTable very inefficient when multithreaded. HasTable is almost no longer in use.

ConcurrentHashMap

ConcurrentHashMap is an optimized implementation of HasTable. Again, the basic principle is the same as HashMap, but the locking mode is changed. ConcurrentHashMap adds the keyword synchronize to the block of code traversing the list and the red-black tree. It only works when two threads access the same list and red-black tree at the same time. If two threads access different lists, they do not affect each other. Segment locking performance has been greatly improved compared with full locking, and ConcurrentHashMap is generally used in multithreaded.