Collections

 

The Java Collections Framework provides a unified architecture for representing and manipulating collections. This blogs covers some important aspects of the framework.

A PriorityQueue is a queue data structure where elements are ordered by their priority (natural or custom).

• Characteristics:

• Implements Queue

• Uses a min-heap internally

• Doesn’t allow null elements

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a PriorityQueue of Integers (natural ordering - min-heap)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add elements
        pq.add(10);
        pq.add(5);
        pq.add(20);
        pq.add(1);
        pq.add(15);

        System.out.println("Elements in PriorityQueue (order not guaranteed on print): " + pq);

        // Retrieve elements (elements are retrieved in ascending order)
        System.out.println("Polling elements from PriorityQueue:");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // poll() retrieves and removes the head (smallest element)
        }

        // PriorityQueue with custom ordering (max-heap)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // Lambda for reverse order
        maxHeap.add(10);
        maxHeap.add(5);
        maxHeap.add(20);
        maxHeap.add(1);
        maxHeap.add(15);

        System.out.println("\nPolling elements from Max-Heap PriorityQueue:");
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // now it retrieves the largest element first
        }
    }
}

Comparable Interface

The Comparable interface has a single method: public int compareTo(T o)

• Returns a negative integer if this object is less than o.
• Returns zero if this object is equal to o.
• Returns a positive integer if this object is greater than o.

class Student implements Comparable<Student> {
    int id;
    String name;

    public int compareTo(Student s) {
        return this.id - s.id;
    }
}

Comparator Interface

use for custom sorting

Comparator<Student> nameComparator = (s1, s2) -> s1.name.compareTo(s2.name);
Collections.sort(studentList, nameComparator);

Internal Working of HashSet

A HashSet internally uses a HashMap to store its elements. Each element added to the HashSet is stored as a "key" in the internal HashMap, and a dummy Object (a static final Object instance) is stored as its "value".

When you add an element to a HashSet:

1. hashCode() Call: The hashCode() method of the object being added is called. This hashCode is used to determine the initial bucket (or index) in the underlying array of the HashMap where the object might be stored.

2. Bucket Location: Based on the hashCode, the HashMap finds the appropriate bucket. A bucket can contain multiple objects if they have the same hashCode (this is called a "hash collision"). These objects are typically stored in a linked list or, in Java 8+, a balanced tree (like a Red-Black tree) if the list becomes too long, to maintain performance.

3. equals() Call: If the bucket is not empty (i.e., there's a possibility of a collision or a duplicate), the equals() method of the object being added is called to compare it with each object already present in that bucket.

   • If equals() returns true for any object, it means the element is already present, and add() returns false (as HashSet stores unique elements).

   • If equals() returns false for all objects in the bucket, the new element is added to that bucket.

Why equals() and hashCode() are crucial:

• If two objects are equal according to the equals(Object) method, then calling the hashCode() method on each of the two objects must produce the same integer result.

• It is NOT required that if two objects have the same hashCode then they must be equal. (This is why equals() is necessary to resolve collisions).

LinkedHashSet

It guarantees that no duplicate elements are stored. However maintains the insertion order of elements.

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> uniqueColors = new LinkedHashSet<>();

        System.out.println("Adding elements to LinkedHashSet:");
        uniqueColors.add("Red");
        uniqueColors.add("Green");
        uniqueColors.add("Blue");
        uniqueColors.add("Red"); // Duplicate, will not be added
        uniqueColors.add("Yellow");

        System.out.println("Elements in LinkedHashSet (insertion order preserved):");
        for (String color : uniqueColors) {
            System.out.println(color);
        }

        System.out.println("\nDoes it contain 'Green'? " + uniqueColors.contains("Green"));
        System.out.println("Removing 'Blue': " + uniqueColors.remove("Blue"));
        System.out.println("Elements after removing 'Blue': " + uniqueColors);
    }
}

TreeSet 

implementation of the SortedSet interface that stores elements in a sorted (ascending) order. It internally uses a TreeMap for storage and ensures that elements are unique.

Key Characteristics:

• Sorted Order: Elements are stored and retrieved in ascending order (natural ordering or by a provided Comparator).

• Uniqueness: Stores only unique elements.

• No Nulls: Does not permit null elements (unlike HashSet prior to Java 7, but TreeSet never allowed it).

• Internal Implementation: Backed by a TreeMap. Elements are stored as keys in the TreeMap, with a dummy Object as values.

• Performance: Offers O(log n) time complexity for add, remove, and contains operations, due to its tree-based nature (typically a Red-Black Tree).

When to Use TreeSet:

