Sunday, February 7, 2010

Collection Framework

Configuration Utilities describes APIs used to access configuration data supplied when the application is deployed, or by the application's user.
Properties are configuration values managed as key/value pairs. From System Properties you can find information about the operating system, the user, and the version of Java.
The property names (keys) and values are stored in a Properties structure. A Properties object can also be used to store your own program properties in a file.

The following figure illustrates how a typical application might manage its configuration data with a Properties object over the course of its execution:



setProperty(String key, String value)
remove(Object key)
getProperty(String key)
containsKey(Object key)


On the Java platform, an application uses System.getEnv to retrieve environment variable values. Without an argument, getEnv returns a read-only instance of java.util.Map, where the map keys are the environment variable names, and the map values are the environment variable values.

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data.
Core collection interfaces are the foundation of the Java Collections Framework.



Note also that the hierarchy consists of two distinct trees — a Map is not a true Collection.
Note that all the core collection interfaces are generic. For example, this is the declaration of the Collection interface.
public interface Collection...
The syntax tells you that the interface is generic.

A collection represents a group of objects known as its elements. The Collection interface is the least common denominator that all collections implement and is used to pass collections around and to manipulate them when maximum generality is desired.
For example, by convention all general-purpose collection implementations have a constructor that takes a Collection argument. This constructor, known as a conversion constructor, initializes the new collection to contain all of the elements in the specified collection, whatever the given collection's subinterface or implementation type. In other words, it allows you to convert the collection's type.
Suppose, for example, that you have a Collection c, which may be a List, a Set, or another kind of Collection. This idiom creates a new ArrayList (an implementation of the List interface), initially containing all the elements in c.
List list = new ArrayList(c);

The following shows the Collection interface:

public interface Collection extends Iterable {
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element);
//optional
boolean remove(Object element);
//optional 1st occurrence
Iterator iterator();

// Bulk operations
boolean containsAll(Collection c);
//c1.containsAll(c2);
boolean addAll(Collection c);
//optional union c1Uc2
boolean removeAll(Collection c);
//optional difference c1-c2
boolean retainAll(Collection c);
//optional intersection
void clear();
//optional

// Array operations
Object[] toArray();
T[] toArray(T[] a);
}



There are two ways to traverse collections: (1) for-each and (2) using Iterators.

for (Object o : collection) //cannot call remove() method
System.out.println(o);

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

public interface Iterator {
boolean hasNext();
E next();
void remove();
//optional
}
Iterator itr = c.iterator();
while(itr.hasNext())
System.out.println(itr.next());


Collections class consists static methods that operate on or return collections.
Collections.singleton, which is a static factory method that returns an immutable Set containing only the specified element.

to remove all instances of a specified element, e, from a Collection, c.
c.removeAll(Collections.singleton(e));

suppose you want to remove all of the null elements from a Collection.
c.removeAll(Collections.singleton(null));

The array operations allow the contents of a Collection to be translated into an array.
Object[] a = c.toArray();
String[] a = (String[])c.toArray(); //collection has only String


===================Set===============

— a collection that cannot contain duplicate elements. This interface models the mathematical set abstraction.
The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.


The Java platform contains three general-purpose Set implementations:

HashSet, which stores its elements in a hash table, is the best-performing implementation; however it makes no guarantees concerning the order of iteration.

TreeSet, which stores its elements in a red-black tree, orders its elements based on their values; it is substantially slower than HashSet.

LinkedHashSet, which is implemented as a hash table with a linked list running through it, orders its elements based on the order in which they were inserted into the set (insertion-order).

Suppose you have a Collection, c, and you want to create another Collection containing the same elements but with all duplicates eliminated. The following one-liner does the trick.
Collection noDups = new HashSet(c);


=============List================

— an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the list each element is inserted and can access elements by their integer index (position). eg: vector

In addition to the operations inherited from Collection, the List interface includes operations for the following:
  • Positional access — manipulates elements based on their numerical position in the list
  • Search — searches for a specified object in the list and returns its numerical position
  • Iteration — extends Iterator semantics to take advantage of the list's sequential nature
  • Range-view — performs arbitrary range operations on the list.

public interface List extends Collection {
// Positional access
E get(int index);
E set(int index, E element);
//optional replaces element at index
boolean add(E element);
//optional adds new element at end of list

void add(int index, E element); //optional adds new element at given index
E remove(int index);
//optional
boolean addAll(int index, Collection c);
//optional add c starting from index


// Search
int indexOf(Object o);
int lastIndexOf(Object o);

// Iteration

ListIterator listIterator();
ListIterator listIterator(int index);

// Range-view (takes args as index values)
List subList(int from, int to);
}


  1. ArrayList, which is usually the better-performing implementation, and
  2. LinkedList which offers better performance under certain circumstances.

