Internal Working of Map & HashMap in Java (Interview Ready)

-

🔹 Introduction

In the Java Collections Framework, both Map and HashMap are essential for working with key-value pairs. This blog dives into their internal mechanics, including how objects are stored and retrieved, how collisions are managed, and what improvements Java 8 brought to the table.

1. What is a Map?

A Map<K, V> is a data structure that stores unique keys associated with corresponding values. Common implementations include:

  • HashMap – unordered, allows one null key and multiple null values
  • TreeMap – sorted by keys
  • LinkedHashMap – maintains insertion order

2. How HashMap Works Internally

➡️ Nodes & Buckets

Internally, a HashMap uses an array of Node objects, where each node represents a key-value pair plus a pointer for chaining in case of collisions. 

class Node<K,V> {
  int hash;
  K key;
  V value;
  Node<K,V> next;
}

➡️ Hashing & Index Calculation

  1. Obtains the key’s hashCode().
  2. Applies a secondary hash function for better distribution.
  3. Determines bucket index using bitwise operations (n - 1) & hash.

➡️ Collision Handling

  • Before Java 8: Collisions were handled via linked lists.
  • Since Java 8: Once a bucket list becomes too long, it converts into a balanced tree (e.g., red-black tree) for optimized lookup.

➡️ Resizing

When the number of stored entries exceeds capacity × load factor (default 0.75), the internal array is resized, typically doubled in size, and all entries are rehashed to new buckets.

3. Visual Diagram of HashMap Structure

+-------------------------+
|     bucket array        |
| [0] -> Node A → Node B  |
| [1] -> null             |
| [2] -> Node C (tree if long) |
| [3] -> Node D           |
+-------------------------+

4. Code Example

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

public class MapHashMapInternals {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Java", 1995);
        map.put("Python", 1991);
        map.put("C++", 1983);

        System.out.println("Java released: " + map.get("Java"));
        System.out.println("Map size: " + map.size());
    }
}

5. Why This Matters in Interviews

Topic Explanation
Load Factor & Resizing Displays knowledge of runtime optimizations and memory trade-offs.
Collision Handling Explains how HashMap remains efficient under heavy load.
Treeify Threshold Indicates awareness of Java 8 performance improvements.
Null Values Distinguishes HashMap from older structures like Hashtable.
Thread Safety Highlights that HashMap isn’t synchronized — use ConcurrentHashMap if needed.
Immutability of Keys Ensures consistency in hashing and lookup.

6. Key Takeaways

  • HashMap stores entries using buckets (an array of Nodes), each containing hash, key, value, and next.
  • The bucket index is computed via hashCode(), a hashing function, and bitwise operations.
  • Java 8 introduced tree-based collision handling for better lookup performance.
  • Resizing the bucket array (rehashing) ensures performance balance between memory and speed.

Comments

Post a Comment

Popular posts from this blog

Spring Boot on AWS EC2: Upload to S3 Securely Using IAM Role

-
When running a Spring Boot application on AWS EC2 , the most common security mistake is hardcoding AWS access keys inside application.properties . This is unnecessary and risky. AWS already provides a secure mechanism: IAM Roles attached to EC2 . In this blog, you will learn how to upload and download files to Amazon S3 from Spring Boot running on EC2 without any access keys , using: Spring Profiles AWS SDK v2 Instance Metadata Service (IMDS) IAM Roles Why Access Keys Are a Bad Idea on EC2 Typical S3 setups use: Access key Secret key Region Bucket This works only for local development. It should NOT be used on EC2. Problems with access keys: Stored in config or code (high risk) Might leak through Git, logs, or screenshots Require manual rotation Not needed if app runs on EC2 AWS automatically manages temporary credentials using the EC2 Instance Profile (IAM Role) . Architecture: EC2 → IAM Role → S3 Spring Boot app r...
Read more

Java Streams Intermediate Operations Explained with Examples

-
Image
The Java Stream API lets you process collections in a fluent, declarative style. In this post, we’ll walk through the most useful intermediate operations with simple examples. Note: Examples below use Java 8 compatible collect(Collectors.toList()) . If you’re on Java 16+, you can replace it with toList() . 1) filter() — Select elements by a condition Keeps only elements that match the predicate. List<Integer> list = Arrays.asList(1,2,3,4,5,6,7,8,9,10); List<Integer> res = list.stream() .filter(num -> num % 2 != 0) // keep only odd numbers .collect(Collectors.toList()); System.out.println(res); // [1, 3, 5, 7, 9] 2) map() — Transform each element Applies a function to every element and returns a stream of results. List<String> strs = Arrays.asList("rama", "anjaneya", "krishna"); List<String> upper = strs.stream() .map(String::toUpperCase) .collect(Collectors.toList()); System.o...
Read more

ConcurrentHashMap vs Synchronized HashMap in Java

-
Image
Introduction In multi-threaded Java applications, managing shared data safely and efficiently is crucial. Two common approaches are using Synchronized HashMap (via Collections.synchronizedMap(...) ) and ConcurrentHashMap . While both aim to provide thread-safety, their implementations and performance characteristics differ significantly. This post explores these differences in detail. What is a Synchronized HashMap? Created by wrapping a regular HashMap using: Map<K, V> syncMap = Collections.synchronizedMap(new HashMap<>()); Enforces synchronization at the object level , meaning only one thread can access the map at any time (read or write). Supports null keys and values since it relies on HashMap behavior. Iterators are fail-fast , throwing ConcurrentModificationException if the map is modified while iterating. Simpler implementation, suitable when concurrency is low or performance is not cri...
Read more