Map Collections in Java

Master the Map interface, HashMap, LinkedHashMap, TreeMap, Hashtable, and key-value operations for the OCP 21 exam.

Table of Contents

1. Map Interface

The Map interface represents a collection of key-value pairs. Each key maps to exactly one value. Maps do not extend Collection interface.

1.1 Map Characteristics

  • Key-Value Pairs: Stores entries as key-value pairs
  • Unique Keys: Each key can appear only once
  • No Duplicate Keys: Adding same key replaces old value
  • Null Keys/Values: May allow null (implementation-dependent)
  • Not a Collection: Map doesn't extend Collection

1.2 Common Map Implementations

  • HashMap : Hash table implementation, no order
  • LinkedHashMap : Hash table + linked list, insertion order
  • TreeMap : Red-black tree, sorted by keys
  • Hashtable : Legacy synchronized hash table

2. HashMap

HashMap is a hash table implementation of the Map interface. It provides constant-time performance for basic operations.

2.1 Creating HashMap

Example: 
import java.util.*;
// Create empty HashMap Map<
String, Integer>
map1 = new HashMap<
>
();
// Create with initial capacity Map<
String, Integer>
map2 = new HashMap<
>
(16);
// Create with initial capacity and load factor Map<
String, Integer>
map3 = new HashMap<
>
(16, 0.75f);
// Create from another map Map<
String, Integer>
map4 = new HashMap<
>
(map1);
// Using Map.of() (Java 9+) - immutable Map<
String, Integer>
map5 = Map.of("A", 1,"B", 2,"C", 3);

2.2 HashMap Features

  • Uses hash table for storage
  • No guaranteed order
  • O(1) average time for get, put, remove
  • Allows one null key and multiple null values
  • Not thread-safe
  • Uses equals() and hashCode() for keys

3. LinkedHashMap

LinkedHashMap extends HashMap and maintains insertion order using a linked list.

3.1 Creating LinkedHashMap

Example: 
import java.util.*;
// Create LinkedHashMap Map<
String, Integer>
map = new LinkedHashMap<
>
();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
// Maintains insertion order for (String key : map.keySet()) {
    System.out.println(key);
    // Apple, Banana, Cherry (in order) } // Access order mode (LRU cache) Map<
String, Integer>
lruMap = new LinkedHashMap<
>
(16, 0.75f, true);
// true = access order, false = insertion
order

3.2 LinkedHashMap Features

  • Maintains insertion order
  • Can maintain access order (LRU cache)
  • O(1) average time for operations
  • Slightly more memory overhead than HashMap
  • Allows one null key and multiple null values

4. TreeMap

TreeMap is a NavigableMap implementation based on a red-black tree. Entries are stored sorted by keys.

4.1 Creating TreeMap

Example: 
import java.util.*;
// Create TreeMap (natural ordering) Map<
String, Integer>
map1 = new TreeMap<
>
();
map1.put("Banana", 2);
map1.put("Apple", 1);
map1.put("Cherry", 3);
// Keys stored in sorted order: Apple, Banana, Cherry // Create with Comparator Map<
String, Integer>
map2 = new TreeMap<
>
(Comparator.reverseOrder());
map2.put("Apple", 1);
map2.put("Banana", 2);
// Keys: Banana, Apple (reverse order) // Create from another map Map<
String, Integer>
map3 = new TreeMap<
>
(map1);

4.2 TreeMap Features

  • Entries stored sorted by keys
  • O(log n) time for operations
  • Does not allow null keys (but allows null values)
  • Keys must be Comparable or provide Comparator
  • Implements NavigableMap (provides navigation methods)

4.3 NavigableMap Methods

Example: 
NavigableMap<
Integer, String>
map = new TreeMap<
>
();
map.put(10,"Ten");
map.put(20,"Twenty");
map.put(30,"Thirty");
map.put(40,"Forty");
map.put(50,"Fifty");
// Navigation methods Map.Entry<
Integer, String>
lower = map.lowerEntry(25);
// 20=Twenty Map.Entry<
Integer, String>
floor = map.floorEntry(25);
// 20=Twenty Map.Entry<
Integer, String>
higher = map.higherEntry(25);
// 30=Thirty Map.Entry<
Integer, String>
ceiling = map.ceilingEntry(25);
// 30=Thirty // First and last Map.Entry<
Integer, String>
first = map.firstEntry();
// 10=Ten Map.Entry<
Integer, String>
last = map.lastEntry();
// 50=Fifty // Poll first/last (remove and return) Map.Entry<
Integer, String>
polled = map.pollFirstEntry();
// 10=Ten (removed) Map.Entry<
Integer, String>
polled2 = map.pollLastEntry();
// 50=Fifty (removed) // Head, tail, subMap views NavigableMap<
Integer, String>
head = map.headMap(30, false);
// entries <
30 NavigableMap<
Integer, String>
tail = map.tailMap(30, true);
// entries >
= 30 NavigableMap<
Integer, String>
sub = map.subMap(20, false, 40, true);
// 20 <
x <
= 40

5. Hashtable

Hashtable is a legacy synchronized hash table implementation. Similar to HashMap but thread-safe.

5.1 Hashtable Characteristics

Note: Hashtable is legacy. Use HashMap with Collections.synchronizedMap() or ConcurrentHashMap for thread-safety.
Example: 
import java.util.*;
// Create Hashtable Hashtable<
String, Integer>
table = new Hashtable<
>
();
// Hashtable is synchronized (thread-safe) // But slower than HashMap due to synchronization overhead // Does not allow null keys or
values

6. Map Operations

6.1 Adding and Updating Entries