Also, 3. Vector has been retrofitted to implement List.


Consider the following assignment statement.
gift[5] = "golden rings"; //element at index 5 for normal array
The Vector equivalent is:
gift.setElementAt("golden rings", 5);
The List equivalent is:
gift.set(5, "golden rings");


List strengthens the requirements on the equals and hashCode methods so that two List objects can be compared for logical equality without regard to their implementation classes.
NOTE: Two List objects are equal if they contain the same elements in the same order.

The set and remove operations return the old value that is being overwritten or removed; the Vector counterparts (setElementAt and removeElementAt) return nothing (void).

static void shuffle(List list)
Randomly permutes the specified list using a default source of randomness.
Collections.shuffle(list, new Random()); //permutes with specified source of Random
[a, b, c, d, e, f]---->[c, a, f, b, e, d]

List list = Arrays.asList(args); //This class contains various methods for manipulating arrays (such as sorting and searching). This class also contains a static factory that allows arrays to be viewed as lists.


List also provides a richer iterator, called a ListIterator, which allows you to traverse the list in either direction, modify the list during iteration, and obtain the current position of the iterator. The ListIterator interface follows.

public interface ListIterator extends Iterator {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
//optional
void set(E e);
//optional
void add(E e);
//optional
}


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.
ListIterator it = list.listIterator(list.size());


This implies the behavior of the two boundary cases:
  1. a call to previousIndex when the cursor is before the initial element returns -1 and
  2. a call to nextIndex when the cursor is after the final element returns list.size().

List sub_list = _list.subList(from, to);
sl.clear(); //also clears these sub_list elements from main _list; similiarly if

add, set, remove commands executed on sublist, main list also changes
The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List.


polymorphic algorithms in the Collections class apply specifically to List.
  • sort - sorts a List using a merge sort algorithm, which provides a fast, stable sort.
  • shuffle - randomly permutes the elements in a List.
  • reverse - reverses the order of the elements in a List.
  • rotate - rotates all the elements in a List by a specified distance.
  • swap - swaps the elements at specified positions in a List.
  • replaceAll - replaces all occurrences of one specified value with another.
  • fill - overwrites every element in a List with the specified value.
  • copy - copies the source List into the destination List.
  • binarySearch - searches for an element in an ordered List using the binary search algorithm.
  • indexOfSubList - returns the index of the first sublist of one List that is equal to another.
  • lastIndexOfSubList - returns the index of the last sublist of one List that is equal to another.


=============Queue================

— a collection used to hold multiple elements prior to processing. Besides basic Collection operations, a Queue provides additional insertion, extraction, and inspection operations. Besides basic Collection operations, queues provide additional insertion, removal, and inspection operations. The Queue interface follows.
public interface Queue extends Collection {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
//no args reqd. removes on FIFO or priority
}

Each Queue method exists in two forms: (1) one throws an exception if the operation fails, and (2) the other returns a special value if the operation fails (either null or false, depending on the operation). The regular structure of the interface is illustrated in the following table.

Queue Interface Structure



Queues typically, but not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to their values. (removes element based on priority), doesnt add null value gives NullPointerException.

It is possible for a Queue implementation to restrict the number of elements that it holds; such queues are known as bounded. Some Queue implementations in java.util.concurrent(ArrayBlockingQueue, PriorityBlockingQ, LinkedBlockingQ) are bounded, but the implementations in java.util (LinkedList, PriorityQ) are not.

Whatever ordering the head of the queue is the element that would be removed by a call to remove or poll. The remove and poll methods differ in their behavior only when the queue is empty. Under these circumstances, remove throws NoSuchElementException, while poll returns null.

The add method, which Queue inherits from Collection, inserts an element unless it would violate the queue's capacity restrictions, in which case it throws IllegalStateException. The offer method, which is intended solely for use on bounded queues, differs from add only in that it indicates failure to insert an element by returning false.

The element and peek methods return, but do not remove, the head of the queue. They differ from one another in precisely the same fashion as remove and poll: If the queue is empty, element throws NoSuchElementException, while peek returns null.
Queue implementations generally do not allow insertion of null elements. The LinkedList implementation (also implements List interface), which was retrofitted to implement Queue, is an exception.

Queue implementations generally do not define element-based versions of the equals and hashCode methods but instead inherit the identity-based versions from Object.
The Queue interface does not define the blocking queue methods, which are common in concurrent programming. These methods, which wait for elements to appear or for space to become available, are defined in the interface java.util.concurrent.BlockingQueue, which extends Queue.



