public interface Collection

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

All general-purpose Collection implementation classes (which typically implement Collection indirectly through one of its subinterfaces) should provide two "standard" constructors: a void (no arguments) constructor, which creates an empty collection, and a constructor with a single argument of type Collection, which creates a new collection with the same elements as its argument. In effect, the latter constructor allows the user to copy any collection, producing an equivalent collection of the desired implementation type. There is no way to enforce this convention (as interfaces cannot contain constructors) but all of the general-purpose Collection implementations in the JDK comply.

Method Summary
    Basic Operations

• int size() Returns the number of elements in this collection.
• boolean isEmpty() Returns true if this collection contains no elements.
• boolean contains(Object o) Returns true if this collection contains the specified element.
• boolean remove(Object o) Removes a single instance of the specified element from this collection, if it is present (optional operation).
• boolean add(Object o) Ensures that this collection contains the specified element (optional operation).

• boolean containsAll(Collection c) Returns true if this collection contains all of the elements in the specified collection.
• boolean addAll(Collection c) Adds all of the elements in the specified collection to this collection (optional operation).
• boolean removeAll(Collection c) Removes all this collection's elements that are also contained in the specified collection (optional operation).
• boolean retainAll(Collection c) Retains only the elements in this collection that are contained in the specified collection (optional operation).
• void clear() Removes all of the elements from this collection (optional operation).

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

• Iterator iterator() Returns an iterator over the elements in this collection.

    An iterator over a collection.  Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined
     semantics.

Method Summary

• boolean hasNext()    Returns true if the iteration has more elements.
• Object   next()          Returns the next element in the interation.
•  void  remove()         Removes from the underlying collection the last element returned by the iterator (optional operation).

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

The additional stipulation on constructors is, not surprisingly, that all constructors must create a set that contains no duplicate elements (as defined above).
 

 Method Summary ( Collection operations with set rules)

• boolean add(Object o)             Adds the specified element to this set if it is not already present (optional operation).
• boolean  addAll(Collection c)   Adds all of the elements in the specified collection to this set if they're not already present (optional operation).

public interface List extends Collection

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each
element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the
list.

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such
that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all.

