Class 11 — Wednesday, September 30

A map that is holding a key and cannot find it, and the same move in a list and a tree set. Then the hash set, built by hand.

Sections 1 to 3 run on the projector — keyboards down, and section 2 wants a prediction in the Journal before anything runs. From section 4 you are in pairs, typing two files of your own.

  1. A map, in five lines
  2. The key that went missing — predict first
  3. The same move, three collections
  4. Build the buckets
  5. Watch it go wrong, three ways
  6. Take one out
  7. The nearest key
  8. Which way the rule goes
  9. A value beside each key
  10. Walk it with for-each

Sections 1 to 5 are the class. Sections 6 to 10 go past anything you have been asked for — take them in order if you get there.

1. A map, in five lines

Keyboards down.

A Set holds things. A Map holds things and a value for each one. The thing is called the key.

Map<String, Integer> ages = new HashMap<>();
ages.put("Ada", 36);
ages.put("Alan", 41);

System.out.println(ages.get("Ada"));          // 36
System.out.println(ages.containsKey("Ada"));  // true
System.out.println(ages.get("Grace"));        // null

put stores a pair. get hands back the value for a key, or null when the key is not there. Each key is in the map once: a second put with the same key replaces the value. A set’s add says the same thing its own way: it returns false when the thing was already there.

A HashMap finds a key the way a HashSet finds an element. It asks the key for its hashCode, goes to the one place that number names, and only then asks equals of what it finds there. Same two methods, same order, and the same rule from Class 6 about the two agreeing.

2. The key that went missing

Keyboards down. Prediction before it runs.

This is the Point from Class 6, with one difference: it can move. Both fields have lost their final, and there is a moveTo.

import java.util.Objects;

public class Point {
    private int x;
    private int y;

    public Point(int x, int y) { this.x = x; this.y = y; }

    public void moveTo(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Point that)) return false;
        return this.x == that.x && this.y == that.y;
    }

    @Override
    public int hashCode() { return Objects.hash(x, y); }

    @Override
    public String toString() { return "(" + x + ", " + y + ")"; }
}

equals and hashCode are both correct and they agree. Now a point goes into a map as a key, and then it moves:

Point home = new Point(3, 4);

Map<Point, String> labels = new HashMap<>();
labels.put(home, "home");

home.moveTo(3, 5);

System.out.println(labels.containsKey(home));
System.out.println(labels.get(home));
System.out.println(labels.size());
System.out.println(labels);

Write your answer in the Journal before it runs. Four lines, and a guess counts as a line.

What do the four lines print?

false
null
1
{(3, 5)=home}

Read the last two lines against the first two. The map is holding the point. It says so: size 1, and there it is, at (3, 5), labelled home. And it cannot find it.

Nothing in hashCode changed. The point changed, so the number hashCode returns changed with it — 1058 before the move, 1059 after. The map looks in the place 1059 names. The entry is sitting in the place 1058 named, where it was put.

Asking for new Point(3, 4) does not find it either: that goes to the right place, and finds a point that now says it is (3, 5).

Nothing warned you. Both methods are correct. What broke the rule was a field that could change.

3. The same move, three collections

Keyboards down.

A list, a hash set and a tree set each look for things in their own way. Here is section 2’s move in all three. For the tree set, Point also has a compareTo: by x, then by y.

Point home = new Point(3, 4);
List<Point> list = new ArrayList<>(List.of(new Point(5, 5), home));
Set<Point> hashed = new HashSet<>(list);
Set<Point> sorted = new TreeSet<>(list);

home.moveTo(6, 0);

System.out.println(list.contains(home) + " " + hashed.contains(home) + " " + sorted.contains(home));

Which of the three can still find it?

true false false
  • The list looks everywhere. contains walks every element and asks equals, and the moved point is still equal to itself. Always right, and slow.
  • The hash set looks in one bucket: the one the point’s number names now. The point is in the bucket its old number named.
  • The tree set walks down from its top, and compareTo says which way to turn at each step. (5, 5) went in first, so it is at the top, and (3, 4) went to its left. (6, 0) is bigger than (5, 5), so the walk turned right, and the point is not there.

Move it to (3, 5) instead and the tree set finds it: (3, 5) is still smaller than (5, 5), so the walk turns left, as it did for (3, 4). A tree set loses a changed element only when the change moves it past a neighbour. A hash set loses it almost every time.

4. Build the buckets

Keyboards up. Pairs. A new file, in any project you have open.

Now the machine, so that section 2 stops being a mystery.

It is built out of lists. An ArrayList is an array that grows, and you need five things from it: add, contains, remove, get and size. contains and remove use equals to find what you ask for. A BucketSet is a list of buckets, and each bucket is a list of the things in it. BucketSet.java:

import java.util.ArrayList;
import java.util.List;

