Collections Framework

The Collections Framework relates to the grouping of objects, originally there were four classes (Dictionary, Vector, Stack and Properties), the newer frameworks now offer better performance, better interoperability and extending and/or adapting a collection had to be easy (the use of better interfaces) and finally standard arrays were better integrated into the Collections Framework.

Algorithms which are static are available for all collections and thus it does not need to implement its own version, they provide a standard way of manipluating collections. The Iterator interface offers a standard way to access the elements of a collection one at a time, each collection provides an iterator. Lastly each collection provides a spliterator which allows for parallel iteration. I also have a data structures section which uses the collection class for Lists, Stacks, Queues, etc.

I have already covered the for loop in my control statements section which allows the looping of collections very easily, also autoboxing/unboxing and generics where also incorporated in collections, in fact Generics plays a big part in collections which allows easy creation of collections of different types of objects.

There are a few basic operations you'll normally use with collections

There are seven core interfaces, plus collections can use Comparator, RandomAccess, Iterator, ListIterator and Spliterator interfaces.

Interface Methods

Each Collection interface has a number of methods that can be used on the collection, the Collection interface is at the top and thus all other interfaces inherit the methods, other interfaces will also inherit its superclass methods as well, below is a table of these methods grouped by the interfaces, this is a guide to what methods are avaiable and not the full syntax (see Java documentation for full usage)

Collection Interface
Method Description
add adds an object to the collection, some collection does not allow duplicates
addAll adds all elements of the passed collection to the collection
clear removes all elements to
contains returns True if passed object exists in collection
containsAll returns True if all elements in passed collection are in the collection
equals returns True if the invoking collection and passed object are equal
hashCode returns the hashcode for the collection
isEmpty returns True if collection is empty
iterator returns an iterator for the collection
parallelStream returns a Stream that uses the invoking collection as its source, some support parallel operations
remove removes one instance of the passed object from the collection
removeAll removes all instances of the passed object from the collection
removeIf removes from the invoking collection those elements that satisfy the condition specified by the predicate (lambda expression)
retainAll removes all elements from the collection that are not in the passed collection
size retun the number of elements
spliterator returns a spliterator of the collection
stream returns stream that uses the invoking collection as its source for elements
toArray returns an array of the elements from the collection, there is also a Generic version of this method
List Interface (extends Collection)
Method Description
add adds an element to the collection at the passed index position, all elements are shifted, none are deleted
addAll adds the passed collection of elemente to the collection at the passed index position, all elements are shifted, none are deleted
get retrieve the element at the passed index position
indexOf returns the index of the first instance of the passed object
lastIndexOf returns the index of the last instance of the passed object
listIterator returns a iterator which starts at index 0, there is another method where to can begin at a specific index
remove removes an element at the passed index position, the list is then compacted, nothing else is deleted
replaceAll updates each element with the value from the passed opToApply (UnaryOperator)
set assign the passed object at the passed specified index but return the old value
sort sorts the list using the passed Comparator
subList returns a list specified by the passed start and end index positions
Set Interface (extends Collection)
Method Description
No additional methods Duplicates are not allowed in Sets
SortedSet Interface
Method Description
comparator returns the invoking sorted sets comparator, if the natural ordering is used for this set null will be returned
first returns the first element in the sortedSet
headSet returns a SortedSet from index 0 to the passed end index position
last returns the last element in the sortedSet
subSet returns a SortSet specified by the passed start and end index positions
tailSet returns a SortSet greater and equal to the passed starting index position
NavigableSet Interface
Method Description
ceiling searches (and returns) the smallest element of the collection using the passed element
descendingIterator returns an iterator that moves from the greatest to the least.
descendingSet returns a NavigableSet that is the reverse of the invoking set
floor searches the set for the largest element of the passed object
headSet returns NavigableSet that includes all elements from the set that are less than the passed upperbound. There is an option to also include the equal elements
higher searches the set for the largest element than the passed object
lower searches the set for the smallest element than the passed object
pollFirst returns the first element removing the element in the process
pollLast returns the last element removing the element in the process
subSet returns a NavigableSet specified by the passed start and end index positions
tailSet returns a NavigableSet greater and equal to the passed starting index position
Queue Interface
Method Description
element returns the element at the head of the queue
offer attempts to add an element to the queue
peek returns the element at the head of the queue
poll returns the element at the had of the queue, removing the element in the process
remove removes the element at the head of the queue, returning the elemnt in the process
Deque Interface
Method Description
addFirst, addLast add passed element at head/tail of the deque
descendingIterator returns an iterator that moves from tail to head of the deque
getFirst, getLast returns first/last element in the deque
offerFirst, offerLast attepmts to add element at head/tail of deque
peekFirst, peekLast returns element at head/tail of the queue (does not remove)
pollFirst, pollLast returns element at head/tail of the queue and in the process removes element from the deque
pop, push pop returns element and removes it, push adds element to head of the deque
removeFirst, removeLast removes the element at head/tail of the deque
removeFirstOccurrence, removeLastOccurence removes the first/last occurrence of the passed element from the dequeue

