Java Collections Framework: Deep Dive into Set & Map Implementations

This chapter provides a comprehensive exploration of the internal methods, constructors, and architectural hierarchies of Java's Set and Map interfaces. We will trace the evolution of standard collections into highly optimized, specialized structures such as TreeSet, TreeMap, EnumMap, and IdentityHashMap, analyzing their performance characteristics and production use cases.

1. Set Interface Hierarchy & The TreeSet Evolution

To understand how Java's Set implementations function, we must first examine their inheritance structure. While HashSet and LinkedHashSet directly implement or extend classes that implement the core Set interface, TreeSet follows a more specialized path.

The Set Inheritance Hierarchy

The Design of the Set Interface

An interesting aspect of Java's interface design is that the Set interface does not declare a single unique method of its own. Every method inside Set (such as add(), remove(), contains(), clear(), isEmpty(), and size()) is inherited directly from the Collection and Iterable interfaces.

Note: The Set interface exists purely as a behavioral contract to enforce element uniqueness, relying on the type system and polymorphism rather than introducing new APIs.

In contrast, TreeSet implements NavigableSet, which in turn extends SortedSet. These two intermediate interfaces introduce a rich set of navigation and range-query APIs that make TreeSet highly powerful for sorted data operations.

2. HashSet & LinkedHashSet Constructors

Because HashSet and LinkedHashSet rely internally on a HashMap (or LinkedHashMap) to store elements, their constructors allow you to tune the performance of the underlying hash table.

The Four Core Constructors

Java provides four primary constructors for both HashSet and LinkedHashSet:

1. Default Constructor: Creates an empty set with a default initial capacity of 16 and a default load factor of 0.75.
2. Initial Capacity Constructor: Accepts an integer specifying the starting bucket size. This is useful when the approximate number of elements is known beforehand, preventing costly rehashing operations.
3. Initial Capacity & Load Factor Constructor: Accepts both the starting capacity and a custom load factor (as a float). The load factor determines when the hash table resizes itself. For example, a load factor of 0.8f means the set will rehash when it becomes 80% full.
4. Collection-Based Constructor: Initializes the set with elements copied from an existing collection, automatically removing duplicates.

Implementation Example

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.List;

public class SetConstructorDemo {
    public static void main(String[] args) {
        // 1. Default Constructor (Capacity: 16, Load Factor: 0.75)
        Set<Integer> defaultSet = new HashSet<>();

        // 2. Initial Capacity Constructor (Capacity: 100)
        Set<Integer> capacitySet = new HashSet<>(100);

        // 3. Initial Capacity & Custom Load Factor (Capacity: 100, Load Factor: 80%)
        Set<Integer> tunedSet = new HashSet<>(100, 0.80f);

        // 4. Initialized from another Collection
        List<Integer> sourceList = List.of(1, 2, 3, 4, 5, 5, 6); // Contains duplicate '5'
        Set<Integer> collectionSet = new HashSet<>(sourceList);
        
        System.out.println("Collection Set (duplicates removed): " + collectionSet);
        
        // The same constructors apply seamlessly to LinkedHashSet
        Set<Integer> linkedSet = new LinkedHashSet<>(100, 0.80f);
    }
}

3. TreeSet Operations: SortedSet & NavigableSet Methods

TreeSet is backed by a self-balancing Binary Search Tree (specifically a Red-Black Tree via TreeMap). Because of this structure, elements are kept in sorted order, enabling $O(\log n)$ time complexity for basic operations and unlocking specialized navigation methods.

Reference Variable Type Warning

To access these specialized methods, the reference variable must be declared as TreeSet (or NavigableSet/SortedSet) rather than the generic Set interface.

// WRONG: Set interface does not declare first() or last()
Set<Integer> mySet = new TreeSet<>(); 
// mySet.first(); // Compilation Error!

// CORRECT: Declare as TreeSet or NavigableSet
TreeSet<Integer> correctSet = new TreeSet<>();

SortedSet Interface Methods

These methods focus on basic boundary and range queries:

• first(): Returns the lowest (first) element currently in the set.
• last(): Returns the highest (last) element currently in the set.
• headSet(E toElement): Returns a view of the portion of the set whose elements are strictly less than toElement.
• tailSet(E fromElement): Returns a view of the portion of the set whose elements are greater than or equal to fromElement.
• subSet(E fromElement, E toElement): Returns a view of the portion of the set ranging from fromElement (inclusive) to toElement (exclusive).

