• Make appropriate selection of collection classes/interfaces to suit specified behaviour requirements.
• Distinguish between correct and incorrect implementations of hashcode methods.

The Collections API

java.util.Collections

• a factory class
• a general interface - a bag, or multiset, with no specific order and can have duplicates
• inheriting/non-inheriting interfaces:
  1. java.util.List - order is important
  2. java.util.Set - uniqueness is required
  3. java.util.Map - a lookup table with unique primary keys, does not extend the Collections interface

Implementations

• arrays
  • fast to access
  • slow when very large and trying to insert/delete from middle
  • e.g. java.util.ArrayList
• linked lists
  • size grows easily
  • slower to accesss
  • easy to insert into middle so good for ordering (improve search)
  • e.g. java.util.LinkedList
• trees
  • easy to insert/delete, and grow
  • must have order
  • more efficient for ordering than arrays or linked lists
  • e.g. java.util.TreeMap (O(lg(n)) for access but already sorted) or java.util.TreeSet
• hash-tables
  • requires unique identifying key
  • more complex, so less appropriate for small data sets (calculation of hash code)
  • e.g. java.util.Hashtable (doesn't allow null to be stored) or java.util.HashMap (O(1) for access but sorting is slow) or java.util.HashSet

Collections, Equality and Sorting

• ensuring uniqueness of objects in a Set, or keys in a Map, is done with the equals() method
• compareTo() method required as Collections implement java.lang.Comparable
  used for ordering/sorting
• int hashCode() is requied for Map implementations
  (often use variables compared in the equals method to calculate a hash-code)

Re-use of Code

• e.g. List list = new ArrayList(); - so can later change to a LinkedList if wanted
• only mention the actual implementation when constructing with 'new'