6.1 Collection UsageHomepage  « Java6 Certification « 6.1 Collection Usage

In our first lesson within this section we look at the various types of collections and their corresponding interfaces and which type of collection is suitable for specific types of data. We then look at usage of the Comparable interface.

Lets take a look at the points outlined at the Oracle Website for this part of the certification.

  • Section 6: Collections / Generics

    • Given a design scenario, determine which collection classes and/or interfaces should be used to properly implement that design, including the use of the Comparable interface.

The table below lists the concrete implementation classes of the various collection types and utilities that are covered on the site. Click a link to go to detailed information about a particular class:

Collection Types/Utilities & Concrete Implementation Classes
Collection Hierarchy Map Hierarchy Utilities Hierarchy
ListsQueuesSetsMapsUtilities
ArrayListPriorityQueueHashSetHashMapArrays
VectorLinkedHashSetHashtableCollections
LinkedListTreeSetLinkedHashMap
TreeMap

The table above shows we have two utility classes for use with collections as well as four collection types, these being lists, maps, queues and sets. Each collection type can be further divided by whether it is ordered and unsorted, or both sorted and ordered or finally both unsorted and unordered. Ordered collections allow us to iterate over our collections in a specific pre-determined way. Sorted collections are ordered according to the sort order and as such the ordering is defined by the sorting rules. This is the reason we can't have sorted unordered collections, as the sort order implicitly defines the ordering; but we can have ordered collections that are unsorted.

The sort order is derived from properties within the objects being sorted and can be based on natural ordering such as alphabetically or numerically or in a bespoke order as defined by the programmer. We will expand on the last paragraph when we look at the sorted collection types the terminology applies to as we work through the section.

There is quite a lot of information to assimilate when using collections so lets look at some hierarchy diagrams to clarify the points made so far and give an overview of what's to come:

Collection Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the Collection hierarchy and covers the interfaces and classes studied in the Java section. The diagram has several interfaces missing and also the java.util.EnumSet<E> and java.util.Stack<E> concrete implemetations which are not covered on the site, but should help in visualisation:

collection hierarchy

Collection Interfaces & Classesgo to top of page Top

The table below gives a description of each interface and class within the above diagram. Click a link to go to detailed information about a particular class:

Interface/Class Description
Collection<E>The root interface in the Collection hierarchy which the List<E>, Queue<E> and Set<E> interfaces extend. There is no direct implementation of the Collection<E> interface within the JDK.
List<E>Interface for ordered collections of elements.
Queue<E>Interface for holding elements prior to processing.
Set<E>Interface for unique collections of elements.
ArrayList<E>Random access, resizable-array implementation of the List<E> interface that implements all optional list operations and permits all elements, including null.
Vector<E>Synchronized random access resizable-array implementation of the List<E> interface.
LinkedList<E>Sequential access linked implementation of the List<E> interface that implements all optional list operations, and permits all elements, including null. The class also implements the Queue<E> interface, providing first-in-first-out queue operations.
PriorityQueue<E>Unbounded priority queue implementation of the Queue<E> interface based on a priority heap that does not permit null elements.
HashSet<E>Implementation of the Set<E> interface using a HashMap instance.
LinkedHashSet<E>Hash table and linked list implementation of the Set<E> interface that implements all optional set operations and permits all elements, including null.
SortedSet<E>Interface for unique collections of sorted elements.
TreeSet<E>Implementation of the Set<E> interface using a TreeMap instance.

Collection Types and Orderinggo to top of page Top

The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:

Collection Type Ordering
ListsQueuesSetsOrderedSorted
ArrayList<E>By the indexNo
Vector<E>By the indexNo
LinkedList<E>By the indexNo
PriorityQueue<E>SortedPIPO
HashSet<E>NoNo
LinkedHashSet<E>By insertion orderNo
TreeSet<E>SortedNatural/bespoke order

Setsgo to top of page Top

So what type of collection is a Set? A Set doesn't allow duplicates so every entry within a Set must be unique and as the name implies the interface models the mathematical set abstraction. In practical terms this means that we can never have more than one element within the Set referencing the same object or more than one element within the Set referencing two objects that are considered equal. See the Checking Object Equality section from the OO Concepts - The Object Superclass section of the site for a reminder of what constitutes object equality. We can also only have a maximum of one entry within the set with a value of null.

HashSetsgo to top of page Top

A HashSet is an unordered and unsorted implementation of the Set<E> interface, backed by a hash table using a HashMap instance. This type of set makes no guarantees over iteration order and in particular no guarantees that the iteration order will remain constant over time.

