Maps

🗺️ Java Maps: Your Personal Filing Cabinet

Imagine you have a magical filing cabinet. You write a label on each folder, and inside each folder, you put something special. When you want to find something, you just look at the label—no need to search through everything!

That’s exactly what a Map is in Java. It stores things in key-value pairs. The key is like the label, and the value is what’s inside the folder.

🧠 The Analogy We’ll Use Throughout

Think of a Map like a dictionary. You look up a word (the key), and you find its meaning (the value).

Every Map type we learn is like a special kind of dictionary—some are super fast, some keep things in order, some are safe when many people use them at once.

📚 Map Interface: The Blueprint

Before building any dictionary, we need a plan. The Map interface is that plan. It tells us what every map can do:

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 10);    // Add
ages.get("Alice");        // Find → 10
ages.remove("Alice");     // Delete
ages.containsKey("Bob");  // Check → false

What Every Map Can Do

Key Rule: Each key can appear only once. If you put the same key again, the old value gets replaced!

🚀 HashMap: The Speed Champion

HashMap is the most popular map. It’s like a magic dictionary that finds any word in almost zero time.

How Does It Work? (Simple Version)

Imagine 16 buckets numbered 0 to 15. When you add a key:

1. Java calculates a hash code (a number from the key)
2. It picks a bucket: bucket = hashCode % 16
3. It stores your key-value in that bucket

HashMap<String, String> capitals = new HashMap<>();
capitals.put("France", "Paris");
capitals.put("Japan", "Tokyo");

System.out.println(capitals.get("France"));
// → Paris (found instantly!)

Why Is It So Fast?

Finding something doesn’t mean searching every item. You just:

1. Calculate the hash code of the key
2. Jump directly to the right bucket
3. Pick up your value

It’s like knowing exactly which drawer to open!

graph TD
    A["Key: 'France'"] --> B["Hash Code: 12345"]
    B --> C["Bucket Index: 5"]
    C --> D["Value: 'Paris'"]

⚠️ Important to Know

• Order is NOT guaranteed. Items may appear in random order.
• Allows ONE null key and multiple null values.
• Not safe for multiple threads using it at the same time.

🔍 HashMap Internal Working: Behind the Curtain

Let’s peek inside the magic box. What really happens?

The Bucket Array

HashMap has an array of buckets. Each bucket can hold a linked list (or a tree for many items).

Buckets: [0] → null
         [1] → ("Alice", 25) → null
         [2] → ("Bob", 30) → ("Eve", 22) → null
         [3] → null
         ...

What Happens When Two Keys Land in the Same Bucket?

This is called a collision. The solution? Chain them together like train cars!

graph TD
    B["Bucket 2"] --> N1["#40;Bob, 30#41;"]
    N1 --> N2["#40;Eve, 22#41;"]
    N2 --> N3["null"]

Tree Upgrade (Java 8+)

If one bucket gets too crowded (8+ items), Java converts the linked list to a balanced tree. Finding items stays fast even with collisions.

Resizing: When the Map Gets Full

When 75% of buckets are used (the load factor), HashMap doubles its size and rehashes everything.

This keeps lookups fast!

🔗 LinkedHashMap: Order Keeper

What if you want speed AND you want items to stay in the order you added them?

LinkedHashMap is your answer. It works like HashMap but keeps a double-linked list connecting all entries.

LinkedHashMap<String, Integer> scores = new LinkedHashMap<>();
scores.put("Math", 95);
scores.put("Science", 88);
scores.put("English", 92);

for (String subject : scores.keySet()) {
    System.out.println(subject);
}
// Output (in insertion order):
// Math
// Science
// English

How It Remembers Order

Each entry has two extra pointers: before and after. They form a chain in the order you added items.

graph LR
    A["Math"] --> B["Science"]
    B --> C["English"]

Access Order Mode

You can also make it remember access order (most recently used last):

LinkedHashMap<String, String> cache =
    new LinkedHashMap<>(16, 0.75f, true);
