appropriate selection of collection classes/interfaces
to suit specified behavior requirements.
1.boolean add (Object o);
ensures that this collection contains the specified
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.
4.boolean contains(Object o);
6.boolean equals(Object o);
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
9.boolean remove(Object o);
12.int size (); If
this collection contains more than Integer.MAX_VALUE,
13.Object  toArray();
 toArray(Object  a); returns an
array containing all of the elements in this
collection whose runtime type is that of the specified
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
Inherited from Collection
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.
Other than those inherited from Collection)
void add (int
index, Object element);
addAll (int index,
Object get (int
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
index); returns a list iterator of the
elements in the list in proper sequence starting at
the specified position in this list.
index, Object element);
List subList(int from
index, int to index);
fromIndex inclusive, toIndex exclusive.
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.
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.
implementations, like TreeMap class make specific
guarantees as to their order, others, like HashMap
class do not.
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.
void clear ();
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.
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.
returns the key-value mapping number.
Collection values(); returns a collection
view of the values contained in this map.
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 :
SortedSet and SortedMap
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.
int compare(Object o1,
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.
can define the natural order of its instances by
implementing this interface. Then its objects can be
This natural order of Comparable
objects can be overruled by passing a Comparator to
the constructor when the sorted set or map is created.
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
SortedSet tailSet(Object fromElement);
returns a view of a portion of this sorted set,
whose elements are equal to or more than the
SortedSet subSet(Object fromElement, Object
toElement); fromElement inclusive, toElement
Comparator comparator(); this returns the
comparator associated with this sorted set, or null
if it uses natural ordering of its elements.
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.
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.
application can increase the capacity of an ArrayList
object before adding a large number of elements using
ensureCapacity(). This may reduce the amount of
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
ArrayList allows null elements.
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
Iterators returned by all of this class’s
collection-view methods are fail-fast.
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.
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.
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.
TreeMap (Comparator c)
TreeMap (SortedMap sm)
TreeMap (Map t)
Implements Set, backed by a TreeMap instance.
TreeSet (Comparator c)
TreeSet (SortedSet sm)
TreeSet (Collection c)
AbstractList, implements List. Iterators fail fast,
Enumerations are not.
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
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.
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.
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
Java2 collection classes, except for Vector and
HashTable, are not thread safe i.e. their integrity is
jeopardized by concurrent access.
Type is one of the following
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
One should always define hashCode() for objects that
one inserts in a hash table.
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.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11