Transcript 02-java-collections

Introduction to Java
Collections
Written by
Adam Carmi
Agenda
• About Collections
• Core Collection Interfaces
– Collection, Set, List, Map
• Object Ordering
– Comparable, Comparator
• More Core Collection interfaces
– SortedSet, SortedMap
• Implementations
• Algorithms
What is a Collection
Framework?
• A collection (sometimes called a container) is an
object that groups multiple elements into a single
unit.
• A collection framework is a unified architecture
for representing and manipulating collections.
• Java’s collection framework consists of
– Collection interfaces
– Concrete collection implementations (reusable data
structures)
C++’s Standard
– Algorithms (reusable functionality) Template Library is also
a collection framework
Benefits of a Collection
Framework
• Reduces programming effort
– Powerful data structures and algorithms
• Increases program speed and quality
– High quality implementations
– Fine tuning by switching implementations
• Reduces the effort of learning new APIs
– Uniformity of the framework
– APIs of applications
• Encourages software reuse
– New data structures and algorithms
Core Collection Interfaces
Collection interfaces allow collections to be manipulated
independently of the details of their representation
The Collection Interface
• Represents a group of objects, known as its
elements.
• The JDK does not provide any direct
implementations of this interface.
• Collection is used to pass collections around
and manipulate them when maximum
generality is desired.
• java.util.Collection
Iterator
• A mechanism for iterating over a collection’s
elements.
• Represented by the Iterator interface.
• Iterator allows the caller to remove elements from
the underlying collection during the iteration with
well-defined semantics
– The only safe way to modify a collection during
iteration
• java.util.Iterator
Example: Iterator
static void filter(Collection c)
{
for (Iterator it = c.iterator() ; it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
static void filter(Collection c)
{
Iterator it = c.iterator();
while (it.hasNext())
if (!cond(it.next()))
it.remove();
}
The Set Interface
• A collection that can not contain duplicate
keys.
• Contains no methods other than those
declared in the Collection interface.
• Two set objects are equal if they contain the
same elements, regardless of their
implementations.
• java.util.Set
Example: Set
import java.util.*;
public class FindDups {
public static void main(String args[])
{
Set s = new HashSet();
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);
}
}
The List Interface
• An ordered collection (sometimes called a
sequence)
• Lists may contain duplicate elements
• Collection operations
– remove operation removes the first occurrence of the
specified element
– add and addAll operations always appends new
elements to the end of the list.
– Two List objects are equal if they contain the same
elements in the same order.
The List Interface (cont)
• New List operations
–
–
–
–
Positional access
Search
Iteration (ordered, backward)
Range-view operations
• java.util.List
• java.util.ListIterator
Example: List
private static void swap(List a, int i, int j)
{
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
for (ListIterator i=l.listIterator(l.size()); i.hasPrevious(); ) {
Foo f = (Foo)i.previous();
...
Calls to next and
}
previous can be
intermixed
Exampe: List (cont)
public static void replace(List l, Object val, List newVals)
{
for (ListIterator i = l.listIterator(); i.hasNext() ; ) {
if (val==null ? i.next()==null : val.equals(i.next())) {
i.remove();
for (Iterator j = newVals.iterator(); j.hasNext(); )
i.add(j.next());
}
}
The add method inserts a new
}
element into the list, immediately
before the current cursor position
The Map Interface
• An object that maps keys to values.
– A map cannot contain duplicate keys.
– Each key cat map to at most one value.
• Every object can be used as a hash key
– public int Object.hashCode()
– Equal objects (according to equals()) must produce the
same hash code.
– The same hash code must be returned by an object
throughout the execution of a Java application.
• Two Map objects are equal if they represent the same
key-value mappings
The Map Interface (cont)
• Collection-view methods allow a Map to be viewed as a
Collection
– keySet – The Set of keys contained in the Map
– values – The Collection of values contained in the Map
– entrySet – The Set of key-value pairs contained in the Map
• With all three Collection-views, calling an Iterator's
remove operation removes the associated entry from the
backing Map.
– This is the only safe way to modify a Map during iteration.
• java.util.Map
Example: Map
import java.util.*;
public class Freq {
private static final Integer ONE = new Integer(1);
public static void main(String args[])
{
Map m = new HashMap();
for (int i=0; i<args.length; i++) {
Integer freq = (Integer)m.get(args[i]);
m.put(args[i], (freq==null ?
ONE : new Integer(freq.intValue() + 1)));
}
System.out.println(m.size() + " distinct words detected:");
System.out.println(m);
}
}
Example: Map (cont)
for (Iterator i = m.keySet().iterator() ; i.hasNext() ; )
System.out.println(i.next());
for (Iterator i = m.values().iterator(); i.hasNext() ; )
System.out.println(i.next());
for (Iterator i = m.entrySet().iterator(); i.hasNext() ; ) {
Map.Entry e = (Map.Entry)i.next();
System.out.println(e.getKey() + ": " + e.getValue());
}
Collection-views
provide the only means
to iterate over a Map.
Object Ordering
• A natural ordering can be defined for a class by
implementing the Comparable interface
• Objects of classes that implement the Comparable
interface may be sorted automatically
• Many JDK1 classes implement the Comparable
interface:
1)
Integer
signed numerical
String
lexicographic
Double
signed numerical
Date
chronological
Java Development Kit
Object Ordering (cont)
• The Comparable interface consists of a single
method
compareTo returns a negative
public interface Comparable {
public int compareTo(Object o);
}
integer, zero or a positive
integer as the receiving object
is less than, equal or greater
than the input object
• Natural ordering is not always sufficient
– Ordering objects in some order other than their natural
order
– Ordering objects that don't implement the Comparable
interface
Object Ordering (cont)
• A Comparator may be used to order objects
when natural ordering does not suffice
public interface Comparable {
public int compare(Object o1, Object o2);
}
Example: Comparable
public class Name implements Comparable {
private String firstName, lastName;
...
public int compareTo(Object o)
{
Name n = (Name)o;
int lastCmp = lastName.compareTo(n.lastName);
return lastCmp != 0 ? lastCmp :
firstName.compareTo(n.firstName);
}
}
Example: Comparator
public class NameComparator implements Comparator {
public int compare(Object o1, Object o2)
{
Name n1 = (Name)o1;
Name n2 = (Name)o2;
int lastCmp = n1.getLastName().compareTo(n2.getLastName());
return lastCmp != 0 ? lastCmp :
n1.getFirstName().compareTo(n2.getFirstName());
}
}
SortedSet Interface
• A Set that maintains its elements in ascending order
– according to elements' natural order
– according to a Comparator provided at SortedSet creation time
• Set operations
– Iterator traverses the sorted set in order
• Additional operations
– Range view – range operations
– Endpoints – return the first or last element
– Comparator access
• java.util.SortedSet
SortedMap Interface
• A Map that maintains its entries in ascending order
– According to keys' natural order
– According to a Comparator provided at creation time.
• Map operations
– Iterator traverses elements in any of the sorted map's collectionviews in key-order.
• Additional Operations
– Range view
– End points
– Comparator access
• java.util.SortedMap
Implementations
• Implementations are the actual data objects
used to store elements
– Implement the core collection interfaces
• There are three kinds of implementations
– General purpose implementations
– Wrapper implementations
– Convenience implementations
• Lesson: Implementations
General Purpose
Implementations
Implementations
Hash
Table
Interfaces
Set
HashSet
List
Map
Resizeable
Array
Balanced
Tree
TreeSet
ArrayList
HashMap
Linked
List
LinkedList
TreeMap
Older Implementations
• The collections framework was introduced in JDK1.2.
• Earlier JDK versions included collection implementations
that were not part of any framework
– java.util.Vector
– java.util.Hashtable
• These implementations were extended to implement the
core interfaces but still have all their legacy operations
– Be careful to always manipulate them only through the core
interfaces.
Algorithms
• Polymorphic algorithms are pieces of reusable
functionality provided by the JDK.
– defined as static methods of the Collections class
• Provided algorithms
– Sorting
– Shuffling
– Data manipulation
• reverse, fill, copy
– Searching
– Extreme values
• Lesson: Algorithms
Example: Algorithms
public static void sortNames(Name[] names) {
List l = Arrays.asList(names);
Collections.sort(l);
}
Arrays.asList is a
Convenience
implementation of the
List interface
• API Bridge
• Performance
public static void sortNames(Name[] names) {
List l = Arrays.asList(names);
Collections.sort(l, new Comparator() {
public int compare(Object o1, Object o2) {
Name n1 = (Name)o1;
Name n2 = (Name)o2;
int lastCmp = n1.getLastName().compareTo(n2.getLastName());
return lastCmp != 0 ? lastCmp :
n1.getFirstName().compareTo(n2.getFirstName());
}});
}