Prior to the introduction of the Collections framework in JDK 1.2, you would’ve used Arrays and Vectors to store and manage a group of objects. But they had their own share of drawbacks.

The Java Collections Framework aims to overcome these issues by providing high-performance implementations of common data structures. These allow you to focus on writing the application logic instead of focusing on low-level operations.

Then, the introduction of Generics in JDK 1.5 significantly improved the Java Collections Framework. Generics let you enforce type safety for objects stored in a collection, which enhances the robustness of your applications. You can read more about Java Generics here.

In this article, I will guide you through how to use the Java Collections Framework. We’ll discuss the different types of collections, such as Lists, Sets, Queues, and Maps. I’ll also provide a brief explanation of their key characteristics such as:

• Internal mechanisms

• Handling of duplicates

• Support for null values

• Ordering

• Synchronization

• Performance

• Key methods

• Common implementations

We’ll also walk through some code examples for better understanding, and I’ll touch on the Collections utility class and its usage.

Table of Contents:

1. Understanding the Java Collections Framework

   • Collection Interfaces

   • Decoding the Java Collections Framework Hierarchy

   • A Closer Look at Collection Interfaces

2. Java Collection Interfaces

   • Lists

   • Sets

   • Queues

   • Maps

3. Collections Utility Class

4. Conclusion

Understanding the Java Collections Framework

According to the Java documentation, “A collection is an object that represents a group of objects. A collections framework is a unified architecture for representing and manipulating collections.”

In simple terms, the Java Collections Framework helps you manage a group of objects and perform operations on them efficiently and in an organized way. It makes it easier to develop applications by offering various methods to handle groups of objects. You can add, remove, search, and sort objects effectively using the Java Collections Framework.

Collection Interfaces

In Java, an interface specifies a contract that must be fulfilled by any class that implements it. This means the implementing class must provide concrete implementations for all the methods declared in the interface.

In the Java Collections Framework, various collection interfaces like Set, List, and Queue extend the Collection interface, and they must adhere to the contract defined by the Collection interface.

Decoding the Java Collections Framework Hierarchy

Check out this neat diagram from this article that illustrates the Java Collection Hierarchy:

We’ll start from the top and work down so you can understand what this diagram is showing:

1. At the root of the Java Collections Framework is the Iterable interface, which lets you iterate over the elements of a collection.

2. The Collection interface extends the Iterable interface. This means it inherits the properties and behavior of the Iterable interface and adds its own behavior for adding, removing, and retrieving elements.

3. Specific interfaces such as List, Set, and Queue further extend the Collection interface. Each of these interfaces has other classes implementing their methods. For example, ArrayList is a popular implementation of the List interface, HashSet implements the Set interface, and so on.

4. The Map interface is part of the Java Collections Framework, but it does not extend the Collection interface, unlike the others mentioned above.

5. All the interfaces and classes in this framework are part of the java.util package.

Note: A common source of confusion in the Java Collections Framework revolves around the difference between Collection and Collections. Collection is an interface in the framework, while Collections is a utility class. The Collections class provides static methods that perform operations on the elements of a collection.

Java Collection Interfaces

By now, you’re familiar with the different types of collections that form the foundation of the collections framework. Now we’ll take a closer look at the List, Set, Queue, and Map interfaces.

In this section, we'll discuss each of these interfaces while exploring their internal mechanisms. We'll examine how they handle duplicate elements and whether they support the insertion of null values. We'll also understand the ordering of elements during insertion and their support for synchronization, which deals with the concept of thread safety. Then we’ll walk through a few key methods of these interfaces and conclude by reviewing common implementations and their performance for various operations.

Before we begin, let's talk briefly about Synchronization and Performance.

• Synchronization controls access to shared objects by multiple threads, ensuring their integrity and preventing conflicts. This is crucial for maintaining thread safety.

• When choosing a collection type, one important factor is its performance during common operations like insertion, deletion, and retrieval. Performance is usually expressed using Big-O notation. You can learn more about it here.

Lists

A List is an ordered or sequential collection of elements. It follows zero-based indexing, allowing the elements to be inserted, removed, or accessed using their index position.

1. Internal mechanism: A List is internally supported by either an array or a linked list, depending on the type of implementation. For example, an ArrayList uses an array, while a LinkedList uses a linked list internally. You can read more about LinkedList here. A List dynamically resizes itself upon the addition or removal of elements. The indexing-based retrieval makes it a very efficient type of collection.