There are a number of concrete classes, also you have the AbstractCollection class that implements most of the Collection interface

List Implementations (Collections Class) Set Implementations (Collections Class) Queue Implementations (Collections Class)
AbstractList AbstractSet AbstractQueue
AbstractSequentialList EnumSet ArrayDeque
LinkedList HashSet PriorityQueue
ArrayList LinkedHashSet
Vector TreeSet

The collections come in three basic flavors each having subflavors of Sorted, Unsorted, Ordered and Unordered

Ordered means that you iterate through the collection in a specific order (not random), for an example you would iterate through an array starting at index position 0, this does not means that the object you retrieve are in any sorted order.

Sorted means you retrieve the objects that are sorted naturally, what I mean here is Strings objects would be alphabetically ordered, int would be numerically ordered.

List (a list cares about the index)
ArrayList

Think of this as a growable array, it is a ordered collection (uses a index) but it is not sorted, this interface implements a RandomAccess interface

Choose this over a LinkedList when you need fast iteration but aren't as likely to be doing a lot of insertion and deletion

Vector

Vector and Hashtable were the original collections. A Vector is the same as a ArrayList but a Vector methods are synchronized for thread safety. Vectors also implement a RandomAccess interface.

Use a ArrayList if you don't need synchronization at it decreases performance.

LinkedList

LinkedList is ordered by index position, like ArrayList but doubly-linked up.

LinkedLists are ideal for stacks and queues, its also a good candidate for fast insertion and deletion

Set (a set cares about the uniqueness)
HashSet

A HashSet is an unsorted, unordered Set. It uses the hashcode of the object being inserted, so the better the hashcode the better performance you will get.

Use this when you want a collection with no duplicates and you don't really care about the order.

LinkedHashSet

A LinkedHashSet is an ordered version of a HashSet that maintains a doubly-linked List across all elements.

use this collection when you care about the order

TreeSet It uses a Red-Black tree structure that guarantees that elements will be in ascending order, according to the natural order of the elements (String would be a,b,c,d,etc , int would be 1,2,3,4), there will also be no duplicates.
EnumSet is specifically used for use with enums
Queue (can only access head/tail of the queue)
ArrayDeque

Creats a dynamic array and has no capacity restrictions

PriorityQueue

Creats a queue that is prioritized based on the queues comparator

Here are a few examples, one each for List, Set and Queue, you will notice that they are all very similiar and thats the idea regarding the Collection interface

List Example
ArrayList a1 = new ArrayList<>();
a1.add("A");
a1.add("B");
a1.add("C");
a1.add("D");

// Use an Iterator
Iterator<String> itr = a1.iterator();
System.out.print("Use Iterator: ");
while(itr.hasNext())
    System.out.print( itr.next() +  " ");
System.out.println();

// spliterator
Spliterator<String> spl1 = a1.spliterator();
System.out.print("Use spliterator: ");
while(spl1.tryAdvance( (n) -> System.out.print(n + " ")));                                     // notice the lambda expression
System.out.println();

// Use the new for-loop
System.out.print("Use for-loop: ");
for(String s : a1)
    System.out.print(s +  " ");
System.out.println();

