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.
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 |
Queue Example | ArrayDeque |
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")); |
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); |
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.
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.
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.