🗺️ Java Map Interface - Complete Guide

“Maps provide efficient key-value storage and retrieval, making them perfect for caching, configuration, and data lookup scenarios.”

🎯 What is the Map Interface?

The Map interface represents a collection of key-value pairs where:

• Keys are unique - no duplicate keys allowed
• Values can be duplicated - multiple keys can map to same value
• Efficient lookup - retrieve values by key in optimal time
• Not a Collection - separate hierarchy from Collection interface

🔗 Key Characteristics

Feature	Description	Example
Key-Value Pairs	Associates keys with values	"name" → "John"
Unique Keys	No duplicate keys allowed	{a→1, b→2} not {a→1, a→3}
Duplicate Values	Multiple keys can have same value	{a→1, b→1} is valid
Null Handling	Depends on implementation	HashMap allows nulls, TreeMap doesn’t

📊 Map Hierarchy and Implementations

🌳 Interface Hierarchy

Map<K,V> (interface)
├── HashMap<K,V> - Hash table implementation, O(1) operations
├── LinkedHashMap<K,V> - Maintains insertion/access order
├── Hashtable<K,V> - Synchronized HashMap (legacy)
├── SortedMap<K,V> (interface)
│   └── NavigableMap<K,V> (interface)
│       └── TreeMap<K,V> - Red-black tree, sorted keys
├── ConcurrentMap<K,V> (interface) - Thread-safe maps
│   ├── ConcurrentHashMap<K,V> - High-performance concurrent map
│   └── ConcurrentSkipListMap<K,V> - Concurrent sorted map
└── Properties - String-based configuration map (legacy)

📈 Performance Comparison Matrix

Implementation	Get	Put	Remove	Iteration	Null Keys	Null Values	Thread Safe	Ordering
HashMap	O(1)*	O(1)*	O(1)*	O(n)	1 allowed	✅	❌	No
LinkedHashMap	O(1)*	O(1)*	O(1)*	O(n)	1 allowed	✅	❌	Insertion/Access
TreeMap	O(log n)	O(log n)	O(log n)	O(n)	❌	✅	❌	Sorted
Hashtable	O(1)*	O(1)*	O(1)*	O(n)	❌	❌	✅	No
ConcurrentHashMap	O(1)*	O(1)*	O(1)*	O(n)	❌	❌	✅	No

* Average case - worst case O(n) due to hash collisions

💻 Method Usage Examples

public class MapMethodExamples {
    public void demonstrateMapMethods() {
        Map<String, Integer> scores = new HashMap<>();

        // Basic operations
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);

        // Retrieve values
        Integer aliceScore = scores.get("Alice");  // 95
        Integer davidScore = scores.get("David");  // null

        // Safe retrieval with default
        Integer safeScore = scores.getOrDefault("David", 0);  // 0

        // Check existence
        boolean hasAlice = scores.containsKey("Alice");      // true
        boolean hasScore95 = scores.containsValue(95);       // true

        // Remove entries
        Integer removed = scores.remove("Bob");              // 87
        boolean removedBob = scores.remove("Bob", 87);       // false (already removed)

        // Size operations
        int size = scores.size();                            // 2
        boolean isEmpty = scores.isEmpty();                  // false

        // Clear all entries
        scores.clear();
        System.out.println("Size after clear: " + scores.size());  // 0
    }
}

🚀 HashMap Implementation

💡 What is HashMap?

HashMap is a hash table-based implementation of the Map interface that provides:

• O(1) average case operations for get, put, and remove
• No ordering guarantees
• Efficient memory usage
• Fast key-based lookup

🔧 HashMap Construction

public class HashMapConstructionExamples {
    public void demonstrateConstruction() {
        // Default constructor (initial capacity 16, load factor 0.75)
        HashMap<String, Integer> map1 = new HashMap<>();

        // With initial capacity
        HashMap<String, Integer> map2 = new HashMap<>(100);

        // With initial capacity and load factor
        HashMap<String, Integer> map3 = new HashMap<>(100, 0.8f);

        // From existing map
        Map<String, Integer> existing = Map.of("a", 1, "b", 2, "c", 3);
        HashMap<String, Integer> map4 = new HashMap<>(existing);

        // Using factory methods (Java 9+)
        Map<String, Integer> immutableMap = Map.of("x", 10, "y", 20, "z", 30);
        HashMap<String, Integer> mutableMap = new HashMap<>(immutableMap);
    }
}

📊 HashMap Performance Characteristics

public class HashMapPerformanceExample {
    public void demonstratePerformance() {
        HashMap<String, Integer> scores = new HashMap<>();

        // Fast insertion (O(1) average)
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        scores.put("David", 89);
        scores.put("Eve", 91);

        // Fast lookup (O(1) average)
        Integer aliceScore = scores.get("Alice");
        boolean hasBob = scores.containsKey("Bob");

        // Fast removal (O(1) average)
        Integer removed = scores.remove("Charlie");

        // Iteration (O(n))
        System.out.println("All scores:");
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // Bulk operations
        Map<String, Integer> moreScores = Map.of("Frank", 88, "Grace", 94);
        scores.putAll(moreScores);

        // Java 8+ methods
        scores.putIfAbsent("Alice", 100);  // Won't overwrite existing 95
        scores.computeIfAbsent("Henry", k -> 85);  // Add if not present
        scores.computeIfPresent("Bob", (k, v) -> v + 5);  // Update if present

        System.out.println("Updated scores: " + scores);
    }
}

