Specific Implementation of Hash Table in Java (HashMap)

Specific Implementation of Hash Table in Java (HashMap)

1. Basic Structure of HashMap
HashMap in Java adopts a combined structure of array + linked list/red-black tree. Each array position is called a "bucket," storing the head node of a linked list or the root node of a red-black tree. When the length of the linked list exceeds 8 and the array length is ≥ 64, the linked list is converted to a red-black tree; when the number of tree nodes is ≤ 6, the red-black tree degenerates into a linked list.

2. Core Parameter Analysis

  1. Initial Capacity (initialCapacity): Default is 16, must be a power of 2.
  2. Load Factor (loadFactor): Default is 0.75, measuring how full the hash table is.
  3. Expansion Threshold (threshold) = Capacity × Load Factor, default is 16 × 0.75 = 12.
  4. TREEIFY_THRESHOLD = 8: Threshold for converting a linked list to a tree.
  5. UNTREEIFY_THRESHOLD = 6: Threshold for converting a tree to a linked list.

3. Detailed Execution Flow of the put Method

  1. Calculate the hash value of the key: Use the hash() method to perform secondary hashing on the key's hashCode to reduce collision probability.
  2. Determine the bucket position: index = (n-1) & hash (where n is the array length).
  3. Traverse elements in the bucket:
    • If the bucket is empty, create a new node and insert it directly.
    • If the bucket is a linked list: Traverse and compare hash and equals; if the same key exists, update the value; otherwise, add a new node using the tail insertion method.
    • If the bucket is a red-black tree: Call the putTreeVal method to insert.
  4. Determine whether expansion is needed: Perform resize() when size exceeds the threshold.

4. Detailed Explanation of the Expansion Mechanism resize()

  1. Create a new array: Capacity is doubled (ensuring it remains a power of 2).
  2. Redistribute elements:
    • Recalculate positions for linked list nodes: New position = Original position or Original position + Old capacity.
    • Redistribute red-black tree nodes using the split method, which may degenerate into a linked list.
  3. Set the new threshold: New capacity × Load factor.

5. Execution Flow of the get Method

  1. Calculate the hash value of the key and the bucket position (same as steps 1-2 in put).
  2. Traverse elements in the bucket:
    • Linked list: Sequentially compare hash and equals.
    • Red-black tree: Call the getTreeNode method for tree search.
  3. Return the value if a matching node is found; otherwise, return null.

6. Thread Safety Issues
HashMap is not thread-safe. In multi-threaded environments, the following issues may occur:

  1. Formation of a circular linked list during expansion (a JDK 1.7 issue).
  2. Data overwriting due to concurrent put operations.
    Solutions: Use ConcurrentHashMap or Collections.synchronizedMap.

7. Key Points for Performance Optimization

  1. Set an appropriate initial capacity to reduce the number of expansions.
  2. Ensure key objects implement standardized hashCode() and equals() methods.
  3. When using custom objects as keys, ensure immutability.

Through this layered implementation, HashMap maintains O(1) time complexity in most scenarios, while also ensuring performance in worst-case scenarios through tree conversion when handling hash collisions.