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
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
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:
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 :
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 :
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 :
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 :
Choosing an
implementation
Lists
Type |
Methods |
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.
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
|