• When you need a Set where elements are automatically kept in sorted order.

• When you frequently need to perform range-based operations (e.g., finding elements greater than a certain value).

• Useful for maintaining unique elements and iterating over them in a sorted sequence.

Important Note for Custom Objects: For TreeSet to sort custom objects, those objects must either:

1. Implement the Comparable interface (for natural ordering).

2. Be provided with a Comparator at TreeSet creation time.

public class TreeSetExample {
    public static void main(String[] args) {
        // TreeSet with natural ordering (Integers are naturally comparable)
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(50);
        numbers.add(10);
        numbers.add(30);
        numbers.add(20);
        numbers.add(10); // Duplicate, will not be added

        System.out.println("Numbers in TreeSet (natural order): " + numbers);

        System.out.println("First element: " + numbers.first());
        System.out.println("Last element: " + numbers.last());
        System.out.println("Elements less than or equal to 30: " + numbers.headSet(30, true));
        System.out.println("Elements greater than 20: " + numbers.tailSet(20, false));

        // TreeSet with custom objects (using our Student class and a Comparator)
        TreeSet<Student> studentsByName = new TreeSet<>(Comparator.comparing(Student::getName));
        studentsByName.add(new Student("Alice", 103, 85.5));
        studentsByName.add(new Student("Bob", 101, 92.0));
        studentsByName.add(new Student("Charlie", 102, 78.0));
        studentsByName.add(new Student("Alice", 100, 90.0)); // This Alice will be considered a duplicate of the first if 'name' is the only comparison factor

        System.out.println("\nStudents in TreeSet (sorted by name using Comparator):");
        for (Student s : studentsByName) {
            System.out.println(s);
        }

        // To handle duplicates with same name but different other attributes in TreeSet,
        // the Comparator needs to implement a tie-breaking rule,
        // or the Student class's compareTo (if Comparable) needs to be more comprehensive.
    }
}

Sorting an Array

Java provides convenient ways to sort both arrays and lists using the java.util.Arrays and java.util.Collections utility classes, respectively.

Sorting an Array: java.util.Arrays.sort()

The Arrays.sort() method can sort primitive arrays and arrays of objects.

• Primitive Arrays: Sorts in ascending order.

• Object Arrays: Sorts based on the natural ordering of elements (if they implement Comparable) or by a provided Comparator.

public class ArraySortingExample {
    public static void main(String[] args) {
        // Sorting a primitive integer array
        int[] numbers = {5, 2, 8, 1, 9, 3};
        System.out.println("Original int array: " + Arrays.toString(numbers));
        Arrays.sort(numbers);
        System.out.println("Sorted int array: " + Arrays.toString(numbers));

        // Sorting a String array (natural ordering)
        String[] fruits = {"Banana", "Apple", "Orange", "Cherry"};
        System.out.println("\nOriginal String array: " + Arrays.toString(fruits));
        Arrays.sort(fruits);
        System.out.println("Sorted String array: " + Arrays.toString(fruits));

        // Sorting a custom object array using Comparable (Student class from earlier)
        Student[] studentsArray = {
                new Student("Alice", 103, 85.5),
                new Student("Bob", 101, 92.0),
                new Student("Charlie", 102, 78.0)
        };
        System.out.println("\nOriginal Student array: " + Arrays.toString(studentsArray));
        // Assumes Student implements Comparable<Student> by rollNumber
        Arrays.sort(studentsArray);
        System.out.println("Sorted Student array (by rollNumber): " + Arrays.toString(studentsArray));

        // Sorting a custom object array using Comparator
        Arrays.sort(studentsArray, new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                return s1.getName().compareTo(s2.getName());
            }
        });
        System.out.println("Sorted Student array (by name): " + Arrays.toString(studentsArray));

        // Using lambda for Comparator
        Arrays.sort(studentsArray, (s1, s2) -> Double.compare(s2.getMarks(), s1.getMarks()));
        System.out.println("Sorted Student array (by marks, descending): " + Arrays.toString(studentsArray));
    }
}

Sorting a List

Lists can be sorted using Collections.sort() or, since Java 8, directly using the sort() method available on the List interface itself.

• Collections.sort(List<T> list): Sorts the elements of the specified list into ascending order, according to the natural ordering of its elements. The elements must implement the Comparable interface.

• Collections.sort(List<T> list, Comparator<? super T> c): Sorts the elements of the specified list according to the order induced by the specified Comparator.

• List.sort(Comparator<? super E> c) (Java 8+): This is the default method added to the List interface. It sorts this list according to the order induced by the specified Comparator. This method is generally preferred for lists over Collections.sort() when a Comparator is needed, as it's more idiomatic and often more performant (as it can be optimized for specific list implementations). If you want to use natural ordering, you can pass null or Comparator.naturalOrder().