2. Duplicates: Duplicate elements are allowed in a List, which means there can be more than one element in a List with the same value. Any value can be retrieved based on the index at which it is stored.

3. Null: Null values are also allowed in a List. Since duplicates are permitted, you can also have multiple null elements.

4. Ordering: A List maintains insertion order, meaning the elements are stored in the same order they are added. This is helpful when you want to retrieve elements in the exact order they were inserted.

5. Synchronization: A List is not synchronized by default, which means it doesn't have a built-in way to handle access by multiple threads at the same time.

6. Key methods: Here are some key methods of a List interface: add(E element), get(int index), set(int index, E element), remove(int index), and size(). Let's look at how to use these methods with an example program.

    import java.util.ArrayList;
    import java.util.List;
   
    public class ListExample {
        public static void main(String[] args) {
            // Create a list
            List<String> list = new ArrayList<>();
   
            // add(E element)
            list.add("Apple");
            list.add("Banana");
            list.add("Cherry");
   
            // get(int index)
            String secondElement = list.get(1); // "Banana"
   
            // set(int index, E element)
            list.set(1, "Blueberry");
   
            // remove(int index)
            list.remove(0); // Removes "Apple"
   
            // size()
            int size = list.size(); // 2
   
            // Print the list
            System.out.println(list); // Output: [Blueberry, Cherry]
   
            // Print the size of the list
            System.out.println(size); // Output: 2
        }
    }
   

7. Common implementations: ArrayList, LinkedList, Vector, Stack

8. Performance: Typically, insert and delete operations are fast in both ArrayList and LinkedList. But fetching elements can be slow because you have to traverse through the nodes.

Sets

A Set is a type of collection that does not allow duplicate elements and represents the concept of a mathematical set.

1. Internal mechanism: A Set is internally backed by a HashMap. Depending on the implementation type, it is supported by either a HashMap, LinkedHashMap, or a TreeMap. I have written a detailed article about how HashMap works internally here. Be sure to check it out.

2. Duplicates: Since a Set represents the concept of a mathematical set, duplicate elements are not allowed. This ensures that all elements are unique, maintaining the integrity of the collection.

3. Null: A maximum of one null value is allowed in a Set because duplicates are not permitted. But this does not apply to the TreeSet implementation, where null values are not allowed at all.

4. Ordering: Ordering of elements in a Set depends on the type of implementation.

   • HashSet: Order is not guaranteed, and elements can be placed in any position.

   • LinkedHashSet: This implementation maintains the insertion order, so you can retrieve the elements in the same order they were inserted.

   • TreeSet: Elements are inserted based on their natural order. Alternatively, you can control the insertion order by specifying a custom comparator.

5. Synchronization: A Set is not synchronized, meaning you might encounter concurrency issues, like race conditions, which can affect data integrity if two or more threads try to access a Set object simultaneously

6. Key methods: Here are some key methods of a Set interface: add(E element), remove(Object o), contains(Object o), and size(). Let's look at how to use these methods with an example program.

    import java.util.HashSet;
    import java.util.Set;
   
    public class SetExample {
        public static void main(String[] args) {
            // Create a set
            Set<String> set = new HashSet<>();
   
            // Add elements to the set
            set.add("Apple");
            set.add("Banana");
            set.add("Cherry");
   
            // Remove an element from the set
            set.remove("Banana");
   
            // Check if the set contains an element
            boolean containsApple = set.contains("Apple");
            System.out.println("Contains Apple: " + containsApple);
   
            // Get the size of the set
            int size = set.size();
            System.out.println("Size of the set: " + size);
        }
    }
   

7. Common implementations: HashSet, LinkedHashSet, TreeSet

8. Performance: Set implementations offer fast performance for basic operations, except for a TreeSet, where the performance can be relatively slower because the internal data structure involves sorting the elements during these operations.

Queues

A Queue is a linear collection of elements used to hold multiple items before processing, usually following the FIFO (first-in-first-out) order. This means elements are added at one end and removed from the other, so the first element added to the queue is the first one removed.

