HashMap in Java – Internal Working and Hashing Explained

When speed matters, HashMap is Java's go-to data structure. Whether you're caching results, counting frequencies, or building configuration maps, HashMap delivers key-based access with constant-time performance. But under the hood, it’s not magic—just smart engineering with arrays, hashing, and buckets.

This tutorial explores the inner mechanics of HashMap, clarifies how collisions are handled, explains what changed in Java 8+, and offers pro tips for performance.

---

Table of Contents

• What is HashMap in Java?
• Core Syntax and Class Structure
• Internal Working and Hashing Mechanism
• Collision Handling and Resizing
• Performance Benchmarks and Big-O Complexity
• Real-World Use Cases
• Java Version Differences (Java 8–21)
• Functional Programming Support (Java 8+)
• Comparisons: HashMap vs TreeMap vs LinkedHashMap
• Pros and Cons
• Anti-patterns and Common Pitfalls
• Refactoring Legacy Code
• Best Practices
• 📌 What's New in Java [version]?
• Conclusion and Key Takeaways
• FAQ – 10 Expert-Level Questions

What is HashMap in Java?

HashMap is a part of the Java Collections Framework. It implements the Map<K, V> interface and stores data in key-value pairs. It does not maintain any order.

Map<String, String> capitals = new HashMap<>();
capitals.put("India", "New Delhi");
capitals.put("USA", "Washington D.C.");
System.out.println(capitals.get("India")); // Output: New Delhi

Core Syntax and Structure

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // Hash table (array of Node<K, V>)
    transient Node<K,V>[] table;
    ...
}

Internal Working and Hashing Mechanism

Each key-value pair is stored in a Node object in an array, using the hash of the key to determine the index.

Simplified Working

1. Call hashCode() on key
2. Compute index via bit manipulation
3. Store the value in a bucket (linked list or tree)

int hash = key.hashCode();
int index = (n - 1) & hash; // Bitwise optimization instead of modulo

Collisions

• Before Java 8: handled using linked lists
• Java 8+: if collisions exceed 8 in one bucket, it's converted to a balanced binary tree (Red-Black Tree)

Resizing Mechanism

Resizing happens when entries exceed capacity * load factor. Default values:

• Initial capacity: 16
• Load factor: 0.75

if (size >= threshold)
    resize(); // Doubles the capacity

Performance Benchmarks

Operation	Time Complexity	Notes
get/put/remove	O(1) average	O(n) worst case (collisions)
iteration	O(n)	Dependent on keySet/entrySet

Real-World Use Cases

• Database index caching
• Frequency counters
• Configuration maps
• Session management
• Grouping and lookup tables

Java Version Differences

Java 8

• Introduced treeification to address poor performance under heavy collision
• Methods like computeIfAbsent(), getOrDefault(), forEach()

Java 9

• Map.of() factory methods (immutable)

Java 10+

• var keyword for local inference

Java 21

• Performance tuning for hashing and garbage collection

Functional Programming Support

Map<String, Integer> scores = Map.of("Alice", 90, "Bob", 82);

scores.forEach((k, v) -> System.out.println(k + ": " + v));

// Streams
scores.entrySet()
      .stream()
      .filter(e -> e.getValue() > 85)
      .forEach(e -> System.out.println(e.getKey()));

Comparisons

Feature	HashMap	TreeMap	LinkedHashMap
Order	None	Sorted (by key)	Insertion order
Null keys	1 allowed	Not allowed	1 allowed
Performance	O(1)	O(log n)	O(1)

Pros and Cons

✅ Pros

• Fast for lookup and insert
• Easy to use API
• Tree-based fallback improves reliability

❌ Cons

• Not thread-safe
• Unpredictable order
• Complex key hashing needs care

Anti-patterns and Common Pitfalls

❌ Using mutable keys

class Key {
    int id;
    // no hashCode() or equals() overridden
}

Solution: Always override equals() and hashCode() for custom keys.

❌ Modifying Map during iteration

Use Iterator.remove() or ConcurrentHashMap in concurrent scenarios.

Refactoring Legacy Code

Before:

if (!map.containsKey(key)) {
    map.put(key, new ArrayList<>());
}
map.get(key).add(value);

After (Java 8+):

map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

Best Practices

• Set initial capacity when size is known
• Avoid null keys/values in large systems
• Use ConcurrentHashMap in multi-threaded contexts
• Avoid mixing hash-sensitive objects (like arrays) as keys

📌 What's New in Java [version]?

Java 8

• getOrDefault(), forEach(), compute(), merge()
• Tree-based buckets for better performance
• Lambda support

Java 9

• Map.of(), Map.ofEntries()

Java 10

• var keyword simplifies declaration

Java 17

• Continued performance optimization

Java 21

• Further GC efficiency and hashing speed improvements

Conclusion and Key Takeaways

• HashMap offers a balanced mix of speed and flexibility
• Proper hashing and capacity planning ensure optimal use
• Java 8+ features make it more powerful and expressive
• Best for key-value access where order doesn't matter

FAQ – 10 Expert-Level Questions

1. What happens when two keys have the same hashCode?

They go into the same bucket and are checked via equals().

2. How many collisions make a HashMap treeify its bucket?

By default, 8.

3. What’s the difference between get() and getOrDefault()?

get() returns null if absent, getOrDefault() allows specifying a fallback.

4. Is HashMap synchronized?

No. Use Collections.synchronizedMap() or ConcurrentHashMap.

5. Why is initial capacity important?

Improves performance by avoiding unnecessary resizing.

6. Can we store null keys and values?

Yes, one null key and multiple null values are allowed.

7. What’s the Big-O of put/get?

Average O(1), worst O(n) (if all keys hash to the same bucket).

8. Does HashMap preserve insertion order?

No. Use LinkedHashMap for that.

9. How does resizing work?

When size exceeds threshold, capacity doubles and all entries are rehashed.

10. Why override hashCode and equals for custom keys?

Because HashMap uses hashCode to locate the bucket and equals to confirm key match.

---