Handling Collisions in Hash Tables

Imagine you keep a list of student records, and each record is tied to a student ID. If someone asks for the record of a 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.

In an unsorted list you may have to look at many unrelated items before reaching the right one. In a binary sort tree you follow a path from the root downward. A hash table tries to remove that searching entirely by letting the key itself point to a location. The source describes this as going directly to the place where the item is stored, with the caveat that this is close to true only when the hash table is working properly. Keeping that caveat in mind matters, because collisions are the reason it is only close to true.

Suppose every key were a whole number from 0 to 99. 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 does this computing. The number a key produces this way is called its hash code. A hash code is therefore the array index where that key is stored.

The hash function is the only piece that knows how a key maps to a position. The rest of the table never has to inspect the other stored items to find the right one. In this example the key cat and the hash code 7 are illustrative values chosen to show the chain, not outputs of any particular hash function.

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

The array has fewer locations than there are possible keys, so two different keys can produce the same hash code. When that happens, both keys want the same array location. This situation is called a collision. 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. The hash code still tells you the array location, but that location may now hold several pairs, so you must check the keys in that list to find the one you want.

The values 4 and 9 in the diagram are illustrative. To find the pair for dog in slot 3, the lookup checks the key of the first entry, sees cat, moves to the next entry, and finds dog. The extra checking stays inside a single location. The source notes that if the hash table is working properly, that checking stays small, which is why the direct-access idea is described as close to true rather than exactly true.