// Get element
System.out.println("Use get() and size(): " + a1.get(0) +  " " + a1.get(a1.size() - 1));       // use get() and size() method

// Remove element
a1.remove(2);                                                                                  // remove 'C' element
System.out.print("Use remove(): ");
for(String s : a1)
    System.out.print(s +  " ");
System.out.println();

Note: output will be
    Use Iterator: A B C D 
    Use for-loop: A B C D
    Use spliterator: A B C D 
    Use get() and size(): A D
    Use remove(): A B D 
Set Example
HashSet hs1 = new HashSet<>();
hs1.add("Paul");
hs1.add("Will");
hs1.add("Moore");
hs1.add("Graham");

// Use Iterator
Iterator<String> itr = hs1.iterator();
System.out.print("Use Iterator: ");
while(itr.hasNext())                                        // there are no guarantees to ordering
    System.out.print( itr.next() +  " ");
System.out.println();

// Use new for-loop
System.out.print("Use for-loop: ");
for(String s : hs1)                                         // there are no guarantees to ordering
    System.out.print(s +  " ");
System.out.println();

// Get element
// There are no gets methods, you have to loop through the set and use equals

// Remove element
//String will = "Will";                                                 
hs1.remove("will");                                      // you can also pass other objects
System.out.print("Use remove(): ");
for(String s : hs1)
    System.out.print(s +  " ");
System.out.println();

Note: the ouptut will be
    Use Iterator: Moore Graham Will Paul 
    Use for-loop: Moore Graham Will Paul 
    Use remove(): Moore Graham Will Paul 
Queue Example
ArrayDeque ad1 = new ArrayDeque<>();
ad1.push("A");
ad1.push("B");
ad1.push("C");
ad1.push("D");

System.out.print("Pop the stack: ");

while(ad1.peek() != null)
    System.out.print(ad1.pop() + " ");
System.out.println();
System.out.println("Dequeue ad1 has now " + ad1.size() +  " elements");  // we have popped (removed) all the element

Note: the output will be
    Pop the stack: D C B A 
    Dequeue ad1 has now 0 elements

Maps

A map is an object that stores a key with its value (key/value pairs), using the key you can retrieve its value. Both key and values are objects, the keys must be unique, but values can be the same. Some maps can use both key/value as null, others cannot. One point to make is that you cannot iterate over them, they don't implement the iterable interface, I will show you an example on how you can iterate through a map later. I cover how maps work in detail (including collisions) in my data structures section.

The below interfaces support Maps

Interface Description
Map maps unique keys to values
Map.Entry describes an element in a map, this is an inner class of map
SortedMap maintains keys in ascending order
NavigableMap extends SortMap to handle retrieval of entries based on closest-match searches

The methods of each are below

Map Interface
Method Description
clear removes all key/value pairs from the map
compute, computeIfAbsent, computeIfPresent you can pass in lambda expressions and return key/value pairs
containsKey, containsValue returns True/False if key or value is contained in map
entrySet returns a Set that contains the entries in the map
equals returns True if maps are the same otherwise False
forEach executes action on each element in the map
get returns value of the key passed
hashCode returns maps hashcode
isEmpty returns True if map is empty, otherwise False
keySet returns a Set of all the maps keys
merge merge a key/pair into the map using a lambda expression
put, putAll, putIfAbsent puts a entry into the map in the passed key location
remove removes an element from the passed key location
replace, replaceAll if passed key is present, replace with new value
size returns the numbers of key/value pairs in the map
values returns a collection contains all the values in the map
NavigableMap Interface
Method Description
comparator returns the maps comparator
firstKey, lastKey returns either the first key or the last key of the map
headMap, subMap, tailMap return a SortedMap of various elements determines by the method and parameters passed
ceilingEntry, ceilingKey search for smallest key in map
descendingKeySet returns a NavigableSet that contains the keys in reverse order
descendingMap returns a NavigableMap that contains the reverse of the map
firstEntry, floorEntry, floorKey either returns the first entry in the map, or the largest entry
headMap returns a NavigableMap that have keys that are less then the upperbound that is passed
higherEntry, higherKey searches the map for the largest key
lastEntry, lowerEntry, lowerKey returns the last entry or the largest key
navigableKeySet returns a NavigableSet that contains the keys
pollFirstEntry, pollLastEntry returns either the first entry or last entry and removes it in the process
subMap, tailMap returns a NavigableMap of all key/values that are greater than the upperbound/lowerbounds passed
Map.Entry Interface
Method Description
equals returns True if passed object is a Map.Entry whose key/value are equal to the invoking object
getKey returns the key for this map entry
getValue returns the value for this map entry
hashCode returns the hashcode
setValue sets the value for this map entry to the passed value.

