Transcript Java Collection : Built-in Data Structures for Java

Java Collection API :
Built-in Data Structures for Java
based on original presentation by C.-C. Chen
Transparency No. 1
Java Collection
The Java Collection API
Interfaces:
 Collection 
 Set  SortedSet,
 List
 Map  SortedMap
 Iterator  ListIterator
 Comparator
Transparency No. 2
Java Collection
Summary of all interfaces in the java Collection API
Collection Interfaces : The primary means by which collections are
manipulated.
 Collection  Set, List
 A group of objects.
 May or may not be ordered; May or may not contain duplicates.
 Set  SortedSet
 The familiar set abstraction.
 No duplicates; May or may not be ordered.
 SortedSet
 elements automatically sorted, either in their natural ordering (see the
Comparable interface), or by a Comparator object provided when a
SortedSet instance is created.
 List
 Ordered collection, also known as a sequence.
 Duplicates permitted; Allows positional access.
Transparency No. 3
Java Collection
 Map SortedMap
 A mapping from keys to values.
 Each key can map to at most one value (function).
 SortedMap
 A map whose mappings are automatically sorted by key, either in the
keys' natural ordering or by a comparator provided when a SortedMap
instance is created.
Transparency No. 4
Java Collection
classes of the java collection API
1. AbstractCollection (Collection) 



AbstractMap (Map) 





AbstractSet (Set)  HashSet, TreeSet(SortedSet)
AbstractList (List) ArrayList, AbstractSequentialList  LinkedList
HashMap
TreeMap (SortedMap)
WeakHashMap
Arrays
Collections
Transparency No. 5
Java Collection
General-Purpose Implementation classes
The primary implementations of the collection interfaces.
 HashSet : Hash table implementation of the Set interface.
 TreeSet : Red-black tree implementation of the SortedSet interface.
 ArrayList : Resizable-array implementation of the List interface.
 (Essentially an unsynchronized Vector.) The best all-around implementation of the
List interface.
 LinkedList : Doubly-linked list implementation of the List interface.
 May provide better performance than the ArrayList implementation if elements are
frequently inserted or deleted within the list.
 Useful for queues and double-ended queues (deques).
 HashMap : Hash table implementation of the Map interface.
 (Essentially an unsynchronized Hashtable that supports null keys and values.) The
best all-around implementation of the Map interface.
 TreeMap : Red-black tree implementation of the SortedMap interface.
Transparency No. 6
Java Collection
The java.util.Collection interface
 represents a group of objects, known as its elements.
 no direct implementation
 The primary use : pass around collections of objects where