=============Map================


— A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. Multiple keys can map same value. A Key can also map to the null Value. It models the mathematical function abstraction.

The Map interface follows.

public interface Map {

// Basic operations
V put(K key, V value);
// if key is already present, overwrite the value for same key
V get(Object key);
// gets value for the key else returns null
V remove(Object key);
// removes key-value mapping if present else returns null
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();

// Bulk operations
void putAll(Map m);
void clear();
// removes all mappings from Map

// Collection Views (provides only means to iterate over Map)
public Set keySet();
//the set of keys(unique)contained in Map
public Collection values();
//this collection is not a set, as multiple keys can map same value
public Set<>> entrySet();
//small nested interface called Map.Entry, the type of the elements in this Set

// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
}


The Java platform contains three general-purpose Map implementations:

HashMap, which stores its elements(keys) in a hash table, is the best-performing implementation; however it makes no guarantees concerning the order of iteration.

TreeMap, which stores its elements in a red-black tree, orders its elements(keys) based on their values; it is substantially slower than HashSet.

LinkedHashMap, which is implemented as a hash table with a linked list running through it, orders its elements(keys) based on the order in which they were inserted into the Map (insertion-order).


Map is an interface, while Hashtable is a concrete implementation.
The following are the major differences:
  • Map provides Collection views instead of direct support for iteration via Enumeration objects. Collection views greatly enhance the expressiveness of the interface.
  • Map allows you to iterate over keys, values, or key-value pairs; Hashtable does not provide the third option.
  • Map provides a safe way to remove entries in the midst of iteration; Hashtable did not.
  • Finally, Map fixes a minor deficiency in the Hashtable interface. Hashtable has a method called contains, which returns true if the Hashtable contains a given value. Map improves the interface's consistency — containsValue parallels containsKey.


Like the Setand Listinterfaces, Map strengthens the requirements on the equals and hashCode methods so that two Map objects can be compared for logical equality without regard to their implementation types. Two Map instances are equal if they represent the same key-value mappings.

The following one-liner creates a new HashMap initially containing all of the same key-value mappings as m.
Map copy = new HashMap(m);

Set s = m.keySet();
//returns set of keys
Set> em = m.entrySet();
System.out.println("SET Entry Map:" +em);
for(Map.Entry e:em){
System.out.println("Entry:"+e+"Key:"+e.getKey()+"Val:"+e.getValue());
}


