Java's hashCode()

In this course, we are primarily interested in implementing hash tables and not hash functions.

A Hash Table is a data structure which organizes data using hash functions in order to support quick insertion/removal and search.

The responsibility of a hash function is typically divided between the element and the data structure:

  • The first step, which converts the key to an integer (hash code), is done by the element (key) itself.

  • The second step, which reduces (compresses) the hash code to the range of array indices, is part of a general hash table implementation.

In Java, every "type" inherits hashCode() method from the Object class. The hashCode method returns a hash code value (an integer) for an object.

  • When using built-in types, you can simply call their hashCode method to get the hash code value.
  • When making your own custom types, you must provide an implementation of hashCode (override it).

As noted earlier, we are primarily interested in implementing hash tables and not hash functions. So, we take for granted that we can always ask for the hash code of an object by invoking the hashCode method on it.

Once we have the hash code for a given key, mapping that value to array indices can be as simple as follows:

// Compress hashcode to index range [0, M-1]
index = key.hashCode() % M;
Resources