HashMap | Engineering Interview Kit

TL;DR

HashMap implements the Map interface (stores Key-Value pairs).
It does not maintain any order of its keys or values.
Allows exactly one null key and multiple null values.
Offers $O(1)$ constant-time performance for put and get operations.

Concept

A HashMap is the most widely used Map implementation in Java. It works on the principle of Hashing.

When you insert a (Key, Value) pair, it calculates a hash code for the key. This hash code determines which “bucket” (index in an internal array) the pair will be stored in. When you want to retrieve a value, it calculates the hash of the key again, goes straight to that bucket, and retrieves the value.

Collisions

If two different keys produce the same hash code (a hash collision), they are placed in the same bucket. Prior to Java 8, buckets were simply linked lists. In Java 8, if a bucket gets too large (8 or more items), it converts the linked list into a balanced Tree (Red-Black Tree) to improve worst-case lookup performance from $O(n)$ to $O(\log n)$ .

Examples

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

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> inventory = new HashMap<>();
        
        // Inserting data
        inventory.put("Apples", 50);
        inventory.put("Bananas", 20);
        
        // Null keys and values
        inventory.put(null, 0); 
        inventory.put("Oranges", null);
        
        // Updating data (Keys must be unique, so this overwrites)
        inventory.put("Apples", 100); 
        
        // Retrieving data
        System.out.println("Apple count: " + inventory.get("Apples")); // 100
        
        // Safe retrieval (default value if key doesn't exist)
        System.out.println(inventory.getOrDefault("Grapes", 0)); // 0
    }
}

Interview Questions

Q: What happens if two keys have the same hashCode()?
A: They will be placed in the exact same bucket in the HashMap. This is known as a collision. When calling get(), the HashMap goes to that bucket and then uses the equals() method to iterate through all the entries in that bucket until it finds the exact matching key.

Q: Is HashMap thread-safe?
A: No. If multiple threads modify a HashMap concurrently, the internal structure can become corrupted (historically causing infinite loops during resize operations). Use ConcurrentHashMap for thread-safe operations.