Transcript 07-SetAndMapADT

TCSS 342, Winter 2006
Lecture Notes
Java’s Set ADT
Java’s Map ADT
Sample Word Finding/Counting
application
version 1.0
1
Objectives

Learn more about Java’s Collection API




Set
Map
Learn how Set and Map are used
Discuss the basics of how they are
implemented
2
Application: words in a book


Write an application that reads in the text of a
book (say, Moby Dick) and then lets the user
type words, and tells whether those words are
contained in Moby Dick or not.
How would we implement this with a List?



Would this be a good or bad implementation?
Does the ordering of the elements in the List affect
the algorithm? Could we use this information to
our advantage?
Alternative: Use ArraySet implementing SetADT
3
Java’s Set ADT

set: an unordered collection with no duplicates

main purpose of a set is to test objects for
membership in the set (contains)

Java has an interface java.util.Set to represent
this kind of collection


Set is an interface; you can't say new Set()
There are two Set implementations in Java:


HashSet, TreeSet
Java's set implementations have been optimized so that it is
very fast to search for elements in them
4
Java Set interface

interface java.util.Set<T> has the following
methods:

they are exactly those of the Collection interface
int size();
boolean isEmpty();
boolean contains(T e);
boolean add(T e);
boolean remove(T e);
Iterator iterator();
boolean containsAll(Collection c);
boolean addAll(Collection c);
boolean removeAll(Collection c);
boolean retainAll(Collection c);
void clear();
T[] toArray();
T[] toArray(T[] a);
5
Limitations of Sets

Why are these methods missing from Set?






get(int index)
add(int index, Object o)
remove(int index)
How do we access the elements of the set?
How do we get a particular element out of the
set, such as element 0 or element 7?
What happens when we print a Set? Why
does it print what it does?
6
Iterators for Sets


A set has a method iterator to create an
iterator over the elements in the set
The iterator<T> has the usual methods:



public boolean hasNext()
public T next()
public void remove()
7
Typical set operations

sometimes it is useful to compare sets:

subset: S1 is a subset of S2 if S2 contains every element
from S1.


containsAll tests for subset relationship
it can be useful to combine sets in the following ways:

union: S1 union S2 contains all elements that are in S1 or
S2.


intersection: S1 intersect S2 contains only the elements
that are in both S1 and S2.


addAll performs set union
retainAll performs set intersection
difference: S1 difference S2 contains the elements that are
in S1 that are not in S2.

removeAll performs set difference
8
Set practice problems


Given a List of elements or string of many
words, determine if it contains any duplicates,
using a Set. (You can use a Scanner to break
up a String by words.)
Write the Moby Dick word testing program.
9
Set implementation




Should we implement a set using a list?
lists are bad for certain operations

insertion at arbitrary index:
add(index, element)

searching for an element:
contains(element), indexOf(element)

removal from arbitrary index:
remove(index)
all these operations are O(n) on lists! (bad)
use a balanced binary search tree to implement them!
10
Java Collections Framework
11
Java Set interface

interface java.util.Set<T> has the following
methods:
(they are exactly those of the Collection interface)
public
public
public
public
public
public
public
public
public
public
public
public
public
boolean add(T e);
boolean addAll(Collection c);
void clear();
boolean contains(T e);
boolean containsAll(Collection c);
boolean isEmpty();
Iterator iterator();
boolean remove(T e);
boolean removeAll(Collection c);
boolean retainAll(Collection c);
int size();
T[] toArray();
T[] toArray(T[] a);
12
Set implementations in Java

Set is an interface; you can't say new Set()

There are two implementations:

TreeSet: a (balanced) BST storing elements
HashSet: a hash table storing the elements

we have essentially implemented TreeSet



Java's set implementations have been optimized so
that it is very fast to search for elements in them
HashSet is faster than TreeSet for most
operations
13
Mapping between sets

sometimes we want to create a mapping
between elements of one set and another set

example: map people to their phone numbers



"Marty Stepp"
"Jenny"
-->
-->
"692-4540"
"867-5309"
How would we do this with a list (or list(s))?