NavigableSet Interface Methods

These methods provide highly granular search capabilities and mutating retrievals:

• lower(E e): Returns the greatest element strictly less than e, or null if there is no such element.
• floor(E e): Returns the greatest element less than or equal to e, or null if there is no such element.
• higher(E e): Returns the smallest element strictly greater than e, or null if there is no such element.
• ceiling(E e): Returns the smallest element greater than or equal to e, or null if there is no such element.
• pollFirst(): Retrieves and removes the first (lowest) element, or returns null if the set is empty.
• pollLast(): Retrieves and removes the last (highest) element, or returns null if the set is empty.
• descendingSet(): Returns a reverse-order view of the elements contained in this set.
• descendingIterator(): Returns an iterator over the elements in this set in descending order.

Real-World Analogy: The BST Boundary Property

Conceptually, in a Binary Search Tree (BST), the smallest element is always located at the extreme left-most leaf node, while the largest element is located at the extreme right-most leaf node. The first() and last() methods simply traverse to these boundaries in $O(\log n)$ time.

          [50] (Root)
         /    \
      [23]    [80]
      /  \      \
   [10]  [30]   [90]
   /
 [5] (Left-most / Smallest)
                  \
                  [95] (Right-most / Largest)

Comprehensive TreeSet Code Demonstration

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(80);
        set.add(23);
        set.add(10);
        set.add(90);
        set.add(50);

        System.out.println("Initial TreeSet: " + set); // Sorted automatically: [10, 23, 50, 80, 90]

        // --- SortedSet Methods ---
        System.out.println("First Element: " + set.first()); // 10
        System.out.println("Last Element: " + set.last());   // 90
        System.out.println("HeadSet (under 80): " + set.headSet(80)); // [10, 23, 50]
        System.out.println("TailSet (80 and above): " + set.tailSet(80)); // [80, 90]
        System.out.println("SubSet (23 to 80): " + set.subSet(23, 80)); // [23, 50]

        // --- NavigableSet Methods ---
        // Lower vs Floor
        System.out.println("Lower than 10: " + set.lower(10)); // null
        System.out.println("Floor of 10: " + set.floor(10));   // 10

        // Higher vs Ceiling
        System.out.println("Higher than 80: " + set.higher(80)); // 90
        System.out.println("Ceiling of 80: " + set.ceiling(80));   // 80

        // Reverse Views
        System.out.println("Descending Set: " + set.descendingSet()); // [90, 80, 50, 23, 10]

        // Tuned Range Queries (Using Boolean Flags)
        System.out.println("Inclusive HeadSet (under 80, inclusive): " + set.headSet(80, true)); // [10, 23, 50, 80]

        // Polling (Mutative)
        System.out.println("Polled First: " + set.pollFirst()); // Removes and returns 10
        System.out.println("Polled Last: " + set.pollLast());   // Removes and returns 90
        System.out.println("Set after polling: " + set);       // [23, 50, 80]
    }
}

4. Map Interface Hierarchy & Core Operations

Unlike Set, the Map interface does not extend Collection or Iterable. It represents an entirely separate hierarchy in the Java Collections Framework.

The Map Inheritance Hierarchy

Because it is outside the Collection hierarchy, Map must define all of its own methods. However, Java maintains naming consistency with the rest of the framework (e.g., size(), isEmpty(), clear()).

Core Map Methods

• put(K key, V value): Associates the specified value with the specified key. If the key already exists, it updates the value and returns the old value. If the key is new, it returns null.
• get(Object key): Returns the value associated with the key, or null if the key does not exist.
• containsKey(Object key): Returns true if the map contains the key. This is an $O(1)$ average-time operation due to hashing.
• containsValue(Object value): Returns true if the map contains the value. This is an $O(n)$ operation because it requires traversing all buckets and linked lists/trees to find a match.
• remove(Object key): Removes the mapping for a key and returns its associated value.

Key Views and Collections

Maps provide three distinct ways to view their contents:

1. keySet(): Returns a Set<K> of all keys. Keys are guaranteed to be unique.
2. values(): Returns a Collection<V> of all values. Values can contain duplicates, which is why this returns a general Collection rather than a Set.
3. entrySet(): Returns a Set<Map.Entry<K, V>> containing key-value pairs. Map.Entry is a nested interface inside Map that provides getKey() and getValue() methods.

5. Advanced & Production-Ready Map Methods

To write clean, robust, and exception-safe production code, you should use Java's advanced map APIs. These methods help prevent common issues like NullPointerException and reduce boilerplate code.

1. getOrDefault(Object key, V defaultValue)

Retrieves the value associated with the key. If the key is missing, it returns the specified default value instead of null. This is highly useful for avoiding manual null checks.

2. putIfAbsent(K key, V value)

Inserts the key-value pair only if the key is not already present or is mapped to null. Unlike put(), it will never overwrite an existing value.

3. Conditional remove(Object key, Object value)

Removes the entry for a key only if it is currently mapped to a specific value.

4. replace(K key, V value) & replace(K key, V oldValue, V newValue)

• replace(key, value): Updates the value for a key only if the key is already present. It will not insert a new entry.
• replace(key, oldValue, newValue): Updates the value only if the key is currently mapped to oldValue.

5. Map.of()

A static factory method introduced in Java 9 that returns an unmodifiable (immutable) map. Attempting to modify this map throws an UnsupportedOperationException.

Code Demonstration: Advanced Map Operations

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Collection;

public class AdvancedMapDemo {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        
        // Put returns null for new keys
        System.out.println("Put new key 1001: " + map.put(1001, "Aditya")); // null
        // Put returns old value when updating
        System.out.println("Put existing key 1001: " + map.put(1001, "Adi")); // "Aditya"

        map.put(1002, "Rohit");
        map.put(1003, "Rohan");

        // --- 1. getOrDefault ---
        System.out.println("Get 1002: " + map.getOrDefault(1002, "Unknown")); // "Rohit"
        System.out.println("Get 1005: " + map.getOrDefault(1005, "Unknown")); // "Unknown"

        // --- 2. putIfAbsent ---
        map.putIfAbsent(1003, "New Rohan"); // Will NOT change "Rohan"
        map.putIfAbsent(1004, "Abhay");     // Will insert "Abhay"
        System.out.println("Map after putIfAbsent: " + map);

        // --- 3. Conditional Remove ---
        boolean removed = map.remove(1001, "WrongName"); // Will not remove
        System.out.println("Removed with wrong value? " + removed);
        map.remove(1001, "Adi"); // Will successfully remove

        // --- 4. Safe Replace ---
        map.replace(1002, "Rohit", "Sonia"); // Updates "Rohit" to "Sonia"
        System.out.println("Map after replace: " + map);

        // --- 5. Iterating via EntrySet ---
        Set<Map.Entry<Integer, String>> entries = map.entrySet();
        for (Map.Entry<Integer, String> entry : entries) {
            System.out.println("Key: " + entry.getKey() + " -> Value: " + entry.getValue());
        }

        // --- 6. Immutable Map ---
        Map<Integer, String> immutableMap = Map.of(1, "One", 2, "Two");
        // immutableMap.put(3, "Three"); // Throws UnsupportedOperationException
    }
}

6. TreeMap Operations: SortedMap & NavigableMap Methods

Just as TreeSet inherits specialized methods from NavigableSet, TreeMap inherits specialized methods from NavigableMap and SortedMap. These methods mirror the ones found in TreeSet, but they operate on keys or key-value entries.

Key and Entry Navigation Methods

• firstKey() / lastKey(): Returns the lowest and highest keys.
• firstEntry() / lastEntry(): Returns the Map.Entry associated with the lowest and highest keys.
• lowerKey(K key) / lowerEntry(K key): Returns the greatest key (or entry) strictly less than the given key.
• floorKey(K key) / floorEntry(K key): Returns the greatest key (or entry) less than or equal to the given key.
• higherKey(K key) / higherEntry(K key): Returns the smallest key (or entry) strictly greater than the given key.
• ceilingKey(K key) / ceilingEntry(K key): Returns the smallest key (or entry) greater than or equal to the given key.
• pollFirstEntry() / pollLastEntry(): Removes and returns the entry with the lowest or highest key.
• descendingMap(): Returns a reverse-order view of the mappings contained in the map.