public class BucketSet {

    private final List<List<Object>> buckets;

    public BucketSet(int bucketCount) {
        buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    private List<Object> bucketFor(Object o) {
        ...
    }

    public boolean add(Object o) {
        ...
    }

    public boolean contains(Object o) {
        ...
    }

    @Override
    public String toString() {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < buckets.size(); i++) {
            out.append(i).append(": ").append(buckets.get(i)).append('\n');
        }
        return out.toString();
    }
}

Three methods to write.

  • bucketFor turns an object into the one bucket it can be in. Ask the object for its hashCode, and turn that number into an index between 0 and buckets.size() - 1.
  • add puts the object in that bucket — unless an equal one is already there, in which case it does nothing. Return whether it added.
  • contains looks in that one bucket, and nowhere else. A List already has a contains, and it uses equals.

Then, in a main, eight buckets and nine words:

BucketSet words = new BucketSet(8);
for (String w : new String[] {"cod", "hen", "bee", "yak", "dog", "owl", "emu", "cat", "ant"}) {
    words.add(w);
}
System.out.print(words);
System.out.println(words.contains("owl") + " " + words.contains("elk"));

Done when you get

0: [cod]
1: [hen]
2: [bee]
3: [yak]
4: [dog, owl]
5: [emu]
6: [cat]
7: [ant]
true false

Two words share bucket 4. That is the only place equals was ever called today. contains("owl") went to bucket 4 and compared two things. contains("elk") went to bucket 4 too, found nothing that matched, and never looked anywhere else.

dog and owl share a bucket and are not equal, and nothing went wrong: equals told them apart. Two different words can even have exactly the same hashCode — "Aa" and "BB" both have 2112. Equal things must get the same number. Things with the same number do not have to be equal. The rule goes one way only.

Now add one more word, and run it again:

words.add("bucket");
java.lang.IndexOutOfBoundsException: Index -6 out of bounds for length 8

"bucket".hashCode() is -1378203158. A hash code is any int, and half of all ints are negative. % of a negative number is negative, and -6 is not a bucket.

Math.floorMod(h, buckets.size()) does what % was supposed to do. Swap it in and bucket lands in bucket 2.

The nine three-letter words all happened to hash positive. A test that only ever uses small inputs does not find this.

5. Watch it go wrong, three ways

Same two files. Type in the Point from section 2 beside BucketSet.

First: the constant. Change Point.hashCode to return 0; and put three points in.

BucketSet points = new BucketSet(8);
points.add(new Point(1, 1));
points.add(new Point(2, 5));
points.add(new Point(7, 0));
System.out.print(points);
System.out.println(points.contains(new Point(2, 5)) + " " + points.contains(new Point(5, 2)));

Predict the last line before you run it.

0: [(1, 1), (2, 5), (7, 0)]
1: []
...
7: []
true false

Everything in bucket 0, and every answer is right. contains goes to bucket 0, and everything is there to be compared with. With a thousand points it would compare a thousand times per question. Slow, and correct.

Second: no hashCode at all. Delete hashCode from Point, so that it is Class 6’s point: a correct equals and nothing else. Put the same point in three times:

BucketSet points = new BucketSet(8);
points.add(new Point(2, 5));
points.add(new Point(2, 5));
points.add(new Point(2, 5));
System.out.print(points);

Predict how many (2, 5)s the set holds.

Your buckets may differ from ours:

0: []
1: []
2: [(2, 5)]
3: []
4: [(2, 5)]
5: []
6: []
7: [(2, 5)]

Three equal points, in three buckets. Point still had a hashCode: Object’s. It comes from the object, not from x and y, so each new point got a number of its own, and add found an empty bucket each time. equals was never asked.

That is what happened to Class 6’s set: it looked for the new point in the bucket the new point’s number named, and the equal one was in another.

Third: the move. Put Objects.hash(x, y) back. Now section 2, inside your own set:

BucketSet set = new BucketSet(8);
Point home = new Point(3, 4);
set.add(home);
home.moveTo(3, 5);
System.out.println(set.contains(home));
System.out.print(set);

Predict both the true/false and which bucket the point is printed in.

false
0: []
1: []
2: [(3, 5)]
3: []
...

The point is in bucket 2, because Objects.hash(3, 4) is 1058 and 1058 mod 8 is 2. contains asked the point for its hash code now, got 1059, went to bucket 3, and found it empty.

Compare the three runs. The constant hash code put everything in one bucket: slow, and every answer right. No hashCode put three equal points in three buckets. The moved point is in the wrong bucket: fast, and the answer is wrong. Only the first one is not a bug.

Done when one of you can say, without looking, which bucket the point is in and which bucket contains looked in.

If an element has to change, there are three ways to keep a collection from losing it:

  • Take it out, change it, put it back. remove it while it still has its old number, then add it again, and the set files it under the new one.
  • Change a value, not a key. A map files only its keys. In a Map<String, Point>, the name is the key, and the point can move all it likes.
  • Make the key unable to change, so there is nothing to lose: final fields, and a moveTo that returns a new point. Monday’s reading is about this one.

6. Take one out

Write remove. It takes out the object equal to the one you pass, from the one bucket it can be in, and returns whether there was one to take out.

public boolean remove(Object o)

Done when removing "dog" leaves "owl" in bucket 4, and removing "dog" a second time returns false.

Then try this, and explain the answer to each other before opening the box:

BucketSet set = new BucketSet(8);
Point p = new Point(3, 4);
set.add(p);
p.moveTo(3, 5);
System.out.println(set.remove(p));
System.out.print(set);

false, and the point is still there. remove looks in the bucket the point’s current hash code names, and it is not in that one. A key that has moved cannot be found, and it cannot be removed either. It is in the set until the set is thrown away.

7. The nearest key

A hash map finds a key that is equal to the one you ask for, and nothing else. A TreeMap keeps its keys in order, so it can also find the nearest one. Here are grade boundaries:

TreeMap<Integer, String> letters = new TreeMap<>();
letters.put(90, "A");
letters.put(80, "B");
letters.put(70, "C");
letters.put(60, "D");
letters.put(0, "F");

letters.floorKey(87) is the largest key that is 87 or less, which is 80. floorEntry(87) hands back that key together with its value.

Write letter(int mark), which returns the letter for a mark.

Done when 87, 90, 59 and 100 give B A F A.

Then predict these three lines, and run them:

System.out.println(letters.headMap(70));
System.out.println(letters.tailMap(70));
System.out.println(letters.floorKey(-5));
{0=F, 60=D}
{70=C, 80=B, 90=A}
null

headMap is everything below 70, and tailMap is 70 and everything above it. Below 0 there is no floor, so floorKey gives null, the way get does for a missing key. Make letter(-5) return "?" instead of crashing.

8. Which way the rule goes

The rule from Class 6 is one sentence: equal objects must have the same hash code. Here are two ways to change Point on purpose. Only one of them breaks the rule.

First, keep equals as it is and give Point this hashCode:

@Override
public int hashCode() { return x; }

Add (1, 2) and (1, 3) to a BucketSet(8), print it, and ask it whether it contains each of them.

Second, put Objects.hash(x, y) back, and change equals so that it compares x only. Add (1, 2). Print whether new Point(1, 2) equals new Point(1, 3), and whether the set contains new Point(1, 3). Then add (1, 3) and print the set.

Predict every line before you run it.

The first:

0: []
1: [(1, 2), (1, 3)]
2: []
...
true true

The two points have the same number and are not equal. They share a bucket, equals tells them apart, and every answer is right. That is allowed.

The second:

true false
0: []
1: []
2: [(1, 2)]
3: [(1, 3)]
...

equals says the two points are equal. The set cannot find one from the other, and then it holds both. Two equal points, two numbers: that is the rule broken.

Done when you can say which change broke the rule, and why the other one did not. Then put equals back.

9. A value beside each key

A HashMap is a HashSet where each thing in a bucket carries a value along with it. Make BucketMap. It is built the way BucketSet is, with one change: a bucket holds small pair objects, each holding a key and its value, instead of the keys themselves.

public void put(Object key, Object value)
public Object get(Object key)
public boolean containsKey(Object key)

put on a key that is already there replaces that pair’s value, the way HashMap’s does. get goes to the key’s bucket, looks for the pair whose key equals the one asked for, and returns its value, or null. containsKey asks the same bucket the same question and says whether it found one.

Done when the five lines from section 1 work against your BucketMap instead of HashMap and print the same three answers. Then put("Ada", 37) and print the buckets: Ada=37 is there once, and Ada=36 is gone.

Then run section 2 against it, and print the buckets. Now you can see the entry the HashMap was holding and could not find.

10. Walk it with for-each

A for (String w : words) loop works on a list because a list is Iterable. Make BucketSet one too:

import java.util.Iterator;

public class BucketSet implements Iterable<Object> {
    ...
    @Override
    public Iterator<Object> iterator() {
        ...
    }
}

Done when this prints the nine words, bucket by bucket:

for (Object o : words) {
    System.out.print(o + " ");
}
cod hen bee yak dog owl emu cat ant

The short way is to copy everything into one ArrayList and return that list’s iterator(). Then do it the long way: an Iterator of your own that walks the buckets where they are and copies nothing. Write it as a class inside BucketSet, without static, so that it can see buckets. It needs hasNext and next, and two numbers: which bucket it is in, and how far along that bucket it is. Empty buckets are the part to get right, and an empty set should print nothing at all.