Hash Codes and Hash Functions

Imagine you keep a list of student records, and each record is tied to a student ID. If someone asks for the record of one particular ID, the simplest approach is to start at the beginning of the list and check each record until you find a match. That approach works, but the time it takes grows as the list grows. A hash table is a structure designed to answer the question, given a key, without that long scan.

A hash table stores key/value pairs, the same kind of data a HashMap holds. You can also use a hash table to implement a set. In a set there are no values, so the only question is whether a key is present. Either way, the central task is the same: given a key, find out where its information lives.

Suppose every key were a whole number from 0 to 99. Then you could reserve an array of 100 slots and store each pair in the slot whose index equals its key. Finding a pair would require no search at all. The pair for key 42 would sit in slot 42, and you would simply read that slot.

This idea breaks down quickly for realistic keys. An int can take a very large number of values, so an array with one slot for every possible int would be enormous, even if you only plan to store a few thousand items. If keys are strings of arbitrary length, the number of possible keys has no limit, and one slot per key cannot be built at all. The direct-indexing idea is good, but the array has to be much smaller than the set of possible keys. That tension is what hash tables resolve.

A hash table stores its data in an array, but the array index for a key is not the key itself. Instead, the index is computed from the key. A hash function is the piece that performs this computation: it takes a key and produces a hash code. The number that a key produces this way is its hash code, and a hash code is the array index where that key is stored.

The flow of a lookup runs in one direction. You start with the key you are looking for, pass it through the hash function, obtain a hash code, and go straight to that array location. The hash function is the only piece that knows how the key maps to a position, so the rest of the table never needs to inspect the other stored items to find the right one.

Because the lookup depends only on the key, the same key always produces the same hash code, and therefore the same array location. That repeatability is what lets you find a pair again later without searching for it.

The source describes the hash table approach as going directly to the place where the item is stored, with a caveat: this is close to true only when the hash table is working properly. Some extra checking can still happen inside a single location, which is discussed in the collisions section below.

The source pack does not detail how a large hash code is reduced to fit the size of a particular array, even though the array is much smaller than the set of possible keys. It describes the hash code as the array index. If you want the exact mechanism a specific language uses, consult that language's documentation.

The array has fewer locations than there are possible keys, so it is possible for two different keys to produce the same hash code. When that happens, both keys want the same array location. This situation is called a collision. The source is clear that a collision is not an error. A hash table cannot reject a key simply because another key already produced the same hash code. It has to be able to store both in some reasonable way.

The approach described for the Java style of hash table is to let each array location hold a linked list of key/value pairs. The list may be empty. When two items share a hash code, they both belong to the same linked list at that location.

In this illustration, slot 2 holds two pairs because "Ana" and "Ben" produced the same hash code. The other slots hold zero or one pair each, which is the typical situation when the table works well. The collision is visible only as a location with several pairs.

A hash code still tells you the array location, but that location may now hold several pairs. You must then check the keys in that list to find the one you want. Collisions therefore keep the table correct, at the cost of some extra checking inside a single location. If the hash table is working properly, that extra checking stays small. This is why the direct-access idea is described as close to true rather than exactly true.