Java Working of HashMap

A HashMap in Java is implemented as a hash table data structure, which is designed for efficient retrieval and storage of key-value pairs. Here’s how a HashMap works:

1. Hashing:

• When you add a key-value pair to a HashMap using the put(key, value) method, the HashMap uses the key’s hash code to determine where in the hash table the value should be stored.
• The hash code of the key is computed using the hashCode() method of the key object.

1. Index Calculation:

• The hash code is then processed further to calculate an index in the array where the value should be stored. This index is calculated by taking the hash code modulo the current capacity of the hash table.
• The result is an array index where the key-value pair will be stored.

1. Collision Handling:

• Since multiple keys can have the same hash code (collisions), HashMap uses a linked list to store key-value pairs at each index in the array.
• If two or more keys have the same index due to hash code collisions, their key-value pairs are stored in a linked list at that index.

1. Retrieval:

• When you want to retrieve a value associated with a specific key using the get(key) method, the HashMap calculates the index for that key using the same hash code computation.
• It then looks through the linked list at that index (if it exists) to find the key-value pair with the matching key.

1. Resizing:

• A HashMap has an initial capacity, and as you add more elements, it keeps track of the number of key-value pairs stored in it. When the number of key-value pairs exceeds a certain threshold (called the load factor), the HashMap is resized (the capacity is increased), and all the key-value pairs are rehashed and redistributed to new indices.
• This resizing process is performed to maintain a low average chain length (i.e., to avoid long linked lists), which ensures efficient retrieval times.

1. Null Keys and Values:

• A HashMap can store one null key and multiple null values. The null key is usually stored at index 0.

1. Iterating Over Entries:

• You can iterate over the entries in a HashMap using the entrySet() method, which returns a set of key-value pairs (entries).

The efficiency of HashMap is attributed to its ability to distribute key-value pairs across different indices using a hash code and handle collisions efficiently by storing multiple pairs in linked lists. When used correctly, it provides fast O(1) average-case time complexity for basic operations like put() and get().

Here’s a simplified example of how a HashMap works:

// Creating a HashMap
HashMap<String, Integer> ages = new HashMap<>();

// Adding key-value pairs
ages.put("Alice", 25);  // Key: "Alice", Value: 25
ages.put("Bob", 30);    // Key: "Bob", Value: 30
ages.put("Charlie", 35); // Key: "Charlie", Value: 35

// Retrieving a value
int aliceAge = ages.get("Alice"); // Retrieves the value associated with the key "Alice" (25)

This example demonstrates the basic usage of a HashMap, where keys are used to calculate indices in the hash table for efficient retrieval of associated values.