🔗 LinkedHashMap Implementation

💡 What is LinkedHashMap?

LinkedHashMap extends HashMap to maintain a doubly-linked list that preserves:

• Insertion order or access order of entries
• HashMap performance characteristics
• Predictable iteration order
• Higher memory overhead than HashMap

🔧 LinkedHashMap Usage

public class LinkedHashMapExamples {
    public void demonstrateLinkedHashMap() {
        // Insertion-order LinkedHashMap (default)
        LinkedHashMap<String, Integer> insertionOrderMap = new LinkedHashMap<>();
        insertionOrderMap.put("first", 1);
        insertionOrderMap.put("second", 2);
        insertionOrderMap.put("third", 3);

        System.out.println("Insertion order preserved:");
        for (String key : insertionOrderMap.keySet()) {
            System.out.print(key + " ");  // first second third
        }
        System.out.println();

        // Access-order LinkedHashMap
        LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderMap.put("a", 1);
        accessOrderMap.put("b", 2);
        accessOrderMap.put("c", 3);

        // Accessing elements changes order
        accessOrderMap.get("a");  // Move 'a' to end
        accessOrderMap.get("b");  // Move 'b' to end

        System.out.println("Access order (most recently used last):");
        for (String key : accessOrderMap.keySet()) {
            System.out.print(key + " ");  // c a b
        }
        System.out.println();

        // LRU Cache implementation
        LinkedHashMap<String, String> lruCache = new LinkedHashMap<String, String>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 3;  // Keep only 3 entries
            }
        };

        lruCache.put("key1", "value1");
        lruCache.put("key2", "value2");
        lruCache.put("key3", "value3");
        lruCache.put("key4", "value4");  // Removes oldest entry (key1)

        System.out.println("LRU Cache: " + lruCache.keySet());
    }
}

🌳 TreeMap Implementation

💡 What is TreeMap?

TreeMap is a red-black tree-based implementation that provides:

• Sorted keys in natural order or custom comparator
• O(log n) operations for get, put, and remove
• Navigable operations (ceiling, floor, higher, lower)
• No null keys allowed

🔧 TreeMap Construction

public class TreeMapConstructionExamples {
    public void demonstrateConstruction() {
        // Default constructor (natural ordering)
        TreeMap<String, Integer> naturalOrder = new TreeMap<>();

        // With custom comparator
        TreeMap<String, Integer> reverseOrder = new TreeMap<>(Comparator.reverseOrder());

        // With initial map
        Map<String, Integer> existing = Map.of("a", 1, "b", 2, "c", 3);
        TreeMap<String, Integer> fromMap = new TreeMap<>(existing);

        // Custom object with natural ordering
        TreeMap<Person, String> people = new TreeMap<>();

        // Using NavigableMap methods
        NavigableMap<String, Integer> navigableMap = new TreeMap<>();
    }
}

📊 TreeMap Performance Characteristics

public class TreeMapPerformanceExample {
    public void demonstratePerformance() {
        TreeMap<Integer, String> sortedMap = new TreeMap<>();

        // Insertion (O(log n))
        sortedMap.put(5, "five");
        sortedMap.put(2, "two");
        sortedMap.put(8, "eight");
        sortedMap.put(1, "one");
        sortedMap.put(9, "nine");

        // Keys are automatically sorted
        System.out.println("Sorted keys: " + sortedMap.keySet());

        // Navigable operations
        Integer ceiling = sortedMap.ceilingKey(6);    // 8 (smallest >= 6)
        Integer floor = sortedMap.floorKey(6);        // 5 (largest <= 6)
        Integer higher = sortedMap.higherKey(5);      // 8 (smallest > 5)
        Integer lower = sortedMap.lowerKey(5);        // 2 (largest < 5)

        System.out.println("Ceiling(6): " + ceiling);
        System.out.println("Floor(6): " + floor);
        System.out.println("Higher(5): " + higher);
        System.out.println("Lower(5): " + lower);

        // Submap operations
        NavigableMap<Integer, String> subMap = sortedMap.subMap(2, true, 8, true);
        System.out.println("Submap [2,8]: " + subMap);

        // Head and tail maps
        SortedMap<Integer, String> headMap = sortedMap.headMap(5);
        SortedMap<Integer, String> tailMap = sortedMap.tailMap(5);

        System.out.println("Head map < 5: " + headMap);
        System.out.println("Tail map >= 5: " + tailMap);

        // First and last entries
        Map.Entry<Integer, String> first = sortedMap.firstEntry();
        Map.Entry<Integer, String> last = sortedMap.lastEntry();

        System.out.println("First: " + first);
        System.out.println("Last: " + last);
    }
}

📊 Decision Matrix

Use Case	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap	ConcurrentSkipListMap
General Purpose	✅ Best	✅ Good	⚠️ Good	✅ Good	⚠️ Good
Performance	✅ Best	✅ Good	⚠️ Good	✅ Good	⚠️ Good
Memory Efficiency	✅ Best	❌ Poor	✅ Good	✅ Good	✅ Good
Ordering	❌ No	✅ Insertion/Access	✅ Sorted	❌ No	✅ Sorted
Thread Safety	❌ No	❌ No	❌ No	✅ Best	✅ Best
Range Queries	❌ Poor	❌ Poor	✅ Best	❌ Poor	✅ Best