Thread-Safe Collections

Java provides several approaches for thread-safe collections:

1. Synchronized Wrappers (from java.util.Collections): These methods return a synchronized (thread-safe) version of an existing collection. Every method call to the collection is synchronized on the collection itself. While they ensure thread-safety, they can become a performance bottleneck in high-concurrency scenarios because only one thread can access the collection at any given time.

• Collections.synchronizedList(List<T> list)

• Collections.synchronizedSet(Set<T> set)

• Collections.synchronizedMap(Map<K, V> map)

• Collections.synchronizedCollection(Collection<T> c)

2. Concurrent Collections (from java.util.concurrent): These classes are specifically designed for high-performance concurrent access. They use more sophisticated locking mechanisms (like fine-grained locking or lock-free algorithms) to allow multiple threads to read and write concurrently with minimal contention.

   • ConcurrentHashMap: A highly efficient, scalable, and thread-safe alternative to HashMap. It allows concurrent reads and concurrent writes to different parts of the map without locking the entire map.

   • CopyOnWriteArrayList: A thread-safe variant of ArrayList where all mutative operations (add, set, remove, etc.) create a fresh copy of the underlying array. Reads do not require synchronization and are therefore very fast. Suitable for lists that are modified infrequently but are read frequently.

   • CopyOnWriteArraySet: Similar to CopyOnWriteArrayList, backed by a CopyOnWriteArrayList.

   • ConcurrentLinkedQueue: An unbounded, thread-safe, non-blocking queue. Elements are added to the tail and removed from the head.

   • LinkedBlockingQueue: A thread-safe, optionally bounded, blocking queue. It supports put() and take() methods that block if the queue is full or empty, respectively.

   • ConcurrentSkipListMap: A scalable concurrent ConcurrentNavigableMap implementation, often used as a concurrent alternative to TreeMap.

   • ConcurrentSkipListSet: A scalable concurrent ConcurrentNavigableSet implementation, often used as a concurrent alternative to TreeSet.

   Choosing the Right Thread-Safe Collection:

   • Synchronized Wrappers: Simple to use, good for occasional concurrent access or when you need to make an existing collection thread-safe quickly. Can be a bottleneck.

   • Concurrent Collections: Preferred for high-concurrency scenarios, offering better performance and scalability. Choose based on specific access patterns (e.g., CopyOnWriteArrayList for read-heavy lists, ConcurrentHashMap for frequent reads/writes to map).

   How ConcurrentHashMap works internally? https://dzone.com/articles/how-concurrenthashmap-works-internally-in-java 

        How CopyOnWriteArrayList works internally: https://javatrainingschool.com/copyonwritearraylist-and-copyonwritearrayset/

Useful HashMap Methods

Method	Description
getOrDefault()	Gets value or default if absent.
putIfAbsent()	Puts only if key is missing or is mapped to null.
compute()	Recomputes value based on key. Useful for updating a value based on its existing value. If the remappingFunction returns null, the mapping is removed.
computeIfAbsent()	Computes only if key not present or is mapped to null, Useful for lazy initialization of values.
merge()	Combines existing and new values. remappingFunction can be pass for conflicts.
replaceAll()	Applies function to all entries.

Useful Collections Methods

Method	Use Case
Collections.nCopies(n, val)	Returns an immutable list consisting of n copies of the specified object. This is memory-efficient as it doesn't actually create n copies of the object; it just returns a list that behaves as if it contains them.
Collections.frequency(list, val)	Frequency of val
Collections.disjoint(list1, list2)	Returns true if the two specified collections have no elements in common.
Collections.singleton(val) /singletonList(val) /singletonMap(val)	Returns an immutable set, list, or map containing only the specified element/entry. Useful for methods that require a collection but you only have a single item.
Collections.rotate(list, distance)	Rotates the elements in the specified list by the specified distance.

Practice Programs

1. Reverse a list using Collections.reverse()

2. Remove duplicates using HashSet

3. Sort list of objects using Comparable

4. Custom sort using Comparator

5. Count word frequencies using HashMap

6. Find common elements using retainAll()

7. Use TreeSet for automatic sorting

8. Implement LRU Cache using LinkedHashMap

9. Group anagrams using Map<String, List<String>>

10. Thread-safe counter using ConcurrentHashMap

Also Read:

• Best practices: https://www.youtube.com/watch?v=kI7mYQwjqx4
• Choosing the right collection: https://www.baeldung.com/java-choose-list-set-queue-map

End