The hashcode of the object being inserted into the collection is used so the more efficient your override of the hashCode() method of the Object class is, the more efficient the HashSet. This also means that if you want to find out if an object exists within the set, or you want to delete an object from the set, then you need a reference to the object in question.

This type of set is a good choice when you want a collection with no duplicates and fast access and the order doesn't matter when iterating over it.

See HashSets for example code.

LinkedHashSetsgo to top of page Top

A LinkedHashSet is a Hash table and linked list implementation of the Set interface with predictable iteration order and differs from a HashSet by maintaintaining a doubly-linked list running through all of its elements. The linked list defines the iteration order of a LinkedHashSet by the order in which elements are inserted into the set.

This type of set is a good choice when you want a collection with no duplicates and fast access and you want to maintain an insertion order when iterating over it.

See LinkedHashSets for example code.

TreeSetsgo to top of page Top

A TreeSet is a sorted implementation of the Set<E> interface, backed by a TreeMap instance. This type of set guarantees that the set will be sorted in ascending order, according to the natural order of the elements contained within it, or by a custom comparator/comparable, dependant upon the type of constructor used on creation.

The ordering maintained by a set whether through natural order of the elements contained within it or by a custom comparator/comparable, must be consistent with the equals() method override rules of the Object class if it is to correctly implement the Set<E> interface and obey the rules of equality.

This type of set is a good choice when you want a sorted collection with no duplicates with the option of custom sorting.

See TreeSets for example code.

Listsgo to top of page Top

So what type of collection is a List? Lists are ordered collections that use an index for the ordering of the elements within the collection. As such lists have methods for the index that you don't find in other collection types within the The Collections Framework. An element is added to a list by specifying the index position or to the end of the list when no index is specified.

ArrayListsgo to top of page Top

An ArrayList is a resizable-array, ordered implementation of the List<E> interface that permits all elements including null. ArrayList allows random access to elements and is similar to Vector apart from being unsynchronized.

This type of list is a good choice when you want fast access and iteration but are not doing a lot of insertions and deletions.

See ArrayLists for example code.

Vectorsgo to top of page Top

A Vector is a resizable-array, ordered implementation of the List<E> interface that permits all elements including null. Vector allows random access to elements and is similar to ArrayList apart from being synchronized. In fact Vector is one of the two original collections shipped with Java, the other being Hashtable. Vector was retrofitted to implement List<E> interface, so that it became a part of The Collections Framework when the framework was introduced in version 1.2.

There is no sound reason since the introduction of the ArrayList<E> class to use the Vector<E> class. If you need an ArrayList to be synchronized this can be achieved using methods of the Collections class without all the overheads of using Vector<E> synchronized methods.

See Vectors for example code.

LinkedListsgo to top of page Top

A LinkedList is an ordered implementation of the List<E> interface that is accessed sequentialy using a doubly-linked list running through all of its elements. Because of this, the sequential access and the fact that the LinkedList<E> class also implements the Queue<E> interface, there are methods unique to this type of List.

This type of list is a good choice when you are doing a lot of insertions and deletions and because of the implementation of the Queue<E> interface is also a good candidate for stacks and queues.

See LinkedLists for example code.

Queuesgo to top of page Top

So what type of collection is a Queue? A Queue is an ordered list of actions that are to be processed and as such does not allow null elements. Typically, a Queue would be in FIFO (first-in, first-out) order although other orders such as LIFO (last-in, first-out), natural-ordering and custom comparator order are also possible.

PriorityQueuesgo to top of page Top

A PriorityQueue is a sorted, ordered implementation of the Queue<E> interface that permits all elements except null. A PriorityQueue queue is ordered in PIPO (priority-in, priority-out) order. This is achieved by natural order or a custom comparator to do the sorting and elements sorted first get the highest priority, in other words the ordering of the elements represents their priority within the queue.

See PriorityQueues for example code.

Map Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the Map hierarchy and covers the interfaces and classes studied in the Java section. The diagram has several interfaces missing and also the java.util.WeakHashMap<K,V> and java.util.IdentityHashMap<K,V> concrete implemetations which are not covered on the site, but should help in visualisation:

map hierarchy

Map Interfaces & Classesgo to top of page Top

The table below gives a description of each interface and class within the above diagram. Click a link to go to detailed information about a particular class:

Interface/Class Description
Map<K,V>The root interface in the map hierarchy which the SortedMap<K,V> interface extends.
HashMap<K,V>Hash table based implementation of the Map<K,V> interface that implements all optional map operations and permits all elements, including null and the null key.
LinkedHashMap<K,V>Hash table and linked list implementation of the Map<K,V> interface with predictable ordering and permits all elements, including null elements.
Hashtable<K,V>Hash table implementation of the Map<K,V> interface that doesn't allow null elements or null keys.
SortedMap<K,V>Interface for sorted map elements.
TreeMap<K,V>Random access tree based implementation of the SortedMap<K,V> interface.