maximum generality is desired.
Ex: List l = new ArrayList( c ) ; // c is a Collection object
Transparency No. 7
Java Collection
The definition
public interface Collection {
// Basic properties
int size();
boolean isEmpty();
boolean contains(Object element); // use equals() for comparison
boolean equal(Object);
int hashCode(); // new equals() requires new hashCode()
// basic operations
boolean add(Object);
// Optional; return true if this changed
boolean remove(Object); // Optional; use equals() (not ==)
Transparency No. 8
Java Collection
Why using Iterators instead of Enumerations
 Iterator allows the caller to remove elements from the underlying
collection during the iteration with well-defined semantics.
 Method names have been improved.
public interface Iterator {
boolean hasNext(); // cf: hasMoreElements()
Object next();
// cf: nextElement()
void remove();
// Optional
}
// a simple Collection filter using iterator that Enumeration could not help
static void filter(Collection c) {
for (Iterator i = c.iterator(); i.hasNext(); ) {
if ( no-good( i.next() ) ) i.remove(); // i.next() is removed from c
i.remove(); // exception raised, cannot remove more than once !
}}
Transparency No. 9
Java Collection
The Set Interface
 is a Collection that cannot contain duplicate elements.
 models the mathematical set abstraction.
 contains no methods other than those inherited from Collection.





same signatures but different semantics ( meaning )
Collection c = new LinkedList(); Set s = new HashSet();
String o = “a”;
c.add(o); c.add(o) ; // both return true; c.size() == 2
s.add(o); s.add(o) ; // 2nd add() returns false; s.size() == 1
 It adds the restriction that duplicate elements are prohibited.
 Collection noDups = new HashSet(c); // a simple way to eliminate
duplicate from c
 Two Set objects are equal if they contain the same elements.
 Two direct implementations:
 HashSet
TreeSet
Transparency No. 10
Java Collection
Basic Operations
 A simple program to detect duplicates using set:
import java.util.*;
public class FindDups {
public static void main(String args[]) {
Set s = new HashSet(); // or new TreeSet(), another implementation of Set
// following code uses Set methods only
for (int i=0; i<args.length; i++)
if (!s.add(args[i])) System.out.println("Duplicate detected: “ + args[i]);
System.out.println(s.size()+" distinct words detected: "+s);
}}
% java FindDups i came i saw i left
Duplicate detected: i
Duplicate detected: i
4 distinct words detected: [came, left, saw, i]
Transparency No. 11
Java Collection
The Map Interface




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.
Three implementations:
 HashMap, which stores its entries in a hash table, is the bestperforming implementation.
 TreeMap, which stores its entries in a red-black tree, guarantees the
order of iteration.
 Hashtable has also been retrofitted to implement Map.
 All implementation must provide two constructors: (like
Collections) Assume M is your implementation
 M()
// empty map
 M(Map m) // a copy of map from m
Transparency No. 12
Java Collection
The Map interface
public interface Map { // Map does not extend Collection
// Basic Operations
// put or replace, return replace object
// NOTE: different from Weiss’s insert(Hashable x)
Object put(Object key, Object value); // optional
Object get(Object key);
Object remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
Transparency No. 13
Java Collection
The Map interface
// Bulk Operations
void putAll(Map t); //optional
void clear(); // optional
// Collection Views;
// backed by the Map, change on either will be reflected on the other.
public Set keySet(); // cannot duplicate by definition!!
public Collection values(); // can duplicate
public Set entrySet(); // no equivalent in Dictionary
// nested Interface for entrySet elements
public interface Entry {
Object getKey();
Object getValue();
Object setValue(Object value);
}}
Transparency No. 14
Java Collection
Basic Operations
 a simple program to generate a frequency table
import java.util.*;
public class Freq { private static final Integer ONE = new Integer(1);
public static void main(String args[]) {
Map m = new HashMap();
// Initialize frequency table from command line
for (int i=0; i<args.length; i++) {
Integer freq = (Integer) m.get(args[i]); // key is a string
m.put(args[i], (freq==null ? ONE : new Integer( freq.intValue() + 1)));
} // value is Integer
System.out.println( m.size()+" distinct words detected:");
System.out.println(m);
} }
 > java Freq if it is to be it is up to me to delegate
8 distinct words detected:
{to=3, me=1, delegate=1, it=2, is=2, if=1, be=1, up=1}
Transparency No. 15
Java Collection
Collection Views methods
 allow a Map to be viewed as a Collection in three ways:
 keySet: the Set of keys contained in the Map.
 values: The Collection of values contained in the Map. This Collection is not a Set, as
multiple keys can map to the same value.
 entrySet: The Set of key-value pairs contained in the Map.
 The Map interface provides a small nested interface called Map.Entry that is the type
of the elements in this Set.
 the standard idiom for iterating over the keys in a Map:
for (Iterator i = m.keySet().iterator(); i.hasNext(); ) {
System.out.println(i.next());
if(no-good(…)) i.remove() ; } // support removal from the back Map
 Iterating over key-value pairs
for (Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry e = (Map.Entry) i.next();
System.out.println(e.getKey() + ": " + e.getValue());
}
Transparency No. 16
Java Collection
Actual Collection and Map Implementations
 Implementations are the actual data objects used to store
collections (and Maps).
Three kinds of implementations:
 General-purpose Implementations
 the public classes that provide the primary implementations of the
core interfaces.
 Wrapper Implementations
 used in combination with other implementations (often the generalpurpose implementations) to provide added functionality.
 Convenience Implementations
 Convenience implementations are mini-implementations, typically
made available via static factory methods that provide convenient,
efficient alternatives to the general-purpose implementations for
special collections (like singleton sets).
Transparency No. 17
Java Collection
General Purpose Implementations
Hash Table
Set
balanced
tree
ArrayList
Vector
HashMap
Hashtable
linked list
TreeSet
(sortedSet)
HashSet
List
Map
Resizable
array
LinkedList
TreeMap
(sortedMap)
Transparency No. 18
Java Collection
Properties of the implementations




consistent names as well as consistent behavior.
full implementations [of all the optional operations].
All permit null elements, keys and values.
unsynchronized.
 remedy the deficiency of Hashtable and Vector
 can become synchronized through the synchronization wrappers
 All have fail-fast iterators, which detect illegal concurrent
modification during iteration and fail quickly and cleanly.
 All are Serializable,
 all support a public clone() method.
 should be thinking about the interfaces rather than the
implementations. The choice of implementation affects only
performance.
Transparency No. 19
Java Collection
HashSet vs treeSet (and HashMap vs TreeMap)
 HashSet/ HashMap is much faster (constant time vs. log time
for most operations), but offers no ordering guarantees.
 always use HashSet/HashMap unless you need to use the
operations in the SortedSet, or in-order iteration.
 choose an appropriate initial capacity of your HashSet if
iteration performance is important.
 The default initial capacity is 101, and that's often more than you need.
 can be specified using the int constructor.
 Set s= new HashSet(17); // set bucket size to 17
Transparency No. 20
Java Collection
The Collections class
static int binarySearch(List list, Object key [, Comparator c])
static void copy(List dest, List src) // foreach i d.set(i, s.get(i));
static Enumeration enumeration(Collection c)
 Returns an enumeration over the specified collection.
static void
fill(List list, Object o)
static Object max(Collection coll [, Comparator comp] )
static Object min(Collection coll [, Comparator comp] )
static List
nCopies(int n, Object o)
static void
reverse(List l)
static Set
singleton(Object o)
static Comparator reverseOrder() // assume a is of type String[]
// usage: Arrays.sort(a, Collections.reverseOrder());
static void shuffle(List list [, Random rnd])
static void swap(List, int, int)
static void rotate(List, int d) ;// obj at i moved to ( i - d mod size())
Transparency No. 21