// true = access order mode

This is perfect for building LRU caches (Least Recently Used)!

🌳 TreeMap: The Sorted Dictionary

What if you need your dictionary sorted alphabetically (or by some other order)?

TreeMap keeps keys in sorted order automatically!

TreeMap<String, Integer> fruits = new TreeMap<>();
fruits.put("Banana", 3);
fruits.put("Apple", 5);
fruits.put("Cherry", 2);

for (String fruit : fruits.keySet()) {
    System.out.println(fruit);
}
// Output (sorted!):
// Apple
// Banana
// Cherry

How Does It Sort?

TreeMap uses a Red-Black Tree (a self-balancing tree). Every time you add something, it finds the right spot to keep everything sorted.

graph TD
    B["Banana"] --> A["Apple"]
    B --> C["Cherry"]

Speed Trade-off

TreeMap is a bit slower, but sorting is automatic!

🧭 SortedMap and NavigableMap: Extra Powers

SortedMap Interface

TreeMap implements SortedMap, which adds special methods:

SortedMap<Integer, String> ranks = new TreeMap<>();
ranks.put(1, "Gold");
ranks.put(2, "Silver");
ranks.put(3, "Bronze");

ranks.firstKey();     // → 1
ranks.lastKey();      // → 3
ranks.headMap(2);     // → {1=Gold}
ranks.tailMap(2);     // → {2=Silver, 3=Bronze}

NavigableMap Interface (Even More Powers!)

NavigableMap extends SortedMap with navigation methods:

NavigableMap<Integer, String> nav = new TreeMap<>();
nav.put(10, "Ten");
nav.put(20, "Twenty");
nav.put(30, "Thirty");

nav.lowerKey(20);     // → 10 (strictly less)
nav.floorKey(20);     // → 20 (less or equal)
nav.higherKey(20);    // → 30 (strictly greater)
nav.ceilingKey(25);   // → 30 (greater or equal)
nav.descendingMap();  // → {30=Thirty, 20=Twenty, 10=Ten}

Think of it as a GPS for your map—you can go forward, backward, and find nearby keys!

🛡️ ConcurrentHashMap: The Team Player

Imagine many people trying to edit the same dictionary at once. Regular HashMap would get confused and break!

ConcurrentHashMap is designed for multi-threaded programs. Many threads can read and write safely.

ConcurrentHashMap<String, Integer> votes =
    new ConcurrentHashMap<>();

// Thread 1
votes.put("Pizza", 10);

// Thread 2 (at the same time!)
votes.put("Burger", 8);

// Both work safely!

How It Stays Safe

Instead of locking the whole map, it uses segment-level locking (or in newer Java, bucket-level locking). Different threads can work on different parts at the same time!

graph TD
    A["Thread 1: Writes to Bucket 3"] --> M["ConcurrentHashMap"]
    B["Thread 2: Writes to Bucket 7"] --> M
    C["Thread 3: Reads Bucket 3"] --> M

Key Differences from HashMap

Atomic Operations

ConcurrentHashMap has special methods that do read-modify-write in one step:

// Add 1 to current value (thread-safe!)
votes.compute("Pizza", (k, v) -> v == null ? 1 : v + 1);

// Only put if key is absent
votes.putIfAbsent("Sushi", 5);

🎯 Quick Summary: Which Map When?

🌟 You Made It!

You now understand the entire Map family in Java:

1. ✅ Map Interface – The blueprint for all maps
2. ✅ HashMap – The speed champion
3. ✅ HashMap Internals – Buckets, hashing, collisions, resizing
4. ✅ LinkedHashMap – Keeps insertion order
5. ✅ TreeMap – Always sorted
6. ✅ SortedMap & NavigableMap – Extra navigation powers
7. ✅ ConcurrentHashMap – Safe for multi-threading

You’re ready to use Maps like a pro! 🎉

Remember: A Map is just a filing cabinet with labels. Pick the right cabinet for your needs, and coding becomes easy!