There a number of Map classes as per below

Map Implementations (Collections Class)
AbstractMap
EnumMap
HashMap
TreeMap
WeakHashMap (weak keys)
LinkedHashMap (allow insertion-order iterations)
IdentityHashMap (uses references equality when comparing documents)

Here are a few examples, you will notice that they are all very similiar and thats the idea regarding the Collection interface

HashMap Example
HashMap<String, Integer> hm1 = new HashMap<>();

hm1.put("Paul", 1);
hm1.put("Will", 2);
hm1.put("Moore", 3);
hm1.put("Graham", 4);

// Using for-loop
// you can also use KeySet() to get keys or values() to obtain values
for(Map.Entry<String, Integer> me : hm1.entrySet())
    System.out.println("Key: " + me.getKey() + "\t\tValue: " + me.getValue());
System.out.println();

// using iterators
Iterator<Map.Entry<String, Integer>> itr = hm1.entrySet().iterator();
while(itr.hasNext())
{
    Map.Entry<String, Integer> me = itr.next();
    System.out.println("Key: " + me.getKey() + "\t\tValue: " + me.getValue());
}

// Change a value of a specified key
System.out.println("\nPaul's value : " + hm1.get("Paul"));
hm1.put("Paul", 5);
System.out.println("\nPaul's value : " + hm1.get("Paul"));
Concurrent Map example
package uk.co.datadisk;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

class FirstWorker3 implements Runnable {

    private ConcurrentMap<String, Integer> map;

    public FirstWorker3(ConcurrentMap<String, Integer> map) {
        this.map = map;
    }