With all three Collection views, calling an Iterator's remove operation removes the associated entry from the backing Map, assuming that the backing Map supports element removal to begin with.
// Filter a map based on some property of its keys.
for (Iterator it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();
//also removes entry from Map m


The Collection views support element removal in all its many forms — remove, removeAll, retainAll, and clear operations, as well as the Iterator.remove operation.
The Collection views do not support element addition under any circumstances.

if (m1.entrySet().containsAll(m2.entrySet())) { //whether the first Map contains all the key-value mappings in the second

if (m1.keySet().equals(m2.keySet())) { //whether two Map objects contain mappings for all of the same keys


Suppose you want to know all the keys common to two Map objects.
Set commonKeys = new HashSet(m1.keySet());
commonKeys.retainAll(m2.keySet());

Suppose you want to remove all of the key-value pairs that one Map has in common with another.
m1.entrySet().removeAll(m2.entrySet());

Suppose you want to remove from one Map all of the keys that have mappings in another.
m1.keySet().removeAll(m2.keySet());

All employee maps to their managers (Map name managers). To know who all the "individual contributors" (or nonmanagers) are.
Set individualContributors = new HashSet(managers.keySet());
individualContributors.removeAll(managers.values());

To fire all the employees who report directly to some manager, Simon.
Employee simon = ... ;
managers.values().removeAll(Collections.singleton(simon));

Collections.singleton, a static factory method that returns an immutable Set with the single, specified element.


A multimap is like a Map but it can map each key to multiple values. It's a fairly simple matter to use a Map whose values are List instances as a multimap.
Map> m = new HashMap>();



=
======Object-Ordering========

A List l may be sorted as follows.
Collections.sort(l);

If the List consists of String elements, it will be sorted into alphabetical order. If it consists of Date elements, it will be sorted into chronological order. String and Date both implement the Comparable interface.

Interface Comparable implementations provide a natural ordering for a class, which allows objects of that class to be sorted automatically.

If you try to sort a list, the elements of which do not implement Comparable, Collections.sort(list) will throw a ClassCastException.

Similarly, Collections.sort(list, comparator) will throw a ClassCastException if you try to sort a list whose elements cannot be compared to one another using the comparator.

Elements that can be compared to one another are called mutually comparable. Although elements of different types may be mutually comparable, none of the classes listed here permit interclass comparison.

The java.lang.Comparable interface consists of the following method.

public interface Comparable {
public int compareTo(T o);
}


The compareTo method compares the receiving object with the specified object and returns a negative integer, 0, or a positive integer depending on whether the receiving object is less than, equal to, or greater than the specified object. If the specified object cannot be compared to the receiving object, the method throws a ClassCastException.


public class Name implements Comparable {
....
public boolean equals(Object o) {
if (!(o instanceof Name)) return false;
Name n = (Name) o;
return n.firstName.equals(firstName) && n.lastName.equals(lastName); //internally uses String equals() method
}
public int hashCode() {
return 31 * firstName.hashCode() + lastName.hashCode();
}
public int compareTo(Name n) {
int lastCmp = lastName.compareTo(n.lastName); //internally uses String CompareTo() method for lastName comparison
return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName));
}
}
public class NameSort {
List names = Arrays.asList(nameArray);
Collections.sort(names);
.....


To do either of these things, you'll need to provide a Comparator — an object that encapsulates an ordering. Like the Comparable interface, the Comparator interface consists of a single method.

public interface Comparator {
int compare(T o1, T o2);
}


The compare method compares its two arguments, returning a negative integer, 0, or a positive integer depending on whether the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for the Comparator, the compare method throws a ClassCastException.

public class NameSort {
static final Comparator SENIORITY_ORDER = new Comparator() {
public int compare(Name e1, Name e2) {
return e2.hireDate().compareTo(e1.hireDate()); //calls Date class compareTo() method
}
};
List names = Arrays.asList(nameArray);
Collections.sort(names, SENIORITY_ORDER);
.....



====
====Sorted-Set==========

A SortedSet is a Set that maintains its elements in ascending order, sorted according to the elements' natural ordering or according to a Comparator provided at SortedSet creation time.

In addition to the normal Set operations, the SortedSet interface provides operations for the following:
  • Range view — allows arbitrary range operations on the sorted set
  • Endpoints — returns the first or last element in the sorted set
  • Comparator access — returns the Comparator, if any, used to sort the set

Implementations: TreeSet

The code for the SortedSet interface follows.
public interface SortedSet extends Set {
// Range-view (Takes args as element values)
SortedSet subSet(E fromElement, E toElement);
SortedSet headSet(E toElement);
//first element to specified head
SortedSet tailSet(E fromElement);
//specified tail to last element

// Endpoints
E first();
E last();

// Comparator access
Comparator comparator();
}


The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:
  1. The Iterator returned by the iterator operation traverses the sorted set in order.
  2. The array returned by toArray contains the sorted set's elements in order.

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.

TreeSet took the approach that it did, it also provides a constructor that takes a SortedSet and returns a new TreeSet containing the same elements sorted according to the same criterion.

SortedSet implementations also provide, by convention, a constructor that takes a Comparator and returns an empty set sorted according to the specified Comparator. If null is passed to this constructor, it returns a set that sorts its elements according to their natural ordering.

The range-view operations are somewhat analogous to those provided by the List interface, but there is one big difference. Range views of a sorted set remain valid even if the backing sorted set is modified directly. Changes to the range-view write back to the backing sorted set and vice versa.

Sorted sets provide three range-view operations. The first, subSet, takes two endpoints, like subList. Rather than indices, the endpoints are objects and must be comparable to the elements in the sorted set, using the Set's Comparator or the natural ordering of its elements, whichever the Set uses to order itself. Like subList, the range is half open, including its low endpoint but excluding the high one.

including "doorbell" but excluding "pickle", are contained in a SortedSet of strings called dictionary:
int count = dictionary.subSet("doorbell", "pickle").size();

the following one-liner removes all the elements beginning with the letter f.
dictionary.subSet("f", "g").clear();

st.subSet("d", "e").size(); //No. of words that starts with 'd'

Although it isn't entirely obvious, the successor of a string s in String's natural ordering is s + "\0" — that is, s with a null character appended.


Thus, the following one-liner tells you how many words between "doorbell" and "pickle", including doorbell and pickle, are contained in the dictionary.
count = dictionary.subSet("doorbell", "pickle\0").size();

Use the following to calculate the number of words between "doorbell" and "pickle", excluding both.
count = dictionary.subSet("doorbell\0", "pickle").size();

The SortedSet interface contains operations to return the first and last elements in the sorted set, not surprisingly called first and last

The SortedSet interface contains an accessor method called comparator that returns the Comparator used to sort the set, or null if the set is sorted according to the natural ordering of its elements.



====
=====Sorted-Map=========


A SortedMap is a Map that maintains its entries in ascending order, sorted according to the keys' natural ordering, or according to a Comparator provided at the time of the SortedMap creation.

The SortedMap interface provides operations for normal Map operations and for the following:
  • Range view — performs arbitrary range operations on the sorted map
  • Endpoints — returns the first or the last key in the sorted map
  • Comparator access — returns the Comparator, if any, used to sort the map

The following interface is the Map analog of SortedSet.

public interface SortedMap extends Map{
Comparator comparator();
SortedMap subMap(K fromKey, K toKey);
SortedMap headMap(K toKey);
SortedMap tailMap(K fromKey);
K firstKey();
K lastKey();
}


The operations SortedMap inherits from Map behave identically on sorted maps and normal maps with two exceptions:
  1. The Iterator returned by the iterator operation on any of the sorted map's Collection views traverse the collections in order.
  2. The arrays returned by the Collection views' toArray operations contain the keys, values, or entries in order.

Implementations: TreeMap

TreeMap took the approach it did, it also provides a constructor that takes a SortedMap and returns a new TreeMap containing the same mappings as the given SortedMap, sorted according to the same criterion.

SortedMap implementations also provide, by convention, a constructor that takes a Comparator and returns an empty map sorted according to the specified Comparator. If null is passed to this constructor, it returns a Map that sorts its mappings according to their keys' natural ordering.



==
==GeneralPurpose-Implementations====



All permit null elements, keys, and values. None are synchronized (thread-safe). All have fail-fast iterators, which detect illegal concurrent modification during iteration and fail quickly .
All are Serializable and all support a public clone method.

The legacy collections Vector and Hashtable are synchronized.
the Wrapper Implementations section, allow any collection to be transformed into a synchronized collection.

The java.util.concurrent package provides concurrent implementations of the BlockingQueue interface, which extends Queue, and of the ConcurrentMap interface, which extends Map.


General-Purpose Set Implementations

There are three general-purpose Set implementations — HashSet, TreeSet, and LinkedHashSet.

HashSet: HashSet is much faster, initial capacity, the default is 16.
Set s = new HashSet(64);//initial capacity is 64.

TreeSet: If you need to use the operations in the SortedSet interface, or if value-ordered iteration is required, use TreeSet

LinkedHashSet: Implemented as a hash table with a linked list running through it, it provides insertion-ordered iteration (least recently inserted to most recently) and runs nearly as fast as HashSet.


Special-Purpose Set Implementations

There are two special-purpose Set implementations — EnumSet and CopyOnWriteArraySet.

EnumSet is a high-performance Set implementation for enum types. All of the members of an enum set must be of the same enum type.
public enum Day {
SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY
}
for (Day d : EnumSet.range(Day.MONDAY, Day.FRIDAY))
System.out.println(d);
//print from MONDAY to FRIDAY

CopyOnWriteArraySet (java.util.concurrent) is a Set implementation backed up by a copy-on-write array. All mutative operations, such as add, set, and remove, are implemented by making a new copy of the array; no locking is ever required. This implementation is only appropriate for sets that are rarely modified but frequently iterated. It is well suited to maintaining event-handler lists that must prevent duplicates.


General-Purpose List Implementations

There are two general-purpose List implementations — ArrayList and LinkedList.
ArrayList: it can take advantage of System.arraycopy when it has to move multiple elements at the same time. Think of ArrayList as Vector without the synchronization overhead. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList. ArrayList has one tuning parameter — the initial capacity.

LinkedList: frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList.LinkedList has no tuning parameters and seven optional operations, one of which is clone. The other six are addFirst, getFirst, removeFirst, addLast, getLast, and removeLast. LinkedList also implements the Queue interface.



Special-Purpose List Implementations

CopyOnWriteArrayList is a List implementation backed up by a copy-on-write array. No synchronization is necessary, even during iteration, and iterators are guaranteed never to throw ConcurrentModificationException.
Example, it is not generally permssible for one thread to modify a Collection while another thread is iterating over it.
for (Iterator it = myCollection.iterator(); it.hasNext()) {
Object myObject = it.next();
if (someConditionIsTrue) {
// myCollection.remove(myObject); // wrong can throw ConcurrentModificationException
it.remove(myObject); // right
}
}

If you need synchronization, a Vector will be slightly faster than an ArrayList synchronized with Collections.synchronizedList.
But Vector has loads of legacy operations, so be careful to always manipulate the Vector with the List interface or else you won't be able to replace the implementation at a later time.


Map Implementations
Map implementations are grouped into general-purpose, special-purpose, and concurrent implementations.



General-Purpose Map Implementations

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, the default load factor (.75) offers a good tradeoff between time and space costs.

The three general-purpose Map implementations are HashMap, TreeMap and LinkedHashMap.

TreeMap: If you need SortedMap operations or key-ordered Collection-view iteration

HashMap: if you want maximum speed and don't care about iteration order

LinkedHashMap: if you want near-HashMap performance and insertion-order iteration. Note that insertion order is not affected if a key is re-inserted into the map. In other words, merely looking up the value associated with a key brings that key to the end of the map.
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode. accessOrder - the ordering mode - true for access-order, false for insertion-order.
Also, LinkedHashMap provides the removeEldestEntry method, which may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. This makes it very easy to implement a custom cache.
Special-Purpose Map Implementations

There are three special-purpose Map implementations — EnumMap, WeakHashMap and IdentityHashMap.

EnumMap, which is internally implemented as an array, is a high-performance Map implementation for use with enum keys.
public enum Day { MON, TUE, WED }
public enum Val { one, two, three }
Map em = new EnumMap(Day.class);
em.put(Day.MON, Val.one);


WeakHashMap is an implementation of the Map interface that stores only weak references to its keys. Storing only weak references allows a key-value pair to be garbage-collected when its key is no longer referenced outside of the WeakHashMap.

IdentityHashMap is an identity-based Map implementation based on a hash table. This class is useful for topology-preserving object graph transformations, such as serialization or deep-copying. To perform such transformations, you need to maintain an identity-based "node table" that keeps track of which objects have already been seen.

Concurrent Map Implementations
The java.util.concurrent package contains the ConcurrentMap interface, which extends Map with atomic putIfAbsent, remove, and replace methods, and the ConcurrentHashMap implementation of that interface.

ConcurrentHashMap is a highly concurrent, high-performance implementation backed up by a hash table. This implementation never blocks when performing retrievals and allows the client to select the concurrency level for updates.



Queue Implementations

The Queue implementations are grouped into general-purpose and concurrent implementations. Queue Implementations
The Queue implementations are grouped into general-purpose and concurrent implementations.



General-Purpose Queue Implementations

LinkedList implements the Queue interface, providing FIFO queue operations for add, poll, and so on.

The PriorityQueue class is a priority queue based on the heap data structure. This queue orders elements according to an order specified at construction time, which can be the elements' natural ordering or the ordering imposed by an explicit Comparator.

The queue retrieval operations — poll, remove, peek, and element — access the element at the head of the queue. The head of the queue is the least element with respect to the specified ordering.

The iterator provided in method iterator is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

The java.util.concurrent package contains a set of synchronized Queue interfaces and classes. Interface BlockingQueue extends Queue with operations that wait for the queue to become nonempty when retrieving an element and for space to become available in the queue when storing an element. This interface is implemented by the following classes:
  • LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
  • ArrayBlockingQueue — a bounded FIFO blocking queue backed by an array
  • PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
  • DelayQueue — a time-based scheduling queue backed by a heap
  • SynchronousQueue — a simple rendezvous mechanism that uses the BlockingQueue interface


Wrapper Implementations

Wrapper implementations delegate all their real work to a specified collection but add extra functionality on top of what this collection offers. For design pattern fans, this is an example of the decorator pattern.
library provides a static factory method. All these implementations are found in the
Collections class, which consists solely of static methods.
Synchronization Wrappers

The synchronization wrappers add automatic synchronization (thread-safety) to an arbitrary collection. Each of the six core collection interfaces — Collection, Set, List, Map, SortedSet, and SortedMap — has one static factory method.
public static Collection
synchronizedCollection(Collection c);
public static Set
synchronizedSet(Set s);
public static List
synchronizedList(List list);
public static Map
synchronizedMap(Map m);
public static SortedSet
synchronizedSortedSet(SortedSet s);
public static SortedMap
synchronizedSortedMap(SortedMap m);


Each of these methods returns a synchronized (thread-safe) Collection backed up by the specified collection.

List list = Collections.synchronizedList(new ArrayList());


In the face of concurrent access, it is imperative(important) that the user manually synchronize on the returned collection when iterating over it. The reason is that iteration is accomplished via multiple calls into the collection, which must be composed into a single atomic operation. The following is the idiom to iterate over a wrapper-synchronized collection.
Collection c = Collections.synchronizedCollection(myCollection);
synchronized(c) {
for (Type e : c)
foo(e);
}


If an explicit iterator is used, the iterator method must be called from within the synchronized block. Failure to follow this advice may result in nondeterministic behavior.


Unmodifiable Wrappers

Unlike synchronization wrappers, which add functionality to the wrapped collection, the unmodifiable wrappers take functionality away. In particular, they take away the ability to modify the collection by intercepting all the operations that would modify the collection and throwing an UnsupportedOperationException. Unmodifiable wrappers have two main uses, as follows:
To make a collection immutable once it has been built. In this case, it's good practice not to maintain a reference to the backing collection. This absolutely guarantees immutability.
To allow certain clients read-only access to your data structures. You keep a reference to the backing collection but hand out a reference to the wrapper. In this way, clients can look but not modify, while you maintain full access.
Like synchronization wrappers, each of the six core Collection interfaces has one static factory method.

public static Collection
unmodifiableCollection(Collection c);
public static Set
unmodifiableSet(Set s);
public static List
unmodifiableList(List list);
public static Map
unmodifiableMap(Map m);
public static SortedSet
unmodifiableSortedSet(SortedSet s);
public static SortedMap
unmodifiableSortedMap(SortedMap m);
Map unmodifiedMap = Collections.unmodifiableMap(modifiedMap);



Checked Interface Wrappers

The Collections.checked interface wrappers are provided for use with generic collections. These implementations return a dynamically type-safe view of the specified collection, which throws a ClassCastException if a client attempts to add an element of the wrong type. The generics mechanism in the language provides compile-time (static) type-checking, but it is possible to defeat this mechanism. Dynamically type-safe views eliminate this possibility entirely.



Convenience Implementations

This section describes several mini-implementations that can be more convenient and more efficient than general-purpose implementations when you don't need their full power. All the implementations in this section are made available via static factory methods rather than public classes.


List View of an Array

The java.util.ArraysCollections.nCopies method returns such a list. This implementation has two main uses. The first is to initialize a newly created List; for example, suppose you want an ArrayList initially consisting of 1,000 null elements. The following incantation does the trick. Of course, the initial value of each element need not be null. The second main use is to grow an existing List.
List list = new ArrayList(Collections.nCopies(100, (Type) null));
list.addAll(Collections.nCopies(50, type));


Immutable Singleton Set

Sometimes you'll need an immutable singleton Set, which consists of a single, specified element. The Collections.singleton method returns such a Set. One use of this implementation is to remove all occurrences of a specified element from a Collection.
c.removeAll(Collections.singleton(e));
say list.removeAll(Collections.singleton(type));


Empty Set, List, and Map Constants

The Collections class provides methods to return the empty Set, List, and Map — emptySet, emptyList, and emptyMap. The main use of these constants is as input to methods that take a Collection of values when you don't want to provide any values at all, as in this example.
tourist.declarePurchases(Collections.emptySet());
static List emptyList() Returns the empty list (immutable).
static Map emptyMap() Returns the empty map (immutable).
static Set emptySet() Returns the empty set (immutable).




==========Algorithms=========


All of them come from the Collections class, and all take the form of static methods whose first argument is the collection on which the operation is to be performed. The great majority of the algorithms provided by the Java platform operate on List instances, but a few of them operate on arbitrary Collection instances. This section briefly describes the following algorithms:

  • Sorting The sort algorithm reorders a List so that its elements are in ascending order according to an ordering relationship. The sort operation uses a slightly optimized merge sort algorithm that is fast and stable (It doesn't reorder equal elements).
Collections.sort(list);
The second form of sort takes a Comparator in addition to a List and sorts the elements with the Comparator.
static final Comparator SENIORITY_ORDER = new Comparator() {
public int compare(Name e2, Name e1) {
return e2.hireDate().compareTo(e1.hireDate());
}
};
Collections.sort(names, SENIORITY_ORDER);


  • Shuffling The shuffle algorithm does the opposite of what sort does, destroying any trace of order that may have been present in a List.
Collections.shuffle(list); Collections.shuffle(list, random); //Randomly permutes


Routine Data Manipulation The Collections class provides five algorithms for doing routine data manipulation on List objects, all of which are pretty straightforward:

  • reverse — reverses the order of the elements in a List.
  • fill — overwrites every element in a List with the specified value. This operation is useful for reinitializing a List.
  • copy — takes two arguments, a destination List and a source List, and copies the elements of the source into the destination, overwriting its contents. The destination List must be at least as long as the source. If it is longer, the remaining elements in the destination List are unaffected.
  • swap — swaps the elements at the specified positions in a List.
  • addAll — adds all the specified elements to a Collection. The elements to be added may be specified individually or as an array



  • Searching The binarySearch algorithm searches for a specified element in a sorted List. This algorithm has two forms. The first takes a List and an element to search for (the "search key"). This form assumes that the List is sorted in ascending order according to the natural ordering of its elements. The second form takes a Comparator in addition to the List and the search key, and assumes that the List is sorted into ascending order according to the specified Comparator. The sort algorithm can be used to sort the List prior to calling binarySearch. The return value is the same for both forms. If the List contains the search key, its index is returned. If not, the return value is (-(insertion point) - 1)
int pos = Collections.binarySearch(list, key);
if (pos <>

  • Composition The frequency and disjoint algorithms test some aspect of the composition of one or more Collections:
--frequency — counts the number of times the specified element occurs in the specified collection
--disjoint — determines whether two Collections are disjoint; that is, whether they contain no elements in common

  • Finding Extreme Values The min and the max algorithms return, respectively, the minimum and maximum element contained in a specified Collection. Both of these operations come in two forms. The simple form takes only a Collection and returns the minimum (or maximum) element according to the elements' natural ordering. The second form takes a Comparator in addition to the Collection and returns the minimum (or maximum) element according to the specified Comparator.




===
====Custom_Implementation========

Writing a custom implementation is surprisingly easy. The Java Collections Framework provides abstract implementations designed expressly to facilitate custom implementations. We'll start with the following example of an implementation of Arrays.asList.
public static List asList(T[] a) {
return new MyArrayList(a);
}

private static class MyArrayList extends AbstractList {

private final T[] a;

MyArrayList(T[] array) {
a = array;
}

public T get(int index) {
return a[index];
}

public T set(int index, T element) {
T oldValue = a[index];
a[index] = element;
return oldValue;
}

public int size() {
return a.length;
}
}


Believe it or not, this is very close to the implementation that is contained in java.util.Arrays. It's that simple! You provide a constructor and the get, set, and size methods, and AbstractList does all the rest.(need to override abstrct methods only, rest of methods are not abstract) You get the ListIterator, bulk operations, search operations, hash code computation, comparison, and string representation for free.

The following list summarizes the abstract implementations:
  • AbstractCollection — a Collection that is neither a Set nor a List. At a minimum, you must provide the iterator and the size methods.
  • AbstractSet — a Set; use is identical to AbstractCollection.
  • AbstractList — a List backed up by a random-access data store, such as an array. At a minimum, you must provide the positional access methods (get and, optionally, set, remove, and add) and the size method. The abstract class takes care of listIterator (and iterator).
  • AbstractSequentialList — a List backed up by a sequential-access data store, such as a linked list. At a minimum, you must provide the listIterator and size methods. The abstract class takes care of the positional access methods. (This is the opposite of AbstractList.)
  • AbstractQueue — at a minimum, you must provide the offer, peek, poll, and size methods and an iterator supporting remove.
  • AbstractMap — a Map. At a minimum you must provide the entrySet view. This is typically implemented with the AbstractSet class. If the Map is modifiable, you must also provide the put method.



======Compatibility =======


The Java Collections Framework was designed to ensure complete interoperability between the core collection interfaces and the types that were used to represent collections in the early versions of the Java platform: Vector, Hashtable, array, and Enumeration.


Upward Compatibility

Suppose the old API returns an array of objects and the new API requires a Collection. The Collections Framework has a convenience implementation that allows an array of objects to be viewed as a List. You use Arrays.asList to pass an array to any method requiring a Collection or a List.

Foo[] result = oldMethod(arg);
newMethod(Arrays.asList(result));

If the old API returns a Vector or a Hashtable, you have no work to do at all because Vector was retrofitted to implement the List interface, and Hashtable was retrofitted to implement Map.

The Collections.list method translates an Enumeration into a Collection.
Enumeration e = oldMethod(arg);
newMethod(Collections.list(e));



Backward Compatibility


Suppose the new API returns a Collection, and the old API requires an array of Object. As you're probably aware, the Collection interface contains a toArray method designed expressly for this situation.

Collection c = newMethod();
oldMethod(c.toArray());

If the old API requires a Vector, the standard collection constructor comes in handy.

Collection c = newMethod();
oldMethod(new Vector(c));
The case where the old API requires a Hashtable is handled analogously.
Map m = newMethod();
oldMethod(new Hashtable(m));

This is a static factory method that takes a Collection and returns an Enumeration over the elements of the Collection.

Collection c = newMethod();
oldMethod(Collections.enumeration(c));

No comments:

Post a Comment