Map #

You have a list of products and their prices. You want to look up a price by product name. With List, you’d have to traverse all elements one by one until you find it — O(n). With Map, you just give the key and get the value immediately — O(1). That’s the power of Map: a data structure that stores key-value pairs and allows direct key-based lookup without iteration. This article covers the five Map implementations in Java, the available operations, how each works internally, and a guide to choosing the right one for your situation.

Map Overview #

Map is an interface in the Java Collections Framework. Unlike List, which accesses elements by numeric index, Map accesses values by a key you define yourself — it can be a String, Integer, or any object that implements equals() and hashCode().

Three basic Map rules to always remember:

Rule	Description
Keys are unique	Each key can exist only once. `put("A", 2)` over `put("A", 1)` overwrites the old value.
Values can be duplicated	Two different keys may have the same value.
One key, one value	Each key maps to exactly one value.

flowchart TD
    A["«interface»\nMap‹K,V›"] --> B["HashMap"]
    A --> C["LinkedHashMap"]
    A --> D["TreeMap"]
    A --> E["Hashtable"]
    A --> F["ConcurrentHashMap"]
    B --> C

Implementation	Order	Thread-Safe	Allows null key	Complexity
`HashMap`	Not guaranteed	✗	✓ (one)	O(1)
`LinkedHashMap`	Insertion order	✗	✓ (one)	O(1)
`TreeMap`	Key order	✗	✗	O(log n)
`Hashtable`	Not guaranteed	✓	✗	O(1)
`ConcurrentHashMap`	Not guaranteed	✓	✗	O(1)

Like List, declare variables with the interface type: Map<String, Integer> map = new HashMap<>(), not HashMap<String, Integer> map = new HashMap<>(). This makes it easy to swap implementations later without changing the code that uses it.

HashMap #

HashMap is the most commonly used Map implementation. Behind the scenes, it uses a hash table — each key is converted into a hash number that determines which slot the value is stored in. The result: get and put operations run in O(1) on average, no matter how large the map is.

The consequence is ordering. Because element placement is determined by hash, not insertion order, you can’t rely on any particular order when iterating a HashMap.

flowchart LR
    subgraph "Hash Table"
        direction TB
        S0["slot 0"]
        S1["slot 1: 'B'→2"]
        S2["slot 2"]
        S3["slot 3: 'A'→1"]
        S4["slot 4: 'C'→3"]
    end
    K1["'A'"] -->|"hash('A')=3"| S3
    K2["'B'"] -->|"hash('B')=1"| S1
    K3["'C'"] -->|"hash('C')=4"| S4

Creating and Filling #

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

Map<String, Integer> stock = new HashMap<>();

// put: add or overwrite a key-value pair — O(1)
stock.put("Apple", 100);
stock.put("Mango", 50);
stock.put("Orange", 75);

// put with an existing key: the old value is overwritten, the old value is returned
Integer oldStock = stock.put("Apple", 120); // oldStock = 100, stock["Apple"] is now 120

// putIfAbsent: only fills if the key doesn't exist
stock.putIfAbsent("Banana", 30);  // succeeds: "Banana" doesn't exist yet
stock.putIfAbsent("Apple", 999);   // ignored: "Apple" exists, its value stays 120

// Creating a HashMap at once from another Map
Map<String, Integer> copy = new HashMap<>(stock);

Reading and Searching #

// get: retrieve the value by key — O(1)
Integer appleCount = stock.get("Apple");    // 120
Integer missing   = stock.get("Durian");  // null (key not found)

// ANTI-PATTERN: unboxing the get result directly without a null check
int count = stock.get("Durian"); // ✗ NullPointerException!

// CORRECT: use getOrDefault for a fallback value
int safeCount = stock.getOrDefault("Durian", 0); // ✓ 0 if absent

// Check key and value existence — O(1)
boolean hasApple   = stock.containsKey("Apple");    // true
boolean hasValue50 = stock.containsValue(50);     // true

// Size and emptiness checks
int total = stock.size();     // 4
boolean empty = stock.isEmpty(); // false

Modifying and Removing #

// replace: overwrite the value only if the key exists
stock.replace("Apple", 200);         // succeeds: the key exists
stock.replace("Durian", 10);        // ignored: the key doesn't exist