Example: 
Map<
String, Integer>
map = new HashMap<
>
();
// Put entry (adds or updates) Integer oldValue = map.put("Apple", 1);
// null (new key) Integer oldValue2 = map.put("Apple", 10);
// 1 (replaced old value) // Put if absent (only if key doesn't exist) Integer value = map.putIfAbsent("Banana", 2);

// null (added) Integer value2 = map.putIfAbsent("Banana", 20);

// 2 (not replaced) // Put all from another map Map<String, Integer>

more = Map.of("Cherry", 3,"Date", 4);
map.putAll(more);
// Compute (Java 8+) map.compute("Apple", (k, v) -> v == null ? 1 : v + 1);

// Increment value // Compute if absent map.computeIfAbsent("Grape", k -> 5);

// Adds if key doesn't exist // Compute if present map.computeIfPresent("Apple", (k, v) -> v * 2);
// Updates if key exists // Merge (Java 8+) map.merge("Apple", 1, (oldVal, newVal) -> oldVal + newVal);
// Merge
values

6.2 Removing Entries

Example: 
Map<
String, Integer>
map = new HashMap<
>
();
map.putAll(Map.of("Apple", 1,"Banana", 2,"Cherry", 3));
// Remove by key Integer removed = map.remove("Banana");
// Returns 2 (removed value) // Remove by key and value boolean removed2 = map.remove("Cherry", 3);
// true (key-value matched) // Remove if condition map.entrySet().removeIf(entry -> entry.getValue() <
2);
// Clear all map.clear();
// Removes all
entries

6.3 Retrieving Values

Example: 
Map<
String, Integer>
map = new HashMap<
>
();
map.putAll(Map.of("Apple", 1,"Banana", 2,"Cherry", 3));
// Get value by key Integer value = map.get("Apple");
// 1 Integer value2 = map.get("Grape");
// null (key doesn't exist) // Get with default value Integer value3 = map.getOrDefault("Grape", 0);

// 0 (default if not found) // Check if contains key boolean hasKey = map.containsKey("Apple");

// true // Check if contains value boolean hasValue = map.containsValue(2);

// true // Size int size = map.size();

// 3 // Check if empty boolean empty = map.isEmpty();

// false

7. Map Views

Maps provide three collection views: keySet, values, and entrySet.

7.1 Key Set View

Example: 
Map<
String, Integer>
map = new HashMap<
>
();
map.putAll(Map.of("Apple", 1,"Banana", 2,"Cherry", 3));
// Get key set (view, not copy) Set<
String>
keys = map.keySet();
// Iterate keys for (String key : keys) {
    System.out.println(key);
} // Remove from map via keySet keys.remove("Apple");
// Removes entry from map // keySet is a view - changes reflect in map map.put("Date", 4);
// keys now
contains"Date"

7.2 Values View

Example: 
Map<
String, Integer>
map = new HashMap<
>
();
map.putAll(Map.of("Apple", 1,"Banana", 2,"Cherry", 3));
// Get values collection (view) Collection<
Integer>
values = map.values();
// Iterate values for (Integer value : values) {
    System.out.println(value);
} // Remove from map via values values.remove(2);
// Removes entry with value 2 // Values is a view - changes reflect in
map

7.3 Entry Set View

Example: 
Map<
String, Integer>
map = new HashMap<
>
();
map.putAll(Map.of("Apple", 1,"Banana", 2,"Cherry", 3));
// Get entry set (view) Set<
Map.Entry<
String, Integer>
>
entries = map.entrySet();
// Iterate entries for (Map.Entry<
String, Integer>
entry : entries) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key +" =" + value);
    // Update value via entry entry.setValue(value * 2);
} // Remove from map via entrySet entries.removeIf(entry -> entry.getValue() <
2);
// Entry set is a view - changes reflect in
map

8. Map Implementations Comparison

Feature HashMap LinkedHashMap TreeMap Hashtable
Ordering No order Insertion order Sorted by keys No order
Performance O(1) average O(1) average O(log n) O(1) average
Null Keys One null allowed One null allowed No null allowed No null allowed
Null Values Multiple allowed Multiple allowed Multiple allowed No null allowed
Thread-Safe No No No Yes
When to Use General purpose Need insertion order Need sorted keys Legacy code, avoid

9. Exam Key Points

Critical Concepts for OCP 21 Exam:

  • Map Interface: Key-value pairs, unique keys, doesn't extend Collection
  • HashMap: Hash table, no order, O(1) operations, allows one null key
  • LinkedHashMap: Maintains insertion order, O(1) operations
  • TreeMap: Sorted by keys, O(log n) operations, NavigableMap
  • Hashtable: Legacy synchronized HashMap, avoid using
  • put(): Adds or updates entry, returns old value (or null)
  • putIfAbsent(): Adds only if key doesn't exist
  • get(): Returns value for key, null if not found
  • getOrDefault(): Returns value or default if not found
  • remove(): Removes entry by key, returns value
  • containsKey(): Checks if key exists
  • containsValue(): Checks if value exists
  • keySet(): Returns Set view of keys
  • values(): Returns Collection view of values
  • entrySet(): Returns Set view of entries
  • Map Views: Changes to views reflect in map
  • compute(): Computes new value for key
  • merge(): Merges values for key
  • TreeMap Navigation: lowerEntry(), floorEntry(), higherEntry(), ceilingEntry()
  • TreeMap Views: headMap(), tailMap(), subMap()
  • Null Keys: HashMap/LinkedHashMap allow one null, TreeMap/Hashtable don't
  • Null Values: HashMap/LinkedHashMap/TreeMap allow null, Hashtable doesn't
Tags:

Post a Comment

0 Comments