HashMap

05 Jul 2024 . java .

Not thread safe

Before JDK 1.8

Array + LinkedList

  1. HashMap processes key ⇒ hash value.
  2. Use hash value to determine the location where the current element is stored.
  3. If there is an element in the current position, it determines whether the key of the element are the same:
    1. If it is the same, it will be directly covered.
    2. Otherwise it will be resolved through the zipper method.

Zipper Method: Create an Arrayof LinkedList. If you encounter a hash conflict, just add the value to the end of linked list.

After JDK 1.8

  • When the length of the LinkedList > threshold (default is 8), execute the resize() method to expand the array.
  • When the length of the LinkedList ≥ 64, convert to RB Tree to reduce the search time.