Code Demonstration: TreeMap Navigation

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

public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(1003, "Rohan");
        treeMap.put(1001, "Aditya");
        treeMap.put(1002, "Rohit");

        System.out.println("TreeMap (Sorted by Key): " + treeMap);

        // Boundary Queries
        System.out.println("First Key: " + treeMap.firstKey()); // 1001
        System.out.println("Last Entry: " + treeMap.lastEntry()); // 1003=Rohan

        // Navigational Queries
        System.out.println("Floor Entry of 1002: " + treeMap.floorEntry(1002)); // 1002=Rohit
        System.out.println("Lower Entry of 1002: " + treeMap.lowerEntry(1002)); // 1001=Aditya

        // Range Views
        System.out.println("HeadMap (before 1003): " + treeMap.headMap(1003)); // {1001=Aditya, 1002=Rohit}
        System.out.println("Descending Map: " + treeMap.descendingMap()); // Reverse sorted
    }
}

7. Specialized Map Implementations

Java provides several specialized Map implementations designed for specific use cases, performance requirements, or legacy compatibility.

1. Hashtable (Legacy Class)

Hashtable is a legacy class introduced in Java 1.0, before the Collections Framework existed. It is similar to HashMap but has two key differences:

• It is synchronized by default, making it thread-safe but slow because it locks the entire map for every operation.
• It does not allow null keys or null values.

Production Rule: Do not use Hashtable in modern applications. For non-thread-safe environments, use HashMap. For thread-safe environments, use ConcurrentHashMap.

2. Properties (Configuration Management)

Properties is a specialized subclass of Hashtable designed to store configuration data. It represents key-value pairs where both the keys and values are strings.

• It is commonly used to load configuration files (e.g., .properties files) containing application settings like database credentials or API endpoints.
• It will be covered extensively in Spring Boot and enterprise Java development.

3. WeakHashMap (Cache-Friendly Map)

WeakHashMap is a specialized map where the keys are stored as weak references.

• In a standard HashMap, as long as the map is alive, the keys inside it cannot be garbage collected, even if they are no longer used elsewhere in the application. This can lead to memory leaks.
• In a WeakHashMap, if a key is no longer referenced anywhere else in the application, the garbage collector can reclaim it. When the key is garbage collected, its corresponding entry is automatically removed from the map.
• This behavior makes WeakHashMap ideal for implementing temporary caches.

8. IdentityHashMap vs. Standard HashMap

To understand IdentityHashMap, we must first look at how a standard HashMap determines if two keys are identical.

Standard HashMap: Equality-Based (Logical Equality)

A standard HashMap uses the hashCode() and equals() methods to compare keys. This is known as logical equality.

If you create two separate string objects with the same content, they are considered equal by a standard HashMap:

String key1 = new String("Aditya");
String key2 = new String("Aditya");

System.out.println(key1.equals(key2)); // true (Logical Equality)
System.out.println(key1 == key2);      // false (Different memory addresses)

If you use these strings as keys in a standard HashMap, they will overwrite each other because their content is identical:

Map<String, Integer> map = new HashMap<>();
map.put(key1, 1);
map.put(key2, 2); 
System.out.println(map.size()); // Output: 1 (key2 overwrote key1)

IdentityHashMap: Identity-Based (Reference Equality)

IdentityHashMap breaks the standard map contract. Instead of using equals(), it uses the reference equality operator (==) to compare keys. It also bypasses the key's custom hashCode() method, using System.identityHashCode(key) instead.

For IdentityHashMap, key1 and key2 are treated as completely different keys because they point to different memory addresses in the heap:

import java.util.IdentityHashMap;
import java.util.Map;

public class IdentityMapDemo {
    public static void main(String[] args) {
        String key1 = new String("Aditya");
        String key2 = new String("Aditya");

        Map<String, Integer> identityMap = new IdentityHashMap<>();
        identityMap.put(key1, 1);
        identityMap.put(key2, 2);

        System.out.println("IdentityHashMap Size: " + identityMap.size()); // Output: 2
    }
}

Production Use Cases

IdentityHashMap is rarely used in typical business applications. However, it is highly useful in specialized system-level programming, such as:

• Graph Algorithms: Tracking visited nodes during traversal (where two nodes might have identical values but represent different locations in the graph).
• Serialization/Cloning Frameworks: Maintaining an object graph to prevent circular references during deep copy operations.

9. EnumMap: High-Performance Enum Keys

EnumMap is a highly optimized Map implementation designed specifically for use with enum keys.

Why Standard HashMap is Inefficient for Enums

If you use an enum as a key in a standard HashMap, the map still performs standard hashing operations: calculating the hash code, finding the bucket index, and handling potential collisions using linked lists or trees. This introduces unnecessary CPU and memory overhead.

How EnumMap Optimizes Performance

Because an enum has a fixed, predefined set of constants, Java knows the exact number of possible keys at compile time. Each enum constant also has an internal integer value called an ordinal (representing its declaration order, starting at 0).

EnumMap leverages this structure by using a simple, flat Java array (Object[]) internally. The enum's ordinal value acts directly as the array index:

This design provides several major advantages:

• Zero Hashing Collisions: Since each enum constant maps to a unique index, collisions are physically impossible.
• Extreme Speed: Key lookups and insertions are simple array index operations, which are much faster than standard hashing.
• Memory Efficiency: It does not require complex node objects or linked lists, making it highly lightweight.
• Preserved Iteration Order: Iterating over an EnumMap always returns entries in the natural declaration order of the enum.

Code Demonstration: EnumMap

import java.util.EnumMap;
import java.util.Map;

enum Day {
    MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY
}

public class EnumMapDemo {
    public static void main(String[] args) {
        // EnumMap requires the Class type of the enum in its constructor
        EnumMap<Day, String> activityMap = new EnumMap<>(Day.class);

        activityMap.put(Day.MONDAY, "Gym");
        activityMap.put(Day.WEDNESDAY, "Coding");
        activityMap.put(Day.FRIDAY, "Review");

        // activityMap.put(null, "Rest"); // Throws NullPointerException (Null keys not allowed)

        // Iteration order is guaranteed to match the enum declaration order
        for (Map.Entry<Day, String> entry : activityMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

10. ConcurrentHashMap: Modern Thread-Safe Concurrency

In multi-threaded applications, using a standard HashMap can lead to race conditions, data corruption, or infinite loops during resizing. While legacy classes like Hashtable or synchronized wrappers (e.g., Collections.synchronizedMap()) provide thread safety, they do so by locking the entire map for every read and write operation. This creates a major performance bottleneck.

The ConcurrentHashMap Approach

ConcurrentHashMap is Java's modern, highly optimized thread-safe map. Instead of locking the entire map, it uses a technique called lock striping or bucket-level locking:

• Fine-Grained Locking: It only locks the specific bucket (or node) being updated, allowing other threads to read or write to different buckets simultaneously.
• Lock-Free Reads: Read operations (get()) are completely lock-free and highly performant, relying on volatile memory reads to ensure data visibility.
• Compare-And-Swap (CAS): It uses low-level CPU instructions (CAS) to perform atomic updates without traditional locking whenever possible.

11. Synthesis: Map Implementations Comparison

The following table summarizes the key differences between Java's primary Map implementations:

Summary and Key Takeaways

• Set Interface Design: The Set interface does not define any unique methods of its own. It inherits its entire API from Collection and Iterable, acting purely as a contract to enforce element uniqueness.
• TreeSet & TreeMap Power: Both are backed by self-balancing Binary Search Trees (Red-Black Trees). They provide $O(\log n)$ time complexity for basic operations and offer powerful range-query and navigation methods (e.g., floor(), ceiling(), subMap()).
• Safe Production Code: Use advanced map methods like getOrDefault() to prevent NullPointerException and putIfAbsent() to avoid accidentally overwriting existing data.
• IdentityHashMap vs. HashMap: Standard HashMap uses logical equality (equals()), while IdentityHashMap uses reference equality (==), treating two objects with identical content as different keys if they reside at different memory addresses.
• EnumMap Optimization: EnumMap bypasses hashing entirely. It maps enum keys to a flat array using their internal ordinal values, providing $O(1)$ performance with zero collisions and minimal memory overhead.
• Concurrency Evolution: Avoid legacy synchronized maps like Hashtable. Use ConcurrentHashMap for modern, high-performance concurrent applications, as it locks at the bucket level rather than locking the entire map.