1. Internal mechanism: The internal workings of a Queue can differ based on its specific implementation.

   • LinkedList – uses a doubly-linked list to store elements, which means you can traverse both forward and backward, allowing for flexible operations.

   • PriorityQueue – is internally backed by a binary heap, which is very efficient for retrieval operations.

   • ArrayDeque – is implemented using an array that expands or shrinks as elements are added or removed. Here, elements can be added or removed from both ends of the queue.

2. Duplicates: In a Queue, duplicate elements are permitted, allowing multiple instances of the same value to be inserted

3. Null: You cannot insert a null value into a Queue because, by design, some methods of a Queue return null to indicate that it is empty. To avoid confusion, null values are not allowed.

4. Ordering: Elements are inserted based on their natural order. Alternatively, you can control the insertion order by specifying a custom comparator.

5. Synchronization: A Queue is not synchronized by default. But, you can use a ConcurrentLinkedQueue or a BlockingQueue implementation for achieving thread safety.

6. Key methods: Here are some key methods of a Queue interface: add(E element), offer(E element), poll(), and peek(). Let's look at how to use these methods with an example program.

    import java.util.LinkedList;
    import java.util.Queue;
   
    public class QueueExample {
        public static void main(String[] args) {
            // Create a queue using LinkedList
            Queue<String> queue = new LinkedList<>();
   
            // Use add method to insert elements, throws exception if insertion fails
            queue.add("Element1");
            queue.add("Element2");
            queue.add("Element3");
   
            // Use offer method to insert elements, returns false if insertion fails
            queue.offer("Element4");
   
            // Display queue
            System.out.println("Queue: " + queue);
   
            // Peek at the first element (does not remove it)
            String firstElement = queue.peek();
            System.out.println("Peek: " + firstElement); // outputs "Element1"
   
            // Poll the first element (retrieves and removes it)
            String polledElement = queue.poll();
            System.out.println("Poll: " + polledElement); // outputs "Element1"
   
            // Display queue after poll
            System.out.println("Queue after poll: " + queue);
        }
    }
   

7. Common implementations: LinkedList, PriorityQueue, ArrayDeque

8. Performance: Implementations like LinkedList and ArrayDeque are usually quick for adding and removing items. The PriorityQueue is a bit slower because it inserts items based on the set priority order.

Maps

A Map represents a collection of key-value pairs, with each key mapping to a single value. Although Map is part of the Java Collection framework, it does not extend the java.util.Collection interface.

1. Internal mechanism: A Map works internally using a HashTable based on the concept of hashing. I have written a detailed article on this topic, so give it a read for a deeper understanding.

2. Duplicates: A Map stores data as key-value pairs. Here, each key is unique, so duplicate keys are not allowed. But duplicate values are permitted.

3. Null: Since duplicate keys are not allowed, a Map can have only one null key. As duplicate values are permitted, it can have multiple null values. In the TreeMap implementation, keys cannot be null because it sorts the elements based on the keys. However, null values are allowed.

4. Ordering: Insertion order of a Map varies on the implementation:

   • HashMap – the insertion order is not guaranteed as they are determined based on the concept of hashing.

   • LinkedHashMap – the insertion order is preserved and you can retrieve the elements back in the same order that they were added into the collection.

   • TreeMap – Elements are inserted based on their natural order. Alternatively, you can control the insertion order by specifying a custom comparator.

5. Synchronization: A Map is not synchronized by default. But you can use Collections.synchronizedMap() or ConcurrentHashMap implementations for achieving thread safety.

6. Key methods: Here are some key methods of a Map interface: put(K key, V value), get(Object key), remove(Object key), containsKey(Object key), and keySet(). Let's look at how to use these methods with an example program.

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Set;
   
    public class MapMethodsExample {
        public static void main(String[] args) {
            // Create a new HashMap
            Map<String, Integer> map = new HashMap<>();
   
            // put(K key, V value) - Inserts key-value pairs into the map
            map.put("Apple", 1);
            map.put("Banana", 2);
            map.put("Orange", 3);
   
            // get(Object key) - Returns the value associated with the key
            Integer value = map.get("Banana");
            System.out.println("Value for 'Banana': " + value);
   
            // remove(Object key) - Removes the key-value pair for the specified key
            map.remove("Orange");
   
            // containsKey(Object key) - Checks if the map contains the specified key
            boolean hasApple = map.containsKey("Apple");
            System.out.println("Contains 'Apple': " + hasApple);
   
            // keySet() - Returns a set view of the keys contained in the map
            Set<String> keys = map.keySet();
            System.out.println("Keys in map: " + keys);
        }
    }
   

