Warm-up

Collide two strings on purpose

5 minfresher03 yrs

One concept, guided. Near-impossible to fail.

What this teaches

  • Unequal objects sharing a hash code is legal, not a bug
  • int has 4.3 billion values, so collisions are guaranteed by counting
  • equals() decides identity; the hash only picks the bucket

Starter

Starter.java
import java.util.*;

/**
 * Warm-up: collisions are normal.
 *
 * "Aa" and "BB" hash to the same int. That is not a JDK bug, and String is not
 * badly written — there are more possible Strings than there are int values,
 * so some pairs must collide.
 *
 * Run this, then do the two TODOs.
 */
public class Starter {

    public static void main(String[] args) {
        System.out.println("\"Aa\".hashCode() = " + "Aa".hashCode());
        System.out.println("\"BB\".hashCode() = " + "BB".hashCode());
        System.out.println("\"Aa\".equals(\"BB\") = " + "Aa".equals("BB"));

        // TODO 1: find another colliding pair and print it.
        //
        // Hint: String.hashCode() is s[0]*31^(n-1) + s[1]*31^(n-2) + ...
        // For two characters that is c0 * 31 + c1. So raising the first
        // character by one and lowering the second by 31 lands on the same
        // total. Start from "Aa" and work out the next pair by hand.

        // TODO 2: put both strings of your pair into a HashSet and print its
        // size. Predict the number before you run it.
        //
        // If collisions broke maps, the set could not hold both. Does it?
    }
}

Run it locally:

cd exercises/java/oop/hashcode-equals-contract/01-warmup
javac Starter.java -d /tmp/out && java -cp /tmp/out Starter

Done when

  • You print a second colliding pair that is not Aa/BB
  • You show a HashSet containing both colliding strings at the same time

← Back to What is the contract between hashCode() and equals()?