Constructing Sets

• Choose between hash set and tree set
• Use tree set if you want to visit in sorted order
  • Elements need to be Comparable, or supply a Comparator
• Otherwise use hash set
  • a bit more efficient - if the hash function is well chosen
  • hash function is the method of determining the hashcode

Constructing Sets

• Store reference in variable of type Set

  Set<String> names = new HashSet<>();
  Set<String> names = new TreeSet<>();
  Set<String> names = new TreeSet<>(myComparator);

• After you construct the collection object, the implementation no longer matters
  • only the interface is important
  • that is why we declare it as a Set

Working with Sets

Set<String> names;	Use the interface type for variable declarations
names = new HashSet<>();	Use a TreeSet if you need to visit the elements in sorted order.
names.add("Romeo");	Now names.size() is 1
names.add("Fred");	Now names.size() is 2
names.add("Romeo");	names.size() is still 2. You can’t add duplicates.
if (names.contains("Fred"))	The contains method checks whether a value is contained in the set. In this case, the method returns true.
System.out.println(names);	Prints the set in the format [Fred, Romeo]. The elements need not be shown in the order in which they were inserted.
for (String name : names) {...}	Use this loop to visit all elements of a set. (You can also use an iterator.)
names.remove("Romeo");	Now names.size() is 1
names.remove("Juliet");	It is not an error to remove an element that is not present. The method call has no effect.
Iterator<String> iter = names.iterator();	Gets an iterator

Working with Sets

If you want to iterate through the Set removing some elements, you need to use an Iterator.

Iterator<String> iter = names.iterator();
while (iter.hasNext())
{
    String name = iter.next();
    //Do something with name
}

Iterator

• A set iterator visits the elements in the order in which the set implementation keeps them.
  • not necessarily the order in which you inserted them.
• The order of elements in a hash set can seems quite random
  • the hash code spreads the elements into different groups.
• When you visit elements of a tree set, they always appear in sorted order
  • even if you inserted them in a different order.

Iterator vs ListIterator

• The ListIterator has an add method to add an element at the list iterator position.
• The Iterator interface does not.
• It makes no sense to add an element at a particular position in a Set
  • the set can order the elements any way it likes
  • Thus, you always add elements directly to a set, never to an iterator of the set.
• You can remove a set element at an iterator position
• The Iterator interface has no previous method

Demo

Let's look at a demo of a rudimentary spell check that use sets

• read in all words from a dictionary file and add them to a set.
• read all words from a document—here, the book Alice in Wonderland—into a second set.
• Print all words from the second set that are not in the dictionary set.
• These are the potential misspellings.

SpellCheck.java

• Get SpellCheck.java from big java code file
• Put the word files at the project level

Class Question #1

What is wrong with the following test to check whether the Set<String> s contains exactly the elements "Tom", "Diana", and "Harry"?

if (s.toString().equals("[Thomas, Diana, Harry]")) . . .

1. there is no equals method for this class
2. a set is an unordered data set
3. all elements in a set are unique
4. "Thomas" will be printed last because it is longest

What should you do instead?

 

Class Question #2

Suppose you changed line 40 of the SpellCheck program to use a TreeSet instead of
a HashSet.

1. What else would need to change?
   1. everything
   2. nothing
   3. it won't compile
   4. the return type of the method
2. How would the output change?

Maps

• Associates keys and values
• Example: Name -> Color pairing is a Map<String, Color>
• Two implementations: HashMap and TreeMap
• Both implement the Map interface
  • TreeMap visits the keys in sorted order

Working with maps

Map<String, Integer> scores;	Keys are strings, values are Integer wrappers. Use the interface type for variable declarations.
scores = new TreeMap<>();	Use a HashMap if you don’t need to visit the keys in sorted order.
scores.put("Harry", 90); scores.put("Sally", 95);	Adds keys and values to the map.
scores.put("Sally", 100);	Modifies the value of an existing key.
int n = scores.get("Sally"); Integer n2 = scores.get("Diana");	Gets the value associated with a key, or null if the key is not present. n is 100, n2 is null.
System.out.println(scores);	Prints scores.toString(), a string of the form {Harry=90, Sally=100}
for (String key : scores.keySet()) { Integer value = scores.get(key); . . . }	Iterates through all map keys and values.
scores.remove("Sally");	Removes the key and value.

Class Question 4

The values of a map form what kind of collection?

1. A set
2. A stack
3. A list
4. None of the above

Class Question 5

Suppose you want to implement an index that shows the pages on which each particular word occurs. What is a good data structure for this purpose?

1. TreeMap<Integer, TreeSet<String>>
2. TreeMap<String, TreeSet<Integer>>
3. TreeSet<TreeMap<String, Integer>>
4. TreeSet<TreeMap<Integer, String>>

Hash Functions

• Object class has a hashCode method
• Computes an integer for each object
• Override in your own class to be compatible with equals
• Hash code should depend on object contents
• Hash code should “spread around” objects into different numbers
• It's ok to have a few “collisions”—objects with the same hash code

Example: Hash code for String

final int HASH_MULTIPLIER = 31;
int h = 0;
for (int i = 0; i < s.length(); i++)
   h = HASH_MULTIPLIER * h + s.charAt(i);  

eat	100184 = 31 * (31 * 'e' + 'a') + 't'
tea	114704
Juliet	–2065036585
Ugh	84982
VII	84982

Implementing Hash Functions

• Form hash code using each of the instance variables that are compared in equals
• Combine these hash codes

public class Country
{
   public int hashCode()
   {
      int h1 = name.hashCode();
      int h2 = new Double(area).hashCode();
      final int HASH_MULTIPLIER = 31;
      int h = HASH_MULTIPLIER * h1 + h2;
      return h;
   }
}