HashMap is a part of Java’s Collection Framework and is used to store key-value pairs. It allows for fast access to data using a hashing mechanism.

Key Features of HashMap

  • Allows null values and one null key.
  • Does not maintain any order of elements.
  • Not thread-safe (use ConcurrentHashMap for thread-safety).
  • Provides O(1) average-time complexity for basic operations like put() and get().

Internal Working of HashMap

1. Data Structure

Internally, HashMap uses an array of nodes (buckets) and a Linked List or Balanced Tree for collision resolution:

  • Each node is a key-value pair (Map.Entry).
  • Java 8 introduced TreeNodes to handle high-collision scenarios, turning linked lists into balanced trees for faster performance.

2. Key Components

  • Hash Function: Converts a key into a hash code.
  • Bucket: Array index where the key-value pair is stored.
  • Load Factor: Determines when to resize the map.
  • Threshold: Calculated as capacity * load factor, it triggers rehashing when exceeded.

3. Important Methods

put(K key, V value)

  1. Compute Hash:
    • The hash() method generates a hash code for the key.
    • The hash code is compressed using (n - 1) & hash to find the index (bucket) in the array.
  2. Locate the Bucket:
    • The calculated index determines where to store the key-value pair.
  3. Collision Handling:
    • If multiple keys map to the same bucket (collision), a Linked List or TreeNode (if list length > 8) is used.
  4. Insert Node:
    • If the key already exists, its value is updated.
    • Otherwise, a new node is added.

get(Object key)

  1. Compute Hash:
    • The hash code of the key is computed.
  2. Locate the Bucket:
    • The index is determined using (n - 1) & hash.
  3. Search for Key:
    • Traverses the bucket to find the key. If found, returns the corresponding value.

remove(Object key)

  • Similar to get(), locates the key and removes the entry if it exists.

4. Rehashing

When the number of entries exceeds the threshold, the HashMap resizes itself by:

  1. Doubling the size of the bucket array.
  2. Recomputing the index for existing entries.

HashMap in Java 8 vs Earlier Versions

  1. Before Java 8:
    • Used a Linked List to handle collisions, leading to possible performance degradation (O(n) in worst case).
  2. Since Java 8:
    • Replaces Linked List with a Balanced Tree (O(log n) complexity) if collisions exceed 8 in a single bucket.

Example

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // Adding key-value pairs
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        // Accessing values
        System.out.println("Value for key 'Banana': " + map.get("Banana"));

        // Removing a key
        map.remove("Apple");
        System.out.println("Map after removal: " + map);
    }
}

Key Points to Remember

  • HashMap works on the principle of Hashing.

  • Avoids performance bottlenecks using TreeNodes for high-collision buckets.

  • Ensure the key class overrides hashCode() and equals() correctly for reliable behavior.

  • Not synchronized; use Collections.synchronizedMap() or ConcurrentHashMap in multi-threaded scenarios.