Advanced Collection Framework

Understanding Map Collections

Map collections in Java have several distinctive characteristics:

1. They store data in key-value pairs, requiring both elements for each entry
2. Keys must be unique while values can be duplicated
3. Each key maps to exactly one value, creating a one-to-one relationship
4. The combined key-value pair is called an "Entry" object in Java

Essential Map API Methods

Map<String, String> userMap = new HashMap<>();

/* The put method behavior:
When adding data, if the key doesn't exist, the key-value pair is added to the map, returning null
When adding data, if the key already exists, the existing value is replaced, and the old value is returned
*/
userMap.put("John", "Doe");
userMap.put("Jane", "Smith");

// Clear all entries
userMap.clear();

// Check for existence of keys or values
boolean hasKey = userMap.containsKey("John");
boolean hasValue = userMap.containsValue("Doe");

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

// Get the size of the map
int mapSize = userMap.size();

Map Traversal Techniques

Key-Based Traversal

// First, retrieve all keys as a set
Set<String> keys = userMap.keySet();

// Iterate through each key in the set
for (String currentKey : keys) {
    // Use the key to get the corresponding value
    String associatedValue = userMap.get(currentKey);
    System.out.println(currentKey + " : " + associatedValue);
}

Entry-Based Traversal

// Get all entry objects from the map
Set<Map.Entry<String, String>> entries = userMap.entrySet();

// Iterate through each entry
for (Map.Entry<String, String> currentEntry : entries) {
    // Extract key and value from the entry
    String entryKey = currentEntry.getKey();
    String entryValue = currentEntry.getValue();
    System.out.println(entryKey + " : " + entryValue);
}

Lambda Expression Traversal

// Use forEach with a lambda expression
userMap.forEach((key, value) -> System.out.println(key + " : " + value));

HashMap Implementation

HashMap is a concrete implementation of the Map interface with these characteristics:

• No additional methods beyond those in the Map interface
• Properties determined by keys: unordered, unique keys, no indexing
• Uses a hash table structure, similar to HashSet
• Relies on hashCode() and equals() methods to ensure key uniqueness
• Custom objects used as keys require proper hashCode() and equals() implementation

HashMap<Employee, String> employeeDepartmentMap = new HashMap<>();

// Create employee objects
Employee emp1 = new Employee("Robert", 30);
Employee emp2 = new Employee("Emily", 28);
Employee emp3 = new Employee("Michael", 35);

// Add elements to the map
employeeDepartmentMap.put(emp1, "Engineering");
employeeDepartmentMap.put(emp2, "Marketing");
employeeDepartmentMap.put(emp3, "Finance");

// Traversal example using key set
Set<Employee> employeeKeys = employeeDepartmentMap.keySet();
for (Employee currentEmployee : employeeKeys) {
    String department = employeeDepartmentMap.get(currentEmployee);
    System.out.println(currentEmployee + " works in " + department);
}

Frequency Counting with HashMap

// For counting occurrences when simple counters aren't sufficient
// We can use a map for efficient counting
HashMap<String, Integer> frequencyMap = new HashMap<>();

for (String currentItem : itemList) {
    // Check if the item already exists in our map
    if (frequencyMap.containsKey(currentItem)) {
        // Get the current count
        int currentCount = frequencyMap.get(currentItem);
        // Increment the count
        currentCount++;
        // Update the map with the new count
        frequencyMap.put(currentItem, currentCount);
    } else {
        // First occurrence of the item
        frequencyMap.put(currentItem, 1);
    }
}
System.out.println(frequencyMap);

// Find the maximum frequency
int highestFrequency = 0;
Set<Map.Entry<String, Integer>> frequencyEntries = frequencyMap.entrySet();
for (Map.Entry<String, Integer> entry : frequencyEntries) {
    int currentFrequency = entry.getValue();
    if (currentFrequency > highestFrequency) {
        highestFrequency = currentFrequency;
    }
}
System.out.println("Highest frequency: " + highestFrequency);