// replace with old-value verification (conditional replace)
stock.replace("Apple", 200, 250);    // succeeds only if the current value is 200

// compute: calculate a new value based on the old one
stock.compute("Apple", (k, v) -> v == null ? 1 : v + 10); // adds 10 to Apple's stock

// merge: combine values with custom logic
stock.merge("Mango", 20, Integer::sum); // Mango's stock += 20

// remove by key — O(1)
stock.remove("Orange");

// conditional remove: only removes if the value matches
stock.remove("Mango", 70); // removes only if stock["Mango"] == 70

// Remove everything
stock.clear();

Iteration #

Map<String, Integer> scores = new HashMap<>();
scores.put("Math", 85);
scores.put("Physics", 90);
scores.put("Chemistry", 78);

// Iterate entries (key and value together) — most common
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Iterate keys only
for (String subject : scores.keySet()) {
    System.out.println(subject);
}

// Iterate values only
for (int n : scores.values()) {
    System.out.println(n);
}

// forEach with a lambda (Java 8+) — the most concise
scores.forEach((k, v) -> System.out.println(k + " → " + v));

LinkedHashMap #

LinkedHashMap is a subclass of HashMap that adds one extra guarantee: insertion order is always preserved. Behind the scenes, every node in the hash table is also connected via a doubly linked list that records the order elements came in. This makes it slightly slower and more memory-hungry than HashMap, but very useful when order matters.

flowchart LR
    subgraph "Hash Table + Linked List"
        direction LR
        A["'A'→1"] -->|"insert order"| B["'B'→2"] -->|"insert order"| C["'C'→3"]
    end

Insertion Order #

import java.util.LinkedHashMap;
import java.util.Map;

Map<String, Integer> steps = new LinkedHashMap<>();
steps.put("First", 1);
steps.put("Second", 2);
steps.put("Third", 3);
steps.put("Fourth", 4);

// Iteration is ALWAYS in insertion order — unlike HashMap
steps.forEach((k, v) -> System.out.println(v + ". " + k));
// Output (always in order):
// 1. First
// 2. Second
// 3. Third
// 4. Fourth

// Compare with HashMap — order is not guaranteed:
Map<String, Integer> shuffled = new HashMap<>(steps);
shuffled.forEach((k, v) -> System.out.println(v + ". " + k));
// Output can be in any order

Access Mode (LRU Cache) #

LinkedHashMap has a special constructor that changes the ordering mode from “insertion order” to “access order”. The least recently accessed element sits at the front. This is the foundation for building an LRU Cache (Least Recently Used) — a cache that automatically evicts the oldest elements when full.

// accessOrder = true: ordering by last access, not insertion
int capacity = 3;
Map<String, String> lruCache = new LinkedHashMap<>(capacity, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > capacity; // automatically evicts the oldest element when over capacity
    }
};

lruCache.put("A", "Data A");
lruCache.put("B", "Data B");
lruCache.put("C", "Data C");
// cache: [A, B, C]

lruCache.get("A"); // access A — A moves to the back (most recently accessed)
// internal order: [B, C, A]

lruCache.put("D", "Data D"); // cache is full, B (least recently accessed) is evicted
// cache: [C, A, D]

System.out.println(lruCache.containsKey("B")); // false — already evicted
System.out.println(lruCache.containsKey("A")); // true — still there

TreeMap #

TreeMap uses a Red-Black Tree — a binary tree that balances itself automatically. Every key is stored in sorted order (ascending by default), and all operations run in O(log n). It’s slower than HashMap, but TreeMap has capabilities no other implementation has: navigation by key ranges.

flowchart TD
    subgraph "Red-Black Tree"
        B["'B'→2"]
        A["'A'→1"] 
        C["'C'→3"]
        B --> A
        B --> C
    end

Automatic Key Ordering #

import java.util.TreeMap;
import java.util.Map;

Map<String, Integer> rankings = new TreeMap<>();

// Add in random order
rankings.put("Budi", 85);
rankings.put("Ani", 92);
rankings.put("Citra", 78);
rankings.put("Doni", 88);

// Iteration is ALWAYS in key order (alphabetical for String)
rankings.forEach((name, score) -> System.out.println(name + ": " + score));
// Output (always alphabetical):
// Ani: 92
// Budi: 85
// Citra: 78
// Doni: 88