7. Common implementations: HashMap, LinkedHashMap, TreeMap, Hashtable, ConcurrentHashMap

8. Performance: HashMap implementation is widely used mainly due to its efficient performance characteristics depicted in the below table.

Collections Utility Class

As highlighted at the beginning of this article, the Collections utility class has several useful static methods that let you perform commonly used operations on the elements of a collection. These methods help you reduce the boilerplate code in your application and lets you focus on the business logic.

Here are some key features and methods, along with what they do, listed briefly:

1. Sorting: Collections.sort(List<T>) – this method is used to sort the elements of a list in ascending order.

2. Searching: Collections.binarySearch(List<T>, key) – this method is used to search for a specific element in a sorted list and return its index.

3. Reverse order: Collections.reverse(List<T>) – this method is used to reverse the order of elements in a list.

4. Min/Max Operations: Collections.min(Collection<T>) and Collections.max(Collection<T>) – these methods are used to find the minimum and maximum elements in a collection, respectively.

5. Synchronization: Collections.synchronizedList(List<T>) – this method is used to make a list thread-safe by synchronizing it.

6. Unmodifiable Collections: Collections.unmodifiableList(List<T>) – this method is used to create a read-only view of a list, preventing modifications.

Here's a sample Java program that demonstrates various functionalities of the Collections utility class:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(3);
        numbers.add(8);
        numbers.add(1);

        // Sorting
        Collections.sort(numbers);
        System.out.println("Sorted List: " + numbers);

        // Searching
        int index = Collections.binarySearch(numbers, 3);
        System.out.println("Index of 3: " + index);

        // Reverse Order
        Collections.reverse(numbers);
        System.out.println("Reversed List: " + numbers);

        // Min/Max Operations
        int min = Collections.min(numbers);
        int max = Collections.max(numbers);
        System.out.println("Min: " + min + ", Max: " + max);

        // Synchronization
        List<Integer> synchronizedList = Collections.synchronizedList(numbers);
        System.out.println("Synchronized List: " + synchronizedList);

        // Unmodifiable Collections
        List<Integer> unmodifiableList = Collections.unmodifiableList(numbers);
        System.out.println("Unmodifiable List: " + unmodifiableList);
    }
}

This program demonstrates sorting, searching, reversing, finding minimum and maximum values, synchronizing, and creating an unmodifiable list using the Collections utility class.

Conclusion

In this article, you’ve learned about the Java Collections Framework and how it helps manage groups of objects in Java applications. We explored various collection types like Lists, Sets, Queues, and Maps and gained insight into some of the key characteristics and how each of these types supports them.

You learned about performance, synchronization, and key methods, gaining valuable insights into choosing the right data structures for your needs.

By understanding these concepts, you can fully utilize the Java Collections Framework, allowing you to write more efficient code and build robust applications.

If you found this article interesting, feel free to check out my other articles on freeCodeCamp and connect with me on LinkedIn.

In this article, I will introduce you to HashMaps in Java. We will explore the common operations of HashMap and then delve into how it operates internally. You will gain an understanding of the hash function and how index calculation takes place. Finally, we will look at the time complexities of the operations and touch upon the behavior in a concurrent environment.

What is a HashMap in Java?

A HashMap implements the Map interface, which is part of the Java collection framework. It's based on the concept of Hashing.

Hashing is a technique that transforms an input of arbitrary size into a fixed-size output using a hash function. The generated output is called the hash code and is represented by an integer value in Java. Hash codes are used for efficient lookup and storage operations in a HashMap.

Common Operations

Like we discussed above, data in a HashMap is stored in the form of key-value pairs. The key is a unique identifier, and each key is associated with a value.

Below are some common operations supported by a HashMap. Let's understand what these methods do with some simple code examples:

Insertion

• This method inserts a new key-value pair to the HashMap.

• The insertion order of the key-value pairs is not maintained.

• During insertion, if a key is already present, the existing value will be replaced with the new value that is passed.

• You can insert only one null key into the HashMap, but you can have multiple null values.

The method signature for this operation is given below, followed by an example:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

In the code above, we have a HashMap example where we add a key of type String and value of type Integer.

Retrieval:

• Fetches the value associated with a given key.

