Home > Articles > Programming > Java

  • Print
  • + Share This
From the author of

Hash Tables

The implementation of a HashSet in Java uses a hash table data structure. A hash table is a contiguous block of memory into which objects are slotted. Objects are slotted depending on their hash code. Hash codes are derived from an algorithm defined on the class of each object. The general goal of this algorithm is to produce as unique as possible a number, using data from each object. The hash table takes the result of this number modulus the table size in order to determine a precise slot.

In Java, you supply a hash code algorithm in the method hashCode. This method must return an int value. Right now, you have a broken test because you haven’t supplied a hashCode method. In the absence of your providing hashCode, Java uses the superclass definition found in Object. This default definition essentially uses the memory address of each object.

You have 52 card objects stored in the Deck’s set. In the test for containment, you create a new instance of an object that should be semantically equal to one already in the Deck. But this new instance by definition will have a separate memory address, so, in the absence of a custom hashCode definition, it won’t be reported as existing in the set.

Fixing this broken test would be a simple matter of supplying a hashCode method on Card:

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

If you try this experiment, or "spike," the tests pass. However, a hard-coded return value of 1 doesn’t seem right.

  • + Share This
  • 🔖 Save To Your Account