HashMap in Java

Introduction

In Java, a HashMap is one of the most widely used data structures. Part of the java.util package, it implements the Map interface and stores data in key-value pairs. It provides an extremely efficient way to store and retrieve values based on their keys.

Unlike a List, where elements are accessed via a numerical index, a HashMap allows access via an arbitrary object (the key).

Internal Working (Pre and Post Java 8)

Understanding how a HashMap works under the hood is crucial for any Java developer, especially in interviews.

The Basics

Internally, a HashMap uses an array of nodes (often called "buckets" or "bins"). Each node is essentially a linked list data structure (specifically, Map.Entry) that holds:

1. The Hash code of the key
2. The Key
3. The Value
4. A reference to the Next node

The put(K key, V value) Operation

1. Hashing: When you call put(), the HashMap calculates the hash code of the key using the key's hashCode() method.
2. Index Calculation: It then applies a bitwise operation to the hash code to determine the bucket (array index) where the entry should be placed.
3. Collision Handling: If two different keys produce the same index (a collision), the entries are stored in a linked list at that bucket.

The Java 8 Improvement (Treeifying)

Before Java 8, severe hash collisions could degrade the HashMap performance from $O(1)$ to $O(n)$ because the linked lists in buckets would grow very long. In Java 8, if a bucket contains more than 8 nodes (and the overall map capacity is at least 64), the linked list is transformed into a Red-Black Tree. This guarantees a worst-case retrieval time of $O(\log n)$ instead of $O(n)$.

Load Factor and Rehashing

A HashMap has two important parameters that dictate its performance:

• Initial Capacity: The number of buckets when the map is created (default is 16).
• Load Factor: A measure of how full the hash table is allowed to get before its capacity is automatically increased. The default is 0.75.

When the number of entries exceeds the product of the capacity and the load factor (e.g., $16 \times 0.75 = 12$), rehashing occurs. The capacity is doubled (to 32), and all existing elements are re-hashed into the new buckets.

Code Example

import java.util.HashMap;
import java.util.Map;

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

        // Adding key-value pairs
        population.put("New York", 8419000);
        population.put("Los Angeles", 3980000);
        population.put("Chicago", 2716000);

        // Retrieving values
        System.out.println("Population of NY: " + population.get("New York"));

        // Checking for a key
        if (population.containsKey("Chicago")) {
            System.out.println("Chicago is in the map.");
        }

        // Iterating over a HashMap
        for (Map.Entry<String, Integer> entry : population.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Key Characteristics

• Null values: Allows one null key and multiple null values.
• Ordering: Makes no guarantees regarding the order of the map. It does not guarantee that the order will remain constant over time.
• Thread Safety: Not synchronized (not thread-safe). If thread safety is required, use ConcurrentHashMap or Collections.synchronizedMap().
• Performance: Provides constant-time performance $O(1)$ for basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Best Practices

1. Always override equals() and hashCode(): If you use custom objects as keys, you must override both methods correctly. If two objects are equal according to equals(), they must have the same hashCode().
2. Specify Initial Capacity: If you know you are going to add a large number of items, initialize the HashMap with an appropriate capacity to avoid the costly rehashing process.