• Returns null if the key does not exist in the HashMap.

The method signature for this operation is given below, followed by an example:

public V get(Object key)

Integer value = map.get("apple"); // returns 1

In the code above, we're retrieving the value associated with the key apple.

Other common operations include:

• remove: Removes the key-value pair for the specified key. It returns null if the key is not found.

• containsKey: Checks if a specific key is present in the HashMap.

• containsValue: Checks if the specified value is present in the HashMap.

Internal Structure of a HashMap

Internally, a HashMap uses an array of buckets or bins. Each bucket is a linked list of type Node, which is used to represent the key-value pair of the HashMap.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Above, you can see the structure of the Node class which is used to store the key-value pairs of the HashMap.

The Node class has the following fields:

• hash: Refers to the hashCode of the key.

• key: Refers to the key of the key-value pair.

• value: Refers to the value associated with the key.

• next: Acts as a reference to the next node.

The HashMap is fundamentally based on a hash table implementation, and its performance depends on two key parameters: initial capacity and load factor. The original javadocs of the Hash table class define these two parameters as follows:

• The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.

• The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Let's now try and understand how the basic operations, put and get, work in a HashMap.

Hash Function

During the insertion (put) of a key-value pair, the HashMap first calculates the hash code of the key. The hash function then computes an integer for the key. Classes can use the hashCode method of the Object class or override this method and provide their own implementation. (Read about the hash code contract here). The hash code is then XORed (eXclusive OR) with its upper 16 bits (h >>> 16) to achieve a more uniform distribution.

XOR is a bitwise operation that compares two bits, resulting in 1 if the bits are different and 0 if they are the same. In this context, performing a bitwise XOR operation between the hash code and its upper 16 bits (obtained using the unsigned right shift >>> operator) helps to mix the bits, leading to a more evenly distributed hash code.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Above, you can see the static hash method of the HashMap class.

The idea is to have a unique hash code for each key, but the hash function could produce the same hash code for different keys. This leads to a situation known as a collision. We will see how to handle collisions in the next section.

Index Calculation

Once the hash code for a key is generated, the HashMap calculates an index within the array of buckets to determine where the key-value pair will be stored. This is done using a bitwise AND operation, which is an efficient way to calculate the modulo when the array length is a power of two.

int index = (n - 1) & hash;

Here, we're calculating the index where n is the length of the bucket array.

Once the index is calculated, the key is then stored at that index in the bucket array. However, if multiple keys end up having the same index, it causes a collision. In such a scenario, the HashMap handles it in one of two ways:

• Chaining/Linking: Each bucket in the array is a linked list of nodes. If a key already exists at a particular index and another key gets hashed to the same index, it gets appended to the list.

• Treeify: If the number of nodes exceeds a certain threshold, the linked list is converted into a tree (This was introduced in Java 8).

static final int TREEIFY_THRESHOLD = 8;

This is the threshold that determines treeification.

Therefore, it is essential to have a good hash function that uniformly distributes the keys across the buckets and minimizes the chances of collisions.

The retrieval (get) and deletion (remove) operations work similarly to the insertion (put) operation. Here's how:

• Retrieval (get): Computes the hash code using the hash function -> calculates the index using the hash code -> traverses the linked list or tree to find the node with the matching key.

• Deletion (remove): Computes the hash code using the hash function -> calculates the index using the hash code -> removes the node from the linked list or tree.

Time Complexity

The basic operations of a HashMap, such as put, get, and remove, generally offer constant time performance of O(1), assuming that the keys are uniformly distributed. In cases where there is poor key distribution and many collisions occur, these operations might degrade to a linear time complexity of O(n).

Under treeification, where long chains of collisions are converted into balanced trees, lookup operations can improve to a more efficient logarithmic time complexity of O(log n).

Synchronization

The HashMap implementation is not synchronized. If multiple threads access a HashMap instance concurrently and iterate over the map, and if any one of the threads performs a structural modification (such as adding or removing a key-value mapping) on the map, it leads to a ConcurrentModificationException.

To prevent this, you can create a thread-safe instance using the Collections.synchronizedMap method.

Conclusion

In summary, understanding the internal workings of a HashMap is crucial for developers to make informed decisions. Knowing how a key is mapped, how collisions happen, and how they can be avoided helps you use the HashMap efficiently and effectively.