java.util Package

Make appropriate selection of collection classes/interfaces to suit specified behavior requirements.

Collection (Interface)

Methods

1.boolean add (Object o); ensures that this collection contains the specified element.

2.boolean addAll (Collection c); the behavior of this operation is undefined if the specified collection is modified while the operation is in progress. This implies that the behavior of this operation is undefined if the specified collection is this collection, and this collection is non empty.

3.void clear();

4.boolean contains(Object o);

5.boolean containsAll(Collection c);

6.boolean equals(Object o);

7.boolean isEmpty();

8.boolean iterator(); There are no guarantees concerning the order in which the elements are returned unless this collection is an instance of some class that provides a guarantee.

9.boolean remove(Object o);

10.boolean removeAll(Collection c);

11.boolean retainAll(Collection c);

12.int size (); If this collection contains more than Integer.MAX_VALUE, returns Integer.MAX_VALUE.

13.Object [] toArray();

14.Object [] toArray(Object [] a); returns an array containing all of the elements in this collection whose runtime type is that of the specified array.

Sub-interfaces

List
Set
BeanContext
BeanContextServices

Implementing classes

AbstractCollection

Set (Interface)

Allows at most one null element. Great care must be taken if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equal comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

Implementing classes: HashSet

Methods : Inherited from Collection

List (Interface)

List is an ordered collection and allows duplicate elements. So multiple null elements are allowed too. Operations like positional access to list elements may execute in time proportional to the index value for some implementations like LinkedList. Thus, iterating over the elements in a list is typically preferable to indexing through it, if the caller does not know the implementation.

The methods provided for search for a specified object should be used with caution from a performance point of view, as they may prove to be costly linear searches. While it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals() and hashCode() methods are no longer well defined on such a list.

Methods ( Other than those inherited from Collection)

void add (int index, Object element);
boolean addAll (int index, Collection c);
Object get (int index);
int indexOf (Object o); returns –1 if o is not in the list.
int lastIndexOf (Object o); returns –1 if o is not in the list.
ListIterator listIterator();
ListIterator listIterator(int index); returns a list iterator of the elements in the list in proper sequence starting at the specified position in this list.
Object remove(int index);
Object set(int index, Object element);
List subList(int from index, int to index); fromIndex inclusive, toIndex exclusive.

Map (Interface)

Maps keys to values. A map cannot contain duplicate keys. Each key can map to at most one value. This interface takes the place of Dictionary class, which was a totally abstract class.

Map interface three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, and set of key-value mappings. The order of a map is defined as the order in which the iterators on the map’s collection views return their elements.

Some map implementations, like TreeMap class make specific guarantees as to their order, others, like HashMap class do not.

Great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equal comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals () and hashCode() methods are no longer well defined on such a map.

Methods

void clear ();
boolean containsKey(Object key);
boolean containsValue(Object value);
Set entrySet() returns a set view of the mappings in the map.
Object get(Object key); returns the value to which this map maps the specified key.
boolean isEmpty();
Set keySet(); returns a set view of the keys in this map.
Object put(Object key, Object value); returns previous value associated with this key and replaces that specified value. Returns null if there was no value associated with this key earlier.
void putAll(Map t);
Object remove(Object key); removes the mapping for this key if present.
int size(); returns the key-value mapping number.
Collection values(); returns a collection view of the values contained in this map.

All the three views returned by keySet(), values() and entrySet() are backed by the map, so changes to the map are reflected in the set, and vice-versa.

Sub-interfaces : SortedMap

Implementing classes :

AbstractMap
HashMap
HashTable
WeakHashMap
Attributes
RenderingHints

SortedSet and SortedMap

These interfaces extend Set and Map respectively, for implementations that sort their elements in a specific order. Objects can specify their natural order by implementing the Comparable interface, or be dictated a total order by a comparator which implements the Comparator interface.

Comparator

int compare(Object o1, Object o2);

Since this method tests for equality, it is recommended that its implementation does not contradict the semantics of the equals() method. Specific Comparator implementations can be constructed to order elements according to some custom order, or the default comparator which uses the natural order of the elements can be used.

Comparable

int compareTo(Object o);

A class can define the natural order of its instances by implementing this interface. Then its objects can be used

As elements in a sorted set.
As keys in a sorted map.
In lists which can be sorted automatically by Collections.sort() method.

This natural order of Comparable objects can be overruled by passing a Comparator to the constructor when the sorted set or map is created.

SortedSet ( implementing class – TreeSet)

SortedSet headSet(Object toElement); returns a view of a portion of this sorted set, whose elements are strictly less than the specified element.
SortedSet tailSet(Object fromElement); returns a view of a portion of this sorted set, whose elements are equal to or more than the specified element.
SortedSet subSet(Object fromElement, Object toElement); fromElement inclusive, toElement exclusive.
Object first();
Object last();
Comparator comparator(); this returns the comparator associated with this sorted set, or null if it uses natural ordering of its elements.

SortedMap ( implementing class – TreeMap)

SortedMap headMap(Object toKey); returns a view of a portion of this sorted Map, whose Keys are strictly less than the specified Key.
SortedMap tailMap(Object fromKey); returns a view of a portion of this sorted Map, whose Keys are equal to or more than the specified Key.
SortedMap subMap(Object fromKey, Object toKey); fromKey inclusive, toKey exclusive.
Object firstKey ();
Object lastKey ();
Comparator comparator(); this returns the comparator associated with this sorted Map, or null if it uses natural ordering of its keys.