// ANTI-PATTERN: putting null as a key
// rankings.put(null, 100); // ✗ NullPointerException — TreeMap doesn't accept null keys

Custom Ordering with a Comparator #

If the natural order doesn’t fit, you can supply your own Comparator to the TreeMap constructor.

import java.util.Comparator;

// Sort by string length, then alphabetically if equal length
Map<String, Integer> custom = new TreeMap<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())
);

custom.put("Banana", 3);
custom.put("Apple", 1);
custom.put("Mango", 2);
custom.put("Kiwi", 4);

custom.forEach((k, v) -> System.out.println(k + ": " + v));
// Output (sorted from shortest name):
// Kiwi: 4
// Apple: 1
// Banana: 3
// Mango: 2

This is an exclusive TreeMap feature not available in other implementations. You can grab sub-maps, the highest/lowest keys, or the closest keys to a value.

import java.util.TreeMap;

TreeMap<Integer, String> schedule = new TreeMap<>();
schedule.put(8, "Breakfast");
schedule.put(12, "Lunch");
schedule.put(15, "Snack");
schedule.put(19, "Dinner");
schedule.put(22, "Sleep");

// First and last keys
System.out.println(schedule.firstKey()); // 8
System.out.println(schedule.lastKey());  // 22

// Closest keys below and above a value
System.out.println(schedule.floorKey(14));   // 12 (≤ 14)
System.out.println(schedule.ceilingKey(14)); // 15 (≥ 14)
System.out.println(schedule.lowerKey(15));   // 12 (< 15, exclusive)
System.out.println(schedule.higherKey(15));  // 19 (> 15, exclusive)

// Sub-map by key range
Map<Integer, String> dayAndNight = schedule.subMap(12, true, 19, true);
// {12=Lunch, 15=Snack, 19=Dinner}

Map<Integer, String> morning = schedule.headMap(12, false); // < 12
// {8=Breakfast}

Map<Integer, String> evening = schedule.tailMap(19, true); // ≥ 19
// {19=Dinner, 22=Sleep}

Hashtable #

Hashtable is the first Map implementation in Java — it’s existed since Java 1.0, even before the Collections Framework was born. Its structure is similar to HashMap: a hash table with synchronization. The differences: all its methods are synchronized, and none of them accept null as a key or value.

Basic Operations #

import java.util.Hashtable;
import java.util.Map;

Map<String, Integer> table = new Hashtable<>();
table.put("One", 1);
table.put("Two", 2);
table.put("Three", 3);

int value = table.get("One"); // 1
table.remove("Two");
System.out.println(table.size()); // 2

// ANTI-PATTERN: putting null as a key or value
// table.put(null, 1);    // ✗ NullPointerException
// table.put("A", null);  // ✗ NullPointerException

Why It’s Not Recommended for New Code #

Hashtable and Vector share the same problem: coarse method-level synchronization. Every operation locks the entire table, even when only one thread is active. This becomes a serious bottleneck in applications with many threads.

For new code, use HashMap if single-threaded, or ConcurrentHashMap if you need thread safety. Hashtable still exists in Java for backward compatibility — not because it’s a good choice.

ConcurrentHashMap #

ConcurrentHashMap is the modern answer for thread-safe Map needs. Unlike Hashtable, which locks the whole table, ConcurrentHashMap uses segmentation (or node-level locking in Java 8+) — only a small part of the table is locked during write operations, so other threads can still read and write other parts simultaneously.

flowchart LR
    subgraph "ConcurrentHashMap — Node-Level Locking"
        direction LR
        N1["node A\n🔒 Thread 1 writing"]
        N2["node B\n✓ Thread 2 can access"]
        N3["node C\n✓ Thread 3 can access"]
    end

Basic Operations #

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

Map<String, Integer> counter = new ConcurrentHashMap<>();
counter.put("home", 0);
counter.put("about", 0);
counter.put("contact", 0);

// Read/write operations are safe from any thread without explicit locking
counter.put("home", 150);
int visits = counter.get("home"); // 150

// ANTI-PATTERN: putting null as a key or value
// counter.put(null, 1);    // ✗ NullPointerException
// counter.put("A", null);  // ✗ NullPointerException

Atomic Operations #