    @Override
    public void run() {
        try {
            map.put("B",1);
            map.put("H",2);
            map.put("F",3);
            Thread.sleep(1000);
            map.put("A",4);
            Thread.sleep(1000);
            map.put("E",5);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class SecondWorker3 implements Runnable {

    private ConcurrentMap<String, Integer> map;

    public SecondWorker3(ConcurrentMap<String, Integer> map) {
        this.map = map;
    }

    @Override
    public void run() {
        try {
            Thread.sleep(5000);
            System.out.println(map.get("A"));
            Thread.sleep(1000);
            System.out.println(map.get("E"));
            Thread.sleep(1000);
            System.out.println(map.get("C"));
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

public class ConcurrentMap1 {

    public static void main(String[] args) {

        ConcurrentMap<String, Integer> map = new ConcurrentHashMap<>();

        FirstWorker3 firstWorker = new FirstWorker3(map);
        SecondWorker3 secondWorker = new SecondWorker3(map);

        new Thread(firstWorker).start();
        new Thread(secondWorker).start();

    }
}
TreeMap Example
TreeMap<String, Integer> tm1 = new TreeMap<>();

tm1.put("Paul", 1);
tm1.put("Will", 2);
tm1.put("Moore", 3);
tm1.put("Graham", 4);

// Using for-loop
// you can also use KeySet() to get keys or values() to obtain values
for(Map.Entry<String, Integer> me : tm1.entrySet())
    System.out.println("Key: " + me.getKey() + "\t\tValue: " + me.getValue());
System.out.println();

// using iterators
Iterator<Map.Entry<String, Integer>> itr = tm1.entrySet().iterator();
while(itr.hasNext())
{
    Map.Entry<String, Integer> me = itr.next();
    System.out.println("Key: " + me.getKey() + "\t\tValue: " + me.getValue());
}

// Change a value of a specified key
System.out.println("\nPaul's value : " + tm1.get("Paul"));
tm1.put("Paul", 5);
System.out.println("\nPaul's value : " + tm1.get("Paul"));

Comparable

You can implement the comparable interface which can be used to sort (order) a group of related Objects

Comparable example
public class Book implements Comparable<Book> {

    private String authorName;
    private String title;
    private int numOfPages;

    public Book(String authorName, String title, int numOfPages) {
        this.authorName = authorName;
        this.title = title;
        this.numOfPages = numOfPages;
    }

    // Getters and Setters ....

    public int getNumOfPages() {
        return numOfPages;
    }

    @Override
    public String toString() {
        return this.authorName + "-" + this.title + "-" + this.numOfPages;
    }

    @Override
    public int compareTo(Book otherBook) {
        // return Integer.compare(this.numOfPages, otherBook.getNumOfPages());    // ASCENDING
        return -Integer.compare(this.numOfPages, otherBook.getNumOfPages());      // DESCENDING
    }
}

// Code to be used in main
List<Book> books = new ArrayList<>();

books.add(new Book("Will Hay","title1",223));
books.add(new Book("Moore Marriot","title2",33));
books.add(new Book("Graham Moffatt","title3",891));
books.add(new Book("Arthur Askey","title4",34));

// Sorting by number of pages
Collections.sort(books);             // will use the compareTo() method in the Book class

System.out.println(books);

Comparator

Both TreeSet and TreeMap elements are stored in sorted order, the comparator determines the sort order, by default natural ordering is used (alphabet, numbering order, etc), however you can define your own Comparator when you construct the set or map.

Below is a table showing the difference between comparable and comparator

Comparable Comparator
Single sorting sequence, we can sort the collection on the basis of a single element such as id, name, price, etc multiple storting sequences, we can sort the collection on the basis of multiple elements such as id, name, price, etc
affects the orignal class, you need to implement compareTo() method does not affect the original class
uses the compareTo() method uses the compare() method
present in java.lang present in java.util
use Collections.sort(List) use Collections.sort(List, Comparator)

Now for some examples

Comparator Example
// Create a Comparator class
class MyComparator implements Comparator<String> {

    // You can code any ordering you like in the compare method, it returns either 1 (greater than), 0 (equal), -1 (less than)
    public int compare(String aStr, String bStr) {
        return bStr.compareTo(aStr);
    }
}

// Code to be used in main

// Create a TreeSet which is not in order, however natural ordering will be used
        TreeSet<String> ts1 = new TreeSet<>();
        ts1.add("E");
        ts1.add("B");
        ts1.add("D");
        ts1.add("A");
        ts1.add("C");

        System.out.print("Set Values: ");
        for(String s: ts1)
            System.out.print(s + " ");
        System.out.println();

        // Create a TreeSet that will use our own Comparator class
        TreeSet<String> ts2 = new TreeSet<>(new MyComparator());
        ts2.add("E");
        ts2.add("B");
        ts2.add("D");
        ts2.add("A");
        ts2.add("C");

        System.out.print("Set Values: ");
        for(String s: ts2)
            System.out.print(s + " ");
        System.out.println();

Collection Algorithms and Legacy Classes

There are a number of algorithms that can be used by collections and maps, they are static methods within the Collection class, I am not going to cover all of these but commonly used ones are binarySearch, copy, list, reverse, shufflesort, various synchronized methods.

There are number of legacy Classes and interfaces again I am just going to mention them in case you see them in the wild.

Which one to Use

So now that we have had a look at the Collection class which one do you use, let have a quick recap on whats available and if they are ordered and sorted.

A quick reference regarding collections

Class
Map
Set
List
Ordered
Sorted
HashMap
X
No
No
Hashtable
X
No
No
TreeMap
X
Sorted
By natural order or custom comparison rules
LinkedHashMap
X
By insertion order or last access order
No
HashSet
X
No
No
TreeSet
X
Sorted
By natural order or custom comparison rules
LinkedHashSet
X
By insertion order or last access order
No
ArrayList
X
By Index
No
Vector
X
By Index
No
LinkedList
X
By Index
No

So which one to use, I obtained from the internet (URL no longer works) a diagram to explain which Collection or Map you should use, but also test the choosen one to make sure the performance is also within your limits, remember it's very easy to swap from one class to another due to the way the Collection framework works.