ArrayList

The size(), isEmpty(), get(), set(), iterator() and listIterator() operations run in constant time. The add() operation runs in amortized constant time i.e. adding n elements requires o(n) time. All other operations run in linear time.

An application can increase the capacity of an ArrayList object before adding a large number of elements using ensureCapacity(). This may reduce the amount of incremental reallocation.

The iterators returned by iterator() and listIterator() methods are fail-fast. Thus in the face of concurrent modification, the iterator() fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior later, by throwing a ConcurrentModificationException.

ArrayList allows null elements.

Constructors:

ArrayList()
ArrayList(Collection c)
ArrayList(int initialCapacity)

HashMap

Allows null values and keys. It is roughly equivalent to HashTable, except that it is unsynchronized and permits nulls. Makes no guarantee as to order of the Map. It is HashTable based implementation. Constant time performance for get() and put(). Iteration over collection views requires time proportionate to the capacity of the HashMap instance. Thus it is very important not to set the initial capacity too high, or the load factor too low if the iteration performance is important. Initial capacity and load factor affect its performance. When the number of entries exceeds the product of load factor and the current capacity, the capacity is roughly doubled. Default load factor is 0.75.

Iterators returned by all of this class’s collection-view methods are fail-fast.

Constructors :

HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
HashMap(Map)

HashSet

Backed by a HashTable ( actually a HashMap instance). No guarantees as to the iteration order of the set. Offers constant time performance for basic operations like add(), remove(), contains() and size(). Rest like as in HashMap. Iterators fail fast. Default load factor is 0.75.

Constructors :

HashSet()
HashSet (int initialCapacity)
HashSet (int initialCapacity, float loadFactor)
HashSet (Collection c)

HashTable

Extends Dictionary implements Map. It is synchronized. The iterators returned by iterator() and listIterator() of the collections returned by HashTable’s collection-view methods are fail fast. The Enumerations returned by its keys() and values() are not fail fast. Default load factor is 0.75.

Constructors :

HashTable ()
HashTable (int initialCapacity)
HashTable (int initialCapacity, float loadFactor)
HashTable (Map m)

TreeMap

Implements SortedMap extends AbstractMap. This class guarantees that map will be in ascending-key order, sorted as per natural order for the key’s class(comparable) or by comparator provided at creation time. This implementation provides guaranteed log(n) time cost for containsKey(), get(), put() and remove() operations. Iterators are fail fast.

Constructors :

TreeMap ()
TreeMap (Comparator c)
TreeMap (SortedMap sm)
TreeMap (Map t)

TreeSet

Implements Set, backed by a TreeMap instance.

Constructors :

TreeSet ()
TreeSet (Comparator c)
TreeSet (SortedSet sm)
TreeSet (Collection c)

Vector

Extends AbstractList, implements List. Iterators fail fast, Enumerations are not.

Constructors :

Vector ()
Vector (Comparator c)
Vector (int initialCapacity)
Vector (int initialCapacity, int capacityIncrement)

Choosing an implementation

Lists

Type	Methods
Type	Get	Iteration	Insert	Remove
Array	1	1	n.a.	n.a.
ArrayList	2	3	2	2
LinkedList	4	2	1	1
Vector	3	4	3	2

For random access lookups and iteration arrays are fastest. The best approach is probably to choose ArrayList as default, and to change to LinkedList if there are performance problems due to many insertions and removals from the middle of the list. While working with a fixed size group of elements array is best.

Sets

The performance of HashSet is generally superior to TreeSet for all operations, in particular addition and look up (the two most important operations). The only reason TreeSet exists is because it maintains its elements in sorted order, so you only use it when you need a sorted list.

Maps

When choosing between implementations of Map, the size of the map is what most strongly affects performance. When you are using a map your first choice should be HashMap, and only if you need a constantly sorted map will you need a TreeMap. HashTable is generally a bit slower than HashMap. TreeMap should be used as a way to create an ordered list. The behavior of a tree is that it is always in order and does not have to be specially sorted. Once you fill a TreeMap you can call keySet() to get a set view, and then use toArray(). HashMap is designed to rapidly find things. Also, you can easily create a HashMap from a TreeMap with a single object creation.

Points to Remember

1. Some of the operations in the Collection interface are optional, meaning that a collection may choose not to provide a proper implementation of such an operation. In such a case, an UnsupportedOperationException is thrown when the optional operation is invoked.

2. The inherited method add(Object o) from Collection into the List will append the specified element to the end of the list. The inherited remove(Object o) removes the first occurrence of the Object from the list.

3. Apart from other utility methods for searching, sorting etc. Collections class’s methods can be used to customize collection implementations. The important considerations are

Thread safety
Data immutability

The Java2 collection classes, except for Vector and HashTable, are not thread safe i.e. their integrity is jeopardized by concurrent access.

Type synchronizedType(Type t)
Type unmodifiableType(Type t)

where Type is one of the following

Collection
List
Map
Set
SortedSet
SortedMap

4. Linked lists do not support fast random access. If you want to see the nth element, you have to start at the beginning and skip past the first n-1 elements first. Nevertheless, the LinkedList class supplies a get( int index), which is not very efficient. If you find yourself using it, you are probably using wrong data-structure for your problem. For every call of get(index) search begins at the beginning.

5. One should always define hashCode() for objects that one inserts in a hash table.

6. Adding an element to a tree is slower than adding it to a hash table, but it is still much faster than array or LinkedList.

Sections : 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11