Java Collections & Maps

Interfaces

>The symbols shown in the figure above define interfaces. They can only be used as attribute definition, not as instantiation class names:

Collection xx = null;
xx = new Collection ( ); // error !
Set yy = null;
SortedSet zz = null;

The figure also provides the directions of the dependencies.

xx = yy;
xx = zz;
yy = xx; // error !

Corresponding Implementations

		Implementations
		Hash Table	Resizable Array	Balanced Tree	Linked List
Interfaces	Collection	HashSet	ArrayList	TreeSet	LinkedList
	Set	HashSet		TreeSet
	SortedSet			TreeSet
	List		ArrayList		LinkedList
	Map	HashMap		TreeMap
	SortedMap			TreeMap

The table above defines the implementations that correspond to the interfaces shown in the previous figure. An object defined by an interface must be instantiated by means of a class lying on the same line as the interface :

Collection xx1 = new HashSet ( ); // HashSet on the same line as Collection
Collection xx2 = new ArrayList ( );

SortedSet yy = new TreeSet ( );

Of course each collection can also be instantiated under its proper class:

ArrayList al = new ArrayList ( );

Main Characteristics of the Collections and Maps

All collections are used in a very similar way. What changes is the way in which the elements are stored in the collection:

ordered, with duplicates, with an access based on a key...

Moreover, some accesses may be more efficient in a collection or another one:

an ArrayList is created with an extra capacity, it must not be reallocated each time it grows
a LinkedList and an ArrayList can be used to create a fifo (list.add() / list.remove(0))
a TreeMap and a TreeSet are ordered (and thus need comparators)
a Set and a Map cannot contain duplicates
a Map contains pairs of (key;object). the elements are ordered and can be accessed by the key
the elements of some collections can be addressed by index
the collections can be walked through sequentially (iterator)
to walk through a Map, a collection must first be extracted

(see details below).

Storing Objects in a Collection or a Map

The basic methods to insert objects into a collection are given below:

HashSet, TreeSet	set.add(object);	add somewhere, in the order of the elements
LinkedList	list.add(object); list.add(index, object);	adds at the end adds at index and shifts the previous elements from index towards the end
ArrayList	list.add(object) list.add(index, object); list.set(index,object);	adds at the end adds at index and shifts the previous elements overwrite the value at index

The basic methods to insert objects into a map are indicated below:

HashMap TreeMap

map.put(key,value);

both key and value are Objects in the tree maps, keys are put in order of the keys

Note: the aggregations that store the objects in an ordered manner (TreeSet and TreeMap) must know how to compare the inserted objects (respectively keys). There are two ways to do that:

have the objects (respectively keys) that are inserted in the tree aggregation implement Comparable

provide a Comparator in the parameters of the instantiation of the aggregation

Retrieving and Managing Objects in a Collection or a Map

Some methods are known by all aggregations:

clear( ); size( ); remove (object);

Some of the methods defined in a collection are given below:

LinkedList	obj = c.get(index);	obj = c.remove(index);	bool = c.contains(obj);	objArr = c.toArray( );
ArrayList	obj = c.get(index);	obj = c.remove(index);	bool = c.contains(obj);	objArr = c.toArray( );
HashSet	-	see 1 inch above	bool = c.contains(obj);	objArr = c.toArray( );
TreeSet	-	see 1 inch above	bool = c.contains(obj);	objArr = c.toArray( );

Some of the methods defined in a map are defined below (Object obj, key;) :

HashMap TreeMap

obj = m.get (key);

obj = m.remove (key);

bool = m.containsKey (key); bool = m.containsValue( key);

collection = m.values( ); set = m.keySet( );

The operations of the last column return collections of elements. These collections can be used to walk through the trees.

Transformations

Passing from one aggregation type to another one can be used to sort the elements, eliminate the duplicates, create an array, and so on.

A collection of any type can be transformed to another one:

Set set = new HashSet ( );
.... fill in the set ....
SortedSet ss = new TreeSet ( set );

Parameter available for the instantiation:

LinkedList	( )	(Collection)
ArrayList	( )	(Collection)	(initialCapacity)
HashSet	( )	(Collection)	(initialCapacity)	(initialCapacity, loadFactor)
HashMap	( )	(Map)	(initialCapacity)	(initialCapacity, loadFactor)
TreeSet	( )	(Collection)	(Comparator)	(SortedSet)
TreeMap	( )	(Map)	(Comparator)	(SortedMap)

The maps return collections containing only the objects (keys are dropped)

Collection col = tm.values();

which can used as parameter in the instantiation of a collection.

A collection can be transformed into an array with:

Object [] obj = collection.toArray();