A list doesn't map people to phone numbers; it
maps ints from 0 .. size - 1 to objects
Could we map some int to a person's name, and
the same int to the person's phone number?
How would we find a phone number, given the
person's name? Is this a good solution?
14
A new ADT: Map

map: an unordered collection that associates a
collection of element values with a set of keys so that
elements they can be found very quickly



Each key can appear at most once (no duplicate keys)
A key maps to at most one value
the main operations:



put(key, value)
"Map this key to that value."
get(key)
"What value, if any, does this key map to?"
maps are also called:



dictionaries
associative arrays
(depending on implementation) tables, hashes, hash tables
15
Java's Map interface
Basic ops
public interface Map<K,V> {
public V put(K key, V value);
public V get(K key);
public V remove(K key);
public boolean containsKey(K key);
public boolean containsValue(V value);
public int size();
public boolean isEmpty();
public void putAll(Map<K,V> map);
public void clear();
Bulk ops
Collection
views
public Set<K> keySet();
public Collection<V> values();
}
Note that there are 2 generic types here!
16
Implementing Map with a tree

Make a BST of entries, sorted on the keys.
Each entry also contains the associated value
17
Map example
public class Birthday {
public static void main(String[] args){
Map<String,Integer> m =
new HashMap<String,Integer>();
m.put("Newton", new Integer(1642));
m.put("Darwin", new Integer(1809));
System.out.println(m);
}
}
Output:
{Darwin=1809, Newton=1642}
18
Some Map methods in detail

public V get(K key)


public boolean containsKey(K key)


returns the value at the specified key, or null if
the key is not in the map (constant time)
returns true if the map contains a mapping for the
specified key (constant time)
public boolean containsValue(V val)


returns true if the map contains the specified
object as a value
this method is not constant-time O(1) ... why not?
19
Collection views

A map itself is not regarded as a collection



Map does not implement Collection interface
although, in theory, it could be seen as a collection
of pairs, or a relation in discrete math terminology
Instead collection views of a map may be
obtained


Set of its keys
Collection of its values (not a set... why?)
20
Iterators and Maps


Map interface has no iterator method; you can't get an Iterator
directly
must first call either



keySet()
values()
returns a Set of all the keys in this Map
returns a Collection of all the values in this Map
then call iterator() on the key set or values

Examples:
Iterator<K> keyItr = grades.keySet().iterator();
Iterator<V> elementItr = grades.values().iterator();

If you really want the keys or element values in a more familiar
collection such as an ArrayList, use the ArrayList constructor that
takes a Collection as its argument
ArrayList elements = new ArrayList(grades.values());
21
Examining all elements

Usually iterate by getting the set of keys, and iterating
over that
Set<K> keys = m.keySet();
Iterator<K> itr = keys.iterator();
while (itr.hasNext()) {
K key = itr.next();
System.out.println(key + "=>" +
m.get(key));
}
Output:
Darwin => 1809
Newton => 1642
22
Map practice problems

Write code to invert a Map; that is, to make the values the keys
and make the keys the values.
Map<String,String> byName = new HashMap<String,String>();
byName.put("Darwin", "748-2797");
byName.put("Newton", "748-9901");
Map byPhone<String,String> = new HashMap<String,String>();
// ... your code here!
System.out.println(byPhone);
Output:
{748-2797=Darwin, 748-9901=Newton}

Write a program to count words in a text file, using a hash map
to store the number of occurrences of each word.
23
Map Usage Summary


Maps manipulate keys rather than the entire
object
Useful because


allow collections collections to be smaller, more
efficient, and easier to manage
also allows for the same object to be part of
multiple collections by having keys in each
24
TreeSet and TreeMap details


Both the TreeSet and TreeMap classes are
red/black tree implementations of a balanced
binary search tree
Operations, as listed from Lewis and Chase, are
in the next tables.

The tables do not list the generic types version (the
tables reflect Java 1.4.2, not 1.5).
25
TABLE 13.1 Operations on a TreeSet
26
TABLE 13.2 Operations on a TreeMap
27
References


Lewis & Chase book, End of chapter 13.
Java API (available online)
28