Map Types and Orderinggo to top of page Top

The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:

Collection Type Ordering
MapOrderedSorted
HashMap<K,V>NoNo
LinkedHashMap<K,V>By insertion order or last access orderNo
Hashtable<K,V>NoNo
TreeMap<K,V>SortedBy natural order or bespoke order

Mapsgo to top of page Top

So what type of collection is a Map? Maps have unique identifiers as their keys which are mapped to a value, similar to key/value pairs in other languages. A Map doesn't allow duplicates keys so every entry within a Map must be unique. In practical terms this means that we can never have more than one element within the Map referencing the same object or more than one element within the Map referencing two objects that are considered equal. See the Checking Object Equality section from the OO Concepts - The Object Superclass section of the site for a reminder of what constitutes object equality. We can also only have a maximum of one entry within the set with a value of null.

Another feature of Map collection is how the Map<K,V> interface provides three different collection views, allowing us to view a map collection as a set of keys, a collection of values and as a set of key/value mappings.

HashMapgo to top of page Top

A HashMap is an unordered and unsorted implementation of the Map<K,V> interface that allows null values and a null key. This type of map makes no guarantees over iteration order and in particular no guarantees that the iteration order will remain constant over time.

The hashcode of the object being inserted into the collection is used so the more efficient your override of the hashCode() method of the Object class is, the more efficient the HashMap. This also means that if you want to find out if an object exists within the map, or you want to delete an object from the map, then you need a reference to the object in question.

This type of map is a good choice when you want a collection with no duplicates and fast access and the order doesn't matter when iterating over it.

See HashMap for example code.

LinkedHashMapsgo to top of page Top

A LinkedHashMap is a Hash table and linked list implementation of the Map<K,V> interface with predictable iteration order and differs from a HashSet by maintaintaining a doubly-linked list running through all of its elements. The linked list defines the iteration order of a LinkedHashMap by the order in which elements are inserted into the set.

This type of set is a good choice when you want a collection with no duplicates and fast access and you want to maintain an insertion order when iterating over it.

See LinkedHashMaps for example code.

Hashtablesgo to top of page Top

A Hashtable is an unordered and unsorted implementation of the Map<K,V> interface that doesn't allow null values or a null key. This type of map makes no guarantees over iteration order and in particular no guarantees that the iteration order will remain constant over time. Hashtable allows random access to elements and is similar to HashMap apart from being synchronized. In fact Hashtable is one of the two original collections shipped with Java, the other being Vector.

There is no sound reason since the introduction of the HashMap<K,V> class to use the Hashtable<K,V> class. If you need an HashMap to be synchronized this can be achieved using methods of the Collections class without all the overheads of using Hashtable<K,V> synchronized methods.

See Hashtables for example code.

TreeMapsgo to top of page Top

A TreeMap is a sorted implementation of the Map<K,V> interface. This type of map guarantees that the map will be sorted in ascending order, according to the natural order of the elements contained within it, or by a custom comparator/comparable, dependant upon the type of constructor used on creation.

The ordering maintained by a map whether through natural order of the elements contained within it or by a custom comparator/comparable, must be consistent with the equals() method override rules of the Object class if it is to correctly implement the Map<K,V> interface and obey the rules of equality.

This type of map is a good choice when you want a sorted collection with no duplicates with the option of custom sorting.

See TreeMaps for example code.

Utilities Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the utilities hierarchy and covers the java.util.Arrays and java.util.Collections classes which were studied in the Java section. These classes are genral utility classes and give us some useful static methods to use with arrays and collections.

utilities hierarchy

Utilities Classesgo to top of page Top

The table below gives a description of the classes within the above diagram. Click a link to go to detailed information about a particuar class:

Class Description
java.util.ArraysUtility class for manipulating arrays.
java.util.CollectionsUtility class for manipulating collections.

java.lang.Comparable<T> Interfacego to top of page Top

Classes can be sorted by using the java.lang.Comparable interface. We need to implement the Comparable interface and its only method compareTo() within our classes. The compareTo() method returns a negative integer, zero, or a positive integer dependant upon this object being less than, equal to, or greater than the specified object.

See the java.lang.Comparable interface for example code.

Related Java6 Tutorials

Collections/Generics - Collections Overview
Collections/Generics - Sets
Collections/Generics - Lists
Collections/Generics - Queues
Collections/Generics - Maps
Collections/Generics - Generics
OO Concepts - The Object Superclass

go to home page Java6 Tutor Homepage go to home page Top