Transcript Maps

CS2110: Software Development Methods
Maps and Sets in Java
These slides are to help with the lab, Finding Your
Way with Maps
This lab uses Maps, and Sets too (but just a little).
Readings from textbook:
(a) Map introduction: Section 8.2.1 (pp. 521-523)
(b) Map interface: Section 9.3.4 (pp. 636-640)
(c) Set interface: Section 9.3.2 (pp. 624-627) -Maps use Sets so this is needed, but it's simple
Lists, Sets and Maps in Java
• Java has what’s called a Collections Framework
• Includes very useful classes like ArrayList
• Also, other useful classes for other data types
• Sets
• Data model: a collection of items
• Operations: membership, insert, delete
• Maps: like a “lookup table”
• Data model: each data item stored with a lookup key
• Operations: retrieve with the key, etc.
Collection Interface
• All collections implement the Collection interface.
• Helpful! all the collection classes have common
operations!
boolean add(Object obj);
Iterator iterator();
int size();
boolean isEmpty();
boolean contains(Object obj);
boolean containsAll (Collection other);
…
• See Java API documentation for all methods
Set and HashSet in Java Collections
• A Set is a collection of items that
• are unordered
• are unique (no duplicates)
• What kind of operations do we think of?
• element membership (add, remove, isMember, etc.)
• manipulation (union, intersection,…)
• Java gives us:
• Set – an interface
• Several implementation classes, including TreeSet
• And HashSet, but we’ll use TreeSet for now
Java’s Set Interface (see MSD, p. 625)
• The Set interface looks just like the Collection
interface, but with more specific behaviors
• boolean add(elem) – returns false if already there
• boolean remove(elem) – returns false if not there
• What’s sweet here:
• Try to add something that’s already there?
Remove something that’s not there? No problem!
• It basically ignores that attempt!
• This allows some powerful methods to be very
short
• See examples on pages 625 and 626
Examples using Set
• How many unique items in any Collection object?
int numUniq = new TreeSet(someList).size();
• Creates a new set “on the fly” using the constructor
that adds all items from an existing collection
• Remove duplicates from any Collection object?
Set noDups = new TreeSet( someList );
someList.clear();
someList.addAll( noDups );
• Note we don't have to iterate
• We rely on useful constructors and bulk operation
Using Sets in Java: TreeSet class
• TreeSet is a concrete class that implements Set
• How's it work inside? How is it implemented?
• We won't focus on that in CS2110 (not now anyway)
• Because it's a well-implemented abstraction, you don't
need to understand what's in the black-box
• The “tree” refers to type of data structure used
• But you do need one thing:
• All items must be Comparable
• All items must correctly implement compareTo()
• Bonus! Iterating over a TreeSet uses compareTo()'s
ordering. So prints in “correct” order
Common Situation: “data lookup”
• We have some some information, and
we want to retrieve it or look it up
• We find it quickly by using some special data
value. Let’s call that a key
• Examples of keys and data values used in
lookup?
• Often use term “lookup table” for these.
• Databases work this way, don’t they?
What if we had a “Type” for a Table?
• Called “Map” in Java: find data given some key
value
• Map’s model of information
• Some set of values, each associated with a key
• Operations
• Lookup: given a key, retrieve the values
• Insert, remove, updates, etc.
• How could we implement this?
• You’ve been using lists (arrays, ArrayLists) and the
contains() and indexOf() methods
• Disadvantages?
Java Type: Maps
• Map Interface
• Like sets, but have <key, value> instead of <value>
• Examples in real life?
• Dictionary: word to its definition (or list of definitions)
• email to Facebook Profile
• Host Names to IP addresses
• How to declare: Map<KeyType,ValueType>…
Examples:
Map<String,Integer> // maps string to a number
Map<Student,String> // maps Student to a String
Map<String,ArrayList<Course>> // e.g. a schedule
Important Map Methods
• Keys and values
• put (key, value), get(key), remove(key)
• containsKey(key), containsValue(value)
• Can think of a Map as a set of keys and a set of
values
• keySet() // returns a Set of key values
• values() // returns a Collection of values
• Others methods too! See doc or a Java
reference.
Concrete Classes
• Map is an interface. We need concrete classes
that implement it.
• HashMap
• Often used. Allows nulls as values.
• Need a hashCode() method
• String and other classes Java gives us have this
• More later on doing this for our own classes
• TreeMap
•
•
•
•
We’ll use this one in CS2110!
Uses a search tree data structure
Values stored in a sorted order
Keys must implement Comparable!
Why Are Maps Useful and Important?
• “Lookup values for a key” -- an important task
• We often want to do this!
• Need flexibility for what values are stored for a given
key
• Need to use objects other than Strings or ints as key
values
• Efficiency matters for large sets of data
• These are fast!
In Our Lab on Maps
• Demo now in class!
• Pay attention please and learn
• In lab, you’ll do more on this kind of demo
• In lab, you’ll have access to a Zip file with:
• MapDemo0.java – the demo we will do now
• MapDemo.java – the lab exercise you and your
partner will do afterwards
MapDemo0.java file
• We define a set and a map
• We get a scanner for a file that looks like this:
Cavman
101 JPA, Apt. 3. C'ville, VA 22900
Tom
Monticello, C'ville, VA 22900
• Task 1: store the names in the set
• Task 2: store (name,address) pairs in the map
• Task 3 (if time): split the address-line into
words and store each of them in the set
• Task 4: read key and look it up in Map