DEV Community

Code Green
Code Green

Posted on

Explain internal working of HashMap in Java

Internal Working of HashMap in Java

A HashMap in Java is part of the Java Collections Framework and implements the Map interface. It stores key-value pairs and allows for efficient retrieval based on keys.

Key Components of HashMap

  • Hash Table: The underlying data structure is an array of buckets (or linked lists) where each bucket can store multiple entries.
  • Hash Function: This function computes an index (bucket) for a given key using its hash code.
  • Load Factor: This determines how full the HashMap can get before it needs to resize. The default load factor is 0.75.
  • Threshold: The threshold is calculated as the product of the current capacity and load factor. When the number of entries exceeds this threshold, the HashMap is resized.

How HashMap Works

  1. Storing a Key-Value Pair:
    • The key's hash code is computed using the hashCode() method.
    • The hash code is transformed into an index using a bitwise operation to fit within the bounds of the array size.
    • The key-value pair is stored in the corresponding bucket. If multiple keys hash to the same index (collision), they are stored in a linked list or tree (Java 8 and later).
  2. Retrieving a Value:
    • The key's hash code is computed again to find the corresponding bucket.
    • The linked list or tree at that bucket is searched for the key. If found, the associated value is returned.
  3. Resizing:
    • If the number of entries exceeds the threshold, a new larger array is created (typically double the size).
    • All existing entries are rehashed and redistributed into the new array based on their hash codes.

Example Code

    import java.util.HashMap;

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

            // Adding key-value pairs
            map.put("One", 1);
            map.put("Two", 2);
            map.put("Three", 3);

            // Retrieving a value
            System.out.println("Value for 'Two': " + map.get("Two")); // Output: 2

            // Checking size
            System.out.println("Size of map: " + map.size()); // Output: 3
        }
    }
Enter fullscreen mode Exit fullscreen mode

Conclusion

The internal workings of a HashMap involve hashing keys to determine their storage location, managing collisions, and resizing when necessary. This design allows for average-case constant time complexity for insertion and retrieval operations, making HashMaps a powerful tool for efficient data storage and access in Java applications.

Top comments (0)