LinkedHashMap Implementation

LinkedHashMap extends HashMap with these additional features:

• Properties determined by keys: ordered, unique keys, no indexing
• Maintains insertion order (the order in which elements were added)
• Uses a hash table with an additional doubly-linked list to maintain order

LinkedHashMap<String, Integer> orderedMap = new LinkedHashMap<>();

// Add elements
orderedMap.put("first", 100);
orderedMap.put("second", 200);
orderedMap.put("third", 300);

// Output will maintain insertion order: {first=100, second=200, third=300}
System.out.println(orderedMap);

TreeMap Implementation

TreeMap provides these characteristics:

• Uses a red-black tree structure, similar to TreeSet
• Properties determined by keys: unique keys, no indexing, sortable
• Keys are sorted according to their natural order or a specified comparator
• Default sorting is ascending, but custom comparators can change this

Two ways to define sorting rules:

1. Implemetn the Comparable interface in the key class
2. Provide a Comparator object when creating the TreeMap

// Create a TreeMap with custom sorting
TreeMap<Integer, String> descendingTreeMap = new TreeMap<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer firstValue, Integer secondValue) {
        // firstValue: the element to be added
        // secondValue: the element already in the tree
        return secondValue - firstValue;  // Sort in descending order
    }
});

// Example: character frequency counting with sorted output
String text = "aababcabcdabcde";
TreeMap<Character, Integer> charFrequencyMap = new TreeMap<>();

for (int i = 0; i < text.length(); i++) {
    char currentChar = text.charAt(i);
    if (charFrequencyMap.containsKey(currentChar)) {
        int count = charFrequencyMap.get(currentChar);
        count++;
        charFrequencyMap.put(currentChar, count);
    } else {
        charFrequencyMap.put(currentChar, 1);
    }
}

// Build a formatted result string
StringBuilder resultBuilder = new StringBuilder();
charFrequencyMap.forEach((character, count) -> 
    resultBuilder.append(character).append("(").append(count).append(")")
);

System.out.println(resultBuilder);

Variable Arguments (Varargs)

Java allows methods to accept a variable number of arguments using varargs syntax:

// Varargs syntax: type... name
void displayNumbers(int... numbers) {
    // Varargs are implemented as arrays under the hood
    System.out.println("Received " + numbers.length + " numbers:");
    for (int num : numbers) {
        System.out.println(num);
    }
}

/* Varargs usage rules:
1. A method can have at most one varargs parameter
2. If other parameters are present, the varargs parameter must be the last one
*/

Collections Utility Class

The Collections class provides static utility methods for operating on collections:

// Common utility methods

// Add multiple elements to a collection
public static <T> boolean addAll(Collection<T> collection, T... elements)

// Randomize the order of elements in a List
public static void shuffle(List<?> list)

// Sort a List using natural ordering
public static <T> void sort(List<T> list)

// Sort a List using a custom comparator
public static <T> void sort(List<T> list, Comparator<? super T> comparator)

// Binary search for an element in a sorted List
public static <T> int binarySearch(List<? extends T> list, T key)

// Copy elements from one list to another
public static <T> void copy(List<? super T> destination, List<? extends T> source)

// Fill a list with a specified element
public static <T> void fill(List<? super T> list, T element)

// Find the maximum/minimum element using natural ordering
public static <T> T max(Collection<? extends T> collection)
public static <T> T min(Collection<? extends T> collection)

// Swap elements at two positions in a list
public static void swap(List<?> list, int index1, int index2)

// Usage example:
ArrayList<String> wordList = new ArrayList<>();

// Add multiple elements at once
Collections.addAll(wordList, "apple", "banana", "cherry", "date", "elderberry");

// Shuffle the elements
Collections.shuffle(wordList);
System.out.println("Shuffled: " + wordList);

// Sort the list
Collections.sort(wordList);
System.out.println("Sorted: " + wordList);