- Covers all the things we mentioned on the data structures page (and more)
- Was established in Java version 1.2
- Meant to replace more primitive Java 1.0 (legacy) collections but those were adapted so they still work
- Has been slightly extended in later versions
The Framework, mostly in java.util, contains two kinds of things:
- Collections: objects representing groups of objects
- Mappings: objects representing mappings between objects. Mappings comprise key/value pairs. A key is used to look up a value (as in the hash tables we discussed previously). Mappings have views which are collections, which is why they are part of the same API.
Why use collections/mappings?
A process uses significant amounts of data which may have come from database(s) but need to be kept locally for the process while it running and then, after results are output, discarded. Eg, for user interaction with a mouse hovering over a chart you need to have some data about all the objects on the chart held locally to find the nearest one to the mouse and give a summary: it would be too slow to go to a database for every one.
Use an array?
MyClass [] a = new MyClass [N_OBJECTS];
for (int i = 0; i < a.length; i++)
{
a [i] = getDataFromSource (i);
}
... // then the main processing
Advantage: we know the type of every object (no casting/generics).
Disadvantages:
- we have to know the value of N_OBJECTS at the start
- inserting/removing objects requires shifting others
- finding objects involves searching and maybe sorting
Collections and mappings solve such problems.
Main interfaces in the Framework
NB: Interfaces, not classes. All in java.util unless otherwise indicated.
The red 5 means new in Java 5.
Sun uses E for a generic type parameter that is an element of something, K for a key, V for a value, T for anything else. Any letters can really be used for such parametric types.
Any java.util.Collection implements...
Inherited from java.lang.Iterable<E>:
Iterator<E> iterator ()
Inherited from java.util.Collection<E>:
boolean add (E o)
boolean addAll (Collection<? extends E> c)
void clear ()
boolean contains (Object o)
boolean containsAll (Collection<?> c)
boolean isEmpty ()
boolean remove (Object o)
boolean removeAll (Collection<?> c)
boolean retainAll (Collection<?> c)
int size ()
Object[] toArray ()
<T> T[] toArray (T[] a)
Other interfaces in the Framework
Iterator <E>
ListIterator <E> extends Iterator <E>
Comparator <E>
Map.Entry <K, V>
RandomAccess /* a marker interface */
java.util.Iterator<E>
3 methods:
boolean hasNext ()
E next ()
void remove ()
An important feature of Iterators is that their cursors are positioned between objects in the collection.
remove () removes the last encountered object.
NB: Don't forget the for-each loop, which is often better.
java.util.ListIterator<E>
Collection Framework Lists are doubly linked, so this interface adds
boolean hasPrevious ()
E previous ()
Lists also have a numbered order so there is also
int nextIndex ()
int previousIndex ()
And also
void add (E o) // at the current position (between objects)
void set (E o) // replaces the last encountered object
Collection classes in java.util
Which two Collection Framework classes are you most likely to use?
ArrayList & HashMap
- Both can expand, to store unpredictable number of objects
- Both store references to objects
- Retrieval methods return an Object reference, so must cast to actual class or (Java 5) use generics
- ArrayList is accessed by element number
- HashMap is accessed by a key object (typically a String)
NB: Neither ArrayList nor HashMap is synchronised.
Always use ArrayList rather than the similar-looking pre-framework Vector, HashMap rather than Hashtable, and Iterator (or for-each loop) rather than Enumeration. You will see those legacy classes in existing code but do not use them any more.
ArrayList or LinkedList?
Mainly depends on whether you want to insert/remove objects in the middle of the list - easy to change links in a LinkedList but expensive to shift all higher objects up/down in an ArrayList.
ArrayList<E> is designed for random access, with E get (int index) and to have objects appended, with void add (E obj).
Both implement (as declared in the List<E> interface)
void add (int index, E obj)
E remove (int index)
but these are more appropriate for a LinkedList.
Both also have ListIterator<E> listIterator () and remember that a ListIterator can add/remove/set objects too.
Mapping classes in java.util
Views
Several collection methods return collection objects. Eg,
Set keys = map.keySet ();
This is often not a newly created collection but a view of the existing one, for efficiency. The library is designed so developers using the classes do not need to know implementation details.
Views of a Map
3 methods from the Map interface:
Set<Map.Entry<K,V>> entrySet () // all the key-value pairs
Set<K> keySet () // all the keys
Collection<V> values () // all the values
An Iterator can be obtained for each view.
Collections of objects
Some considerations:
- Must the objects all be different?
- Must they all be of the same type?
- Is null allowed?
- How will we find a particular object?
- Do we need to be able to loop through all of them?
- Do they have an inherent ordering?
- Is it required/possible to order them?
- Should they be sorted as they are put in the collection, or on retrieval?
- Are the objects or the collection to be written to from several threads?
All of these are factors in deciding which type of collection to use.
Some factors for Framework classes
| Class | Allows duplicates? | Allows null? | Ordered? |
|---|---|---|---|
| HashSet | no | yes | no |
| TreeSet | no | yes | yes |
| EnumSet | no | no | yes |
| LinkedList | yes | yes | yes |
| ArrayList | yes | yes | yes |
| HashMap | yes (not keys) | yes | no |
| TreeMap | yes (not keys) | yes | yes |
| EnumMap | no | no | yes |
| ConcurrentHashMap | yes (not keys) | no | no |
Memory leakage
A general problem with collections is that they hold object references which prevent the objects from being "garbage-collected" when they could otherwise be.
The Framework contains class WeakHashMap<K,V> which is designed so that when a key goes out of scope the corresponding entry in the map is automatically removed by the garbage collector.
For all other types of collection you must explicitly remove elements when they are no longer needed. For a map, before the key is lost.
NB: Singleton pattern: what if the (immortal) object has a collection?
Class java.util.Collections
Note the final "s" - do not confuse with interface java.util.Collection.
This class only has static methods, for working on collections. Eg,
public static <T> boolean addAll (Collection<? super T> c, T... obj)
public static <T extends Comparable<? super T>>
void sort (List<T> list, Comparator<? super T> c)
public static <T> void sort (List<T> list, Comparator<? super T> c)
public static <T> int binarySearch
(List<? extends Comparable<? super T>> list, T key)
TreeMap<K,V>
Implementation of interface SortedMap<K,V>
Iterating will be in sorted order of the keys (natural order as in Comparable, or defined by a Comparator when the map is constructed). All such keys must be mutually comparable: key1.compareTo (key2) (or comparator.compare (key1, key2)) must not throw a ClassCastException for any elements key1 and key2 in the sorted map.
TreeMap avoids sorting because objects are put (key, value) into it in the right place. It uses a tree structure (really a linked list).
NB: Hashing is faster so use HashMap unless you need to visit the keys in sorted order and do not want the overhead of a separate sort.