Transcript 33-collections

The Collections Framework
A Brief Introduction
Collections
• A collection is a structured group of objects
– An array is a kind of collection
– A Vector is a kind of collection
– A linked list is a kind of collection
• Java 1.2 introduced the Collections Framework
and provided many great implementations
– Vectors have been redefined to implement Collection
– Trees, linked lists, stacks, hash tables, and other classes
are implementations of Collection
– Arrays do not implement the Collection interfaces
Types of Collection
• Java supplies several types of Collection:
– Set: cannot contain duplicate elements, order is not
important
– SortedSet: like a Set, but order is important
– List: may contain duplicate elements, order is
important
• Java also supplies some “collection-like” things:
– Map: a “dictionary” that associates keys with values,
order is not important
– SortedMap: like a Map, but order is important
The Collections framework
Collection
Set
Map
List
SortedMap
SortedSet
• There are two groups: Collections of single
elements, and Maps containing key/value pairs
• These are all interfaces, but there are classes
implementing each interface
Some implementations
Collection
Map
Set
HashSet
SortedSet
TreeSet
List
ArrayList
Hashtable
LinkedList
Vector
HashMap
SortedMap
TreeMap
Stack
• Each class (in green) implements one or more
interfaces (in white), hence implements all the
methods declared in those interfaces
• We will look at the interface methods
Collections are ADTs
• The interfaces of the Collections framework
describe the functionality of a data structure but
not its implementation
• Collections are one of the best-designed parts of
Java, because
– They are elegant: they combine maximum power with
maximum simplicity
– They are uniform: when you know how to use one, you
almost know how to use them all
– You can easily convert from one to another
The Collection interface
• Some simple Collection methods:
–
–
–
–
–
–
int size( )
boolean isEmpty( )
boolean contains(Object e)
boolean add(Object e)*
boolean remove(Object e)*
Iterator iterator( )
• Some “bulk” Collection methods:
–
–
–
–
–
boolean containsAll(Collection c)
boolean addAll(Collection c)*
boolean removeAll(Collection c)*
boolean retainAll(Collection c)*
void clear( )
* Returns true if the Collection was changed, false otherwise
The Set interface
• A Set is a Collection that does not contain
duplicate (“equal”) elements
– “Equal” is defined by whatever equals(Object) method
applies to the elements of the collection
– You need to be sure you have a working equals method
– For a HashSet, you also need a working hashCode
method
• The methods of Set are the same as those of
Collection , but their effects may vary
– Example: If you add an object to a set, and the set
already contains that object (as defined by equals ), it
will not be added
The SortedSet interface
• A SortedSet keeps its elements in increasing order
• Therefore, it must be possible to sort the elements!
• This means:
– The elements must be objects of a type that implement
the Comparable interface (alternatively, you need to
supply a Comparator when you create the SortedSet)
– Elements must be mutually comparable (e.g. you can’t
compare a String to a Button)
– The ordering must be consistent with equals
• Additional methods include first() and last()
The List interface
• List implements all the methods defined by
Collection, and adds a few of its own:
–
–
–
–
–
–
–
Object get(int index)
Object set(int index, Object element)
void add(int index, Object element)
Object remove(int index)
boolean addAll(int index, Collection c)
int indexOf(Object o)
int lastIndexOf(Object o)
• In addition, List supplies a ListIterator that can
iterate through the elements forwards or backwards
The Map interface
• A Map is an object that maps keys to values
• A map cannot contain duplicate keys
– Depending on the implementation, null may or may not
be an allowable key
• Each key can map to at most one value
• Examples: dictionary, phone book, etc.
Map: Basic operations
• Object put(Object key, Object value)
– Returns the old value for this key, or null if no old value
•
•
•
•
•
•
Object get(Object key)
Object remove(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)
int size( )
boolean isEmpty( )
Additional Map methods
• void putAll(Map t)
– Copies one Map into another (adding to whatever is
already there)
– Example: newMap.putAll(oldMap)
• void clear()
– Example: oldMap.clear()
• public Set keySet( )
• public Collection values( )
A simple map: Hashtable
• To create a Hashtable, use:
import java.util.*;
Hashtable table = new Hashtable();
• To put things into a Hashtable, use:
table.put(key, value);
• To retrieve a value from a Hashtable, use:
value = (type)table.get(key);
The SortedMap interface
• A hash table keeps elements in an (apparently)
random order
• Sometimes you want the keys of a map to be in
sorted order (e.g. phone book, dictionary)
• A map can be implemented with a hash table, but
it doesn’t have to be
• The SortedMap interface implements the Map
interface and provides additional methods
• For efficiency, you want an implementation that
keeps its elements in some kind of order
Requirements for SortedMap
• A SortedMap keeps its elements in the order of
increasing key values
• Therefore, it must be possible to sort the keys!
• This means:
– The keys must be objects of a type that implement the
Comparable interface (or the SortedMap must be
created with a Comparator)
– Keys must be mutually comparable (e.g. you can’t
compare a String to a Button)
– The ordering must be consistent with equals
Some SortedMap Methods
• 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.
• There are some other methods, but they are not particularly
useful
• What is more important than these methods is that the
Iterator for a SortedMap returns elements in sorted order
Vectors
• The class Vector has been retrofitted to
implement the Collection interface
• Vector supplies add(Object) and iterator()
methods (among others)
• Let’s look at creating a Vector and iterating
through the elements
The Iterator interface
interface iterator { // java.lang.util
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).
Using a Vector
Collection numerals = new Vector();
numerals .add("one");
numerals .add("two");
numerals .add("three");
Iterator iter = numerals.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
Results:
one
two
three
Using a TreeSet
Collection numerals = new TreeSet();
numerals .add("one");
numerals .add("two");
numerals .add("three");
Iterator iter = numerals.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
Results:
one
three
two
Constructors
• Although constructors cannot be defined in an
interface, every Java-supplied class that
implements Collection has a constructor that
takes any other Collection as an argument
– Example: Vector myVector = new Vector(myTreeSet);
• Similarly, most classes that implement the Map
interface have a constructor that takes any other
Map as an argument
– Example: TreeMap myMap = new TreeMap(myHashtable);
• Thus, it is very easy to convert from one kind of
Collection or Map to another
Back to arrays
• Arrays are not part of the new Collections Framework, but they
haven’t been ignored
• Java 1.2 introduced the new Arrays class, with some useful
operations, for example:
–
–
–
–
–
static
static
static
static
static
void sort(Object[] a)
int binarySearch(Object[] a, Object key)
boolean equals(Object[] a, Object[] a2)
void fill(Object[] a, Object val)
void fill(Object[] a, Object val,
int from, int to)
– static List asList(Object[] a)
• Although I’ve shown these methods for arrays of Objects, there
are corresponding methods for arrays of each of the primitive
types
The End