ConcurrentHashMap provides several methods that run atomically — meaning they can’t be interrupted by another thread mid-execution, without you needing extra manual locking.

// Atomic putIfAbsent: adds only if the key doesn't exist
counter.putIfAbsent("register", 0); // safe from race conditions

// Atomic compute: update the value based on the previous one
// Scenario: counting page visits from many threads at once
counter.compute("home", (k, v) -> v == null ? 1 : v + 1);

// Atomic merge: combine old and new values
counter.merge("home", 1, Integer::sum); // adds 1 to the existing value

// computeIfAbsent: compute and fill the value only if the key doesn't exist
counter.computeIfAbsent("new-page", k -> calculateInitialValue(k));

// computeIfPresent: update only if the key already exists
counter.computeIfPresent("home", (k, v) -> v + 100);

Real Example: Counting Frequency from Many Threads #

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

ConcurrentHashMap<String, Integer> frequency = new ConcurrentHashMap<>();
String[] words = {"java", "map", "java", "list", "map", "java"};

ExecutorService pool = Executors.newFixedThreadPool(3);

for (String w : words) {
    pool.submit(() -> {
        // merge is atomic: safe to run from many threads at once
        frequency.merge(w, 1, Integer::sum);
    });
}

pool.shutdown();
pool.awaitTermination(5, TimeUnit.SECONDS);

frequency.forEach((k, v) -> System.out.println(k + ": " + v));
// Output (unordered, but the values are accurate):
// java: 3
// map: 2
// list: 1

Common Operations Across Implementations #

All Map implementations share the same basic operations because they implement the same interface. Here are patterns frequently used in real code.

Default Values and Lazy Computation #

Map<String, List<String>> groups = new HashMap<>();

// ANTI-PATTERN: manual check before filling
if (!groups.containsKey("Admin")) {
    groups.put("Admin", new ArrayList<>());
}
groups.get("Admin").add("Budi"); // wordy

// CORRECT: computeIfAbsent — create a new value only if it doesn't exist
groups.computeIfAbsent("Admin", k -> new ArrayList<>()).add("Budi");
groups.computeIfAbsent("Admin", k -> new ArrayList<>()).add("Ani"); // the same list
groups.computeIfAbsent("User", k -> new ArrayList<>()).add("Citra");

System.out.println(groups.get("Admin")); // [Budi, Ani]
System.out.println(groups.get("User"));  // [Citra]

Collecting Data into a Map with Streams #

import java.util.stream.Collectors;
import java.util.List;

record Student(String name, String major, double gpa) {}

List<Student> students = List.of(
    new Student("Budi", "Informatics", 3.8),
    new Student("Ani", "Informatics", 3.5),
    new Student("Citra", "Mathematics", 3.9),
    new Student("Doni", "Mathematics", 3.2)
);

// Create a Map of name → gpa
Map<String, Double> gpaMap = students.stream()
    .collect(Collectors.toMap(Student::name, Student::gpa));

// Group by major
Map<String, List<Student>> byMajor = students.stream()
    .collect(Collectors.groupingBy(Student::major));

// Calculate the average gpa per major
Map<String, Double> avgGpa = students.stream()
    .collect(Collectors.groupingBy(
        Student::major,
        Collectors.averagingDouble(Student::gpa)
    ));

avgGpa.forEach((major, avg) ->
    System.out.printf("%s: %.2f%n", major, avg)
);

Converting Map to List and Vice Versa #

Map<String, Integer> prices = new HashMap<>();
prices.put("Apple", 5000);
prices.put("Mango", 8000);
prices.put("Orange", 4000);

// Map → List of keys
List<String> itemNames = new ArrayList<>(prices.keySet());

// Map → List of values
List<Integer> priceList = new ArrayList<>(prices.values());

// Map → List of entries, then sort by value
List<Map.Entry<String, Integer>> entries = new ArrayList<>(prices.entrySet());
entries.sort(Map.Entry.comparingByValue());
entries.forEach(e -> System.out.println(e.getKey() + ": Rp" + e.getValue()));
// Output (sorted from cheapest):
// Orange: Rp4000
// Apple: Rp5000
// Mango: Rp8000

Performance Comparison #

Operation	HashMap	LinkedHashMap	TreeMap
`get(key)`	O(1)	O(1)	O(log n)
`put(key, val)`	O(1)	O(1)	O(log n)
`remove(key)`	O(1)	O(1)	O(log n)
`containsKey(key)`	O(1)	O(1)	O(log n)
Iteration	O(n)	O(n)	O(n)
Key ranges (`subMap`)	✗ Not available	✗ Not available	✓ O(log n)
Memory overhead	Low	Medium (linked list)	Medium (tree pointers)

Decision Tree for Choosing an Implementation #

flowchart TD
    A{Need\nthread safety?} -- Yes --> B{Many concurrent\nread operations?}
    B -- Yes --> C[ConcurrentHashMap]
    B -- No --> D["Hashtable\n(not recommended for new code)"]
    A -- No --> E{Need\nkey order?}
    E -- "Insertion order" --> F[LinkedHashMap]
    E -- "Key order (sorted)" --> G[TreeMap]
    E -- "No order needed" --> H[HashMap]
    G --> I{Need key\nrange navigation?}
    I -- Yes --> J["TreeMap with\nfloorKey/ceilingKey/subMap"]
    I -- No --> G

When to Use Each Implementation #

Use HASHMAP when:
  ✓ It's the default choice — use it unless there's a specific need
  ✓ O(1) performance for get/put/remove is a priority
  ✓ Element order doesn't matter
  ✓ You don't need thread safety

Use LINKEDHASHMAP when:
  ✓ You need insertion order preserved (e.g., process steps, form fields)
  ✓ Building an LRU cache with access-order mode
  ✓ Output must be consistent and predictably ordered

Use TREEMAP when:
  ✓ Keys must always be sorted (alphabetical, numeric, custom)
  ✓ You need key-range navigation (floorKey, ceilingKey, subMap)
  ✓ Building structures like calendars, schedules, or price ranges

Use HASHTABLE when:
  ✗ There's almost no reason for new code
  ✓ Only when you must interact with legacy APIs that require it

Use CONCURRENTHASHMAP when:
  ✓ Many threads read and write simultaneously
  ✓ You need atomic operations like compute, merge, putIfAbsent without manual locks
  ✗ Avoid it if you're single-threaded — the overhead isn't worth it

Summary #

Map stores key-value pairs — keys must be unique, values may be duplicated. Key-based lookup runs in O(1) for hash-based implementations.
HashMap is the default choice — unordered, O(1) for all basic operations, allows one null key. Pick this unless there’s a specific need otherwise.
LinkedHashMap guarantees insertion order — a HashMap subclass that adds an internal doubly linked list. It can also be configured to access-order to build an LRU cache.
TreeMap is always sorted by key — Red-Black Tree based, O(log n) for all operations. Has exclusive navigation APIs: floorKey, ceilingKey, subMap, headMap, tailMap.
Hashtable is a legacy leftover — thread-safe but coarse, doesn’t accept null. Use ConcurrentHashMap as its replacement in new code.
ConcurrentHashMap for modern multithreading — node-level locking instead of locking the whole table. Provides atomic compute, merge, putIfAbsent operations safe from race conditions without manual locks.
Use getOrDefault instead of raw get — get returns null if the key is missing. Unboxing null into an int immediately causes NullPointerException.
computeIfAbsent for values needing initialization — the pattern if (!map.containsKey(k)) map.put(k, new ArrayList<>()) can be replaced with one line: map.computeIfAbsent(k, x -> new ArrayList<>()).

← Previous: List Next: Date & Time →

Map #

Map Overview #

HashMap #

Creating and Filling #

Reading and Searching #

Modifying and Removing #

Iteration #

LinkedHashMap #

Insertion Order #

Access Mode (LRU Cache) #

TreeMap #

Automatic Key Ordering #

Custom Ordering with a Comparator #

Key Range Navigation #

Hashtable #

Basic Operations #

Why It’s Not Recommended for New Code #

ConcurrentHashMap #

Basic Operations #

Atomic Operations #

Real Example: Counting Frequency from Many Threads #

Common Operations Across Implementations #

Default Values and Lazy Computation #

Collecting Data into a Map with Streams #

Converting Map to List and Vice Versa #

Performance Comparison #

Decision Tree for Choosing an Implementation #

When to Use Each Implementation #

Summary #