Transcript Maps

CS2110: Software Development Methods
Maps and Sets in Java
These slides are to help with the lab, Finding
Your Way with Maps
More on these topics in lecture.
Today’s lab uses Maps (and Sets but just a
little).
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 HashSet
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
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
• Maps
• 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
• Most commonly 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
• Uses a search tree data structure
• Values stored in a sorted order
• More on this later.
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!
Demo
• Download the MapLab.zip file from the lab page
• In Eclipse, do the following:
• Select Import from the File menu
• Select “General” and then “Existing Projects into
Workspace”
• Choose “Select Archive File” and the find the
MapLab.zip file
• Two files in there:
• MapDemo0.java – the demo the TAs 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