The List interface places additional stipulations, beyond those specified in the Collection interface, on the contracts of
the iterator, add, remove, equals, and hashCode methods. Declarations for other inherited methods are also included
here for convenience.

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero
based. Note that these operations may execute in time proportional to the index value for some implementations (the
LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the
caller does not know the implementation.

The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and
bidirectional access in addition to the normal operations that the Iterator interface provides. A method is provided to
obtain a list iterator that starts at a specified position in the list.

The List interface provides two methods to search for a specified object. From a performance standpoint, these methods
should be used with caution. In many implementations they will perform costly linear searches.

The List interface provides two methods to efficiently insert and remove multiple elements at an arbitrary point in the list.
 

 Method Summary ( in addition to Collection)

•  void  add(int index, Object element)   Inserts the specified element at the specified position in this list (optional operation).
• addAll(int index, Collection c)     Inserts all of the elements in the specified collection into this list at the specified position (optiona
• Object  get(int index)  Returns the element at the specified position in this list.
• int  indexOf(Object o)  Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element.
•  int lastIndexOf(Object o) Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element.
• ListIterator  listIterator()  Returns a list iterator of the elements in this list (in proper sequence).
•  ListIterator  listIterator(int index) Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position  in this list.
• Object  set(int index, Object element)  Replaces the element at the specified position in this list with the specified element (optional operation).
• List  subList(int fromIndex, int toIndex) Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex,       exclusive.

An iterator for lists that allows the programmer to traverse the list in either direction and modify the list during iteration.

 Method Summary

• void add(Object o)        Inserts the specified element into the list (optional operation).
• boolean   hasNext()       Returns true if this list iterator has more elements when traversing the list in the forward direction.
• boolean  hasPrevious()   Returns true if this list iterator has more elements when traversing the list in the reverse direction.
• Object   next()               Returns the next element in the list.
• int   nextIndex()              Returns the index of the element that would be returned by a subsequent call to next.
• Object   previous()         Returns the previous element in the list.
• int  previousIndex()         Returns the index of the element that would be returned by a subsequent call to previous.
• void   remove()               Removes from the list the last element that was returned by next or previous (optional operation).
• void  set(Object o)         Replaces the last element returned by next or previous with the specified element (optional operation).

public interface Map

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or 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 the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

All general-purpose map implementation classes should provide two "standard" constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument. In effect, the latter constructor allows the user to copy any map, producing an equivalent map of the desired class.

Inner Class Summary

• static interface  Map.Entry       A map entry (key-value pair).

 Method Summary

    Basic Operations

• Object  get(Object key)                        Returns the value to which this map maps the specified key.
• Object  put(Object key, Object value)  Associates the specified value with the specified key in this map (optional operation).
• Object  remove(Object key)                 Removes the mapping for this key from this map if present (optional operation).
• int size()                                                Returns the number of key-value mappings in this map.

• Set  keySet()                                        Returns a set view of the keys contained in this map.
• Set  entrySet()                                      Returns a set view of the mappings contained in this map.
• Collection  values()                               Returns a collection view of the values contained in this map.

• void  clear()                                          Removes all mappings from this map (optional operation).
• boolean  containsKey(Object key)        Returns true if this map contains a mapping for the specified key.
• boolean  containsValue(Object value)   Returns true if this map maps one or more keys to the specified value.
• boolean   isEmpty()                              Returns true if this map contains no key-value mappings.
• void  putAll(Map t)                              Copies all of the mappings from the specified map to this map (optional operation).

A map entry (key-value pair). The Map.entrySet method returns a collection-view of the map, whose elements are of this class. The only way to obtain a reference to a map entry is from the iterator of this collection-view. These Map.Entry objects are valid only for the duration of the iteration; more formally, the behavior of a map entry is undefined if the backing map has been modified after the entry was returned by the iterator, except through the iterator's own remove operation, or through the setValue operation on a map entry returned by the iterator.

Method Summary

• Object   getKey()                           Returns the key corresponding to this entry.
• Object  getValue()                          Returns the value corresponding to this entry.
• Object   setValue(Object value)      Replaces the value corresponding to this entry with the specified value (optional operation).

public interface SortedSet extends Set

A set that further guarantees that its iterator will traverse the set in ascending element order, sorted according to the
natural ordering of its elements (see Comparable), or by a Comparator provided at sorted set creation time. Several
additional operations are provided to take advantage of the ordering. (This interface is the set analogue of SortedMap.)

All elements inserted into an sorted set must implement the Comparable interface (or be accepted by the specified
Comparator). Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) (or
comparator.compare(e1, e2)) must not throw a ClassCastException for any elements e1 and e2 in the sorted
set. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a
ClassCastException.

All general-purpose sorted set implementation classes should provide four "standard" constructors: 1) A void (no
arguments) constructor, which creates an empty sorted set sorted according to the natural order of its elements. 2) A
constructor with a single argument of type Comparator, which creates an empty sorted set sorted according to the
specified comparator. 3) A constructor with a single argument of type Collection, which creates a new sorted set with
the same elements as its argument, sorted according to the elements' natural ordering. 4) A constructor with a single
argument of type SortedSet, which creates a new sorted set with the same elements and the same ordering as the input
sorted set.

Method Summary

• Comparator  comparator()   Returns the comparator associated with this sorted set, or null if it uses its elements' natural ordering.
• Object  first()                       Returns the first (lowest) element currently in this sorted set.
• Object   last()                      Returns the last (highest) element currently in this sorted set.
• SortedSet  headSet(Object toElement)      Returns a view of the portion of this sorted set whose elements are strictly less than toElement.
• SortedSet   subSet(Object fromElement, Object toElement)   Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive.
• SortedSet   tailSet(Object fromElement)     Returns a view of the portion of this sorted set whose elements are greater than or equal to         fromElement.

public interface SortedMap extends Map

A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys
(see the Comparable interface), or by a comparator provided at sorted map creation time. This order is reflected when
iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several
additional operations are provided to take advantage of the ordering. (This interface is the map analogue of the
SortedSet interface.)

All keys inserted into a sorted map must implement the Comparable interface (or be accepted by the specified
comparator). Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) (or
comparator.compare(k1, k2)) must not throw a ClassCastException for any elements k1 and k2 in the sorted
map. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a
ClassCastException.

All general-purpose sorted map implementation classes should provide four "standard" constructors: 1) A void (no
arguments) constructor, which creates an empty sorted map sorted according to the natural order of its keys. 2) A
constructor with a single argument of type Comparator, which creates an empty sorted map sorted according to the
specified comparator. 3) A constructor with a single argument of type Map, which creates a new map with the same
key-value mappings as its argument, sorted according to the keys' natural ordering. 4) A constructor with a single
argument of type sorted map, which creates a new sorted map with the same key-value mappings and the same ordering
as the input sorted map.

 Method Summary

• Comparator   comparator()       Returns the comparator associated with this sorted map, or null if it uses its keys' natural ordering.
• Object  firstKey()                      Returns the first (lowest) key currently in this sorted map.
• Object   lastKey()                     Returns the last (highest) key currently in this sorted map.
• SortedMap  headMap(Object toKey)       Returns a view of the portion of this sorted map whose keys are strictly less than toKey.
• SortedMap  subMap(Object fromKey, Object toKey)    Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to  toKey, exclusive.
• SortedMap  tailMap(Object fromKey)      Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey.

public interface Comparator

A comparison function, which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as Collections.sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as TreeSet or TreeMap).

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the natural ordering is a total order on S. When we say that the ordering imposed by c on S is consistent with equals, we mean that the quotient for the natural ordering is the equivalence relation defined by the objects' equals(Object) method(s):

       {(x, y) such that x.equals((Object)y)}.

 Method Summary

•  int  compare(Object o1, Object o2)        Compares its two arguments for order.

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map or elements in a sorted set, without the need to specify a comparator.

Virtually all Java core classes that implement comparable have natural orderings that are consistent with equals. One exception is java.math.BigDecimal, whose natural ordering equates BigDecimals with equal values and different precisions (such as 4.0 and 4.00).

 Method Summary

• int  compareTo(Object o)   Compares this object with the specified object for order.

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the intial capacity too high (or the load factor too low) if iteration performance is important.

The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

 Constructor Summary

•  HashSet()  Constructs a new, empty set; the backing HashMap instance has default capacity and load factor, which is 0.75.
• HashSet(Collection c)   Constructs a new set containing the elements in the specified collection.
• HashSet(int initialCapacity)  Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor,  which is 0.75.
• HashSet(int initialCapacity, float loadFactor)   Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load  factor.

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the intial capacity too high (or the load factor too low) if iteration performance is important.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly doubled by calling the rehash method.

As a general rule, te default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table.

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a concurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

 Constructor Summary

•  HashMap()   Constructs a new, empty map with a default capacity and load factor, which is 0.75.
• HashMap(int initialCapacity)
• Constructs a new, empty map with the specified initial capacity and default load factor, which is 0.75.
• HashMap(int initialCapacity, float loadFactor)   Constructs a new, empty map with the specified initial capacity and the specified load factor.
• HashMap(Map t)      Constructs a new map with the same mappings as the given map.

This class implements the Set interface, backed by a TreeMap instance. This class guarantees that the sorted set will be in
ascending element order, sorted according to the natural order of the elements (see Comparable), or by the comparator
provided at set creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

 Constructor Summary

•  TreeSet()                         Constructs a new, empty set, sorted according to the elements' natural order.
• TreeSet(Collection c)        Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order.
• TreeSet(Comparator c)     Constructs a new, empty set, sorted according to the given comparator.
• TreeSet(SortedSet s)         Constructs a new set containing the same elements as the given sorted set, sorted according to the same ordering.

public class TreeMap extends AbstractMap implements SortedMap, Cloneable, Serializable

Red-Black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending
key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at
creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
Algorithms are adaptations of those in Corman, Leiserson, and Rivest's Introduction to Algorithms.

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any
time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator throws
a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and
cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
 

Constructor Summary

• TreeMap()                        Constructs a new, empty map, sorted according to the keys' natural order.
• TreeMap(Comparator c)   Constructs a new, empty map, sorted according to the given comparator.
• TreeMap(Map m)             Constructs a new map containing the same mappings as the given map, sorted according to the keys' natural order.
• TreeMap(SortedMap m)   Constructs a new map containing the same mappings as the given SortedMap