Hash Tables: From Key to Slot

A hash table stores values under keys, and finds the value for a key without searching, by turning the key into the index of a slot in an array. This card covers the function that does the turning, why two keys can land in the same slot, and what each operation costs.

A cloakroom works the same way. The number on a ticket tells the attendant which hook holds the coat, so nobody searches the rail. The likeness breaks at the hook: two coats never share one, but two keys often share a slot.

A hash function takes a key and returns a whole number, its hash code. The table keeps an array of slots, called buckets, and puts each key in the bucket whose index is the hash code mod the capacity, where the capacity is the number of buckets and mod gives the remainder after dividing. A lookup repeats the same calculation and goes straight to that bucket. When two different keys land in one bucket, they collide, and every hash table needs a rule for a collision.

A run used Java's hash function for strings, String.hashCode, to place five words in eight buckets. Each language computes its own hash codes, and Python's change from one run of a program to the next, so these numbers belong to Java alone.

Fig and plum share bucket 4, although their hash codes differ, because with only eight buckets many hash codes leave the same remainder. A good hash function spreads keys evenly, so that each bucket holds few of them, and every fast cost below depends on that. Such a cost is expected, meaning it holds on average when keys spread evenly, and not for every possible set of keys.

In general, a hash table trades order for speed. Amortised, in the insert row, means averaged over many inserts. The table finds a key without searching, but it holds its keys in no useful order, so a question such as the smallest key, or every key between 10 and 20, means looking at all of them.