Overriding hashCode()

Today, we learned about hash tables and how items are distributed using Object's hashCode()method. When we override the equals() method on one of our classes, we must override hashCode(), and attempt to satisfy the following properties:

If two objects are considered equal, their hash codes should be equal

If two objects are not considered equal, their hash codes should not be equal

Remember, property 1 is needed for correctness, while property 2 is desired for efficiency. In this lab, you'll get some experience overriding this method, and observe the consequences of different implementations of hashCode().

What to Do

First, you'll need two classes: a Driver class, and a Point2D class to override the hashCode()method on.

Driver

In the Driver class, add a main method which does the following:

Creates a HashSet of Point2D objects (use Java's HashSet implementation)

Inserts all of the points in the square from (0, 0) to (n, n) into the set (approximately n2points in total)

Times how long it takes to do the previous insertion

The value of n will depend on your implementation of hashCode() (see below). For good hash functions, large values of n are possible, for bad hash functions, you may see problems for n as low as 100.

Note: while we never call hashCode() directly, Java's HashSet implementation is similar to ours from class. Whenever an item is inserted into a HashSet, it will call our hashCode() method, and use that value to decide where to store the object.

Point2D

In the Point2D class, add two member variables: integers x and y. Add a constructor which sets both of these variables.

Next, add override the equals(Object other) method to return true iff the other object is a Point2D object with the same x and y coordinates.

Since we've overridden the equals method, we'll need to override hashCode(), so that equal points have equal hash codes. Add and test the following implementations of hashCode() on the Point2D object. Each time you implement a method, time it using your driver.

You will have several implementations of hashCode(), comment them out as you go, so we can see what you did. Above each implementation, add a comment stating whether the insertions were fast or slow, and whether it satisfies our two desired properties (see the overview). If an implementation seems slow, try to explain why.

Define hashCode() to return a constant (ex. always return 1)

Define hashCode() to return a random integer (using the Random class)

Define hashCode() to return one of the coordinates (either x or y)

Define hashCode() to return the sum of x and y

Define hashCode() to return the product of x and y

What to Submit

When you are finished, submit your source files to Canvas. These should include:

Driver.java

Point2D.java