Turning a Key Into an Address

Last timeFinding One Thing Among Many

A hash function squeezes a huge space of possible keys into a small table of positions. Sending two keys to the same place is then unavoidable, and knowing that early shapes everything after.

The last lesson left one requirement: a rule that turns any key into a

position in a small table, using only the key. This lesson builds it and then

proves it cannot be perfect.

FIG 1From a key to a position

: the key, of whatever kind, read as bytes
: the hash, a large whole number computed from those bytes
: the number of positions in the table
: the position, somewhere from zero to one less than m

The first step is the interesting one and the second is a squeeze. A good hash mixes the bytes so that every one of them affects the result and two similar keys give unrelated numbers; a bad one, such as adding the bytes together, gives the same number for any rearrangement of the letters, which sends a great many real keys to the same place. The remainder then folds that number into the table, and when the table size is a power of two it amounts to keeping the lowest bits. The whole computation looks at the key and nothing else, which is exactly the property that makes the lookup independent of how much is stored.

FIG 2How many keys could exist against how many positions there are

	digits in the count of p	digits in the count of p	digits in the keys per p
eight character lowercas	12	7	6
email addresses up to fo	61	7	55
sixty four bit identifie	20	7	14
any file of one megabyte	2525223	7	2525217

The numbers are too large to write out, so each cell counts digits instead: a table of a million positions is seven digits, and the last column is how many possible keys share each position on average. Even the modest first row, eight lowercase letters, puts a six digit number of possible keys on every slot. Nothing about the quality of the hash touches this, because a function from a larger set to a smaller one cannot be one to one. A hash table is therefore not a structure that avoids collisions. It is a structure that survives them, and the next lesson is about how.

Why it cannot be perfect

One consequence is worth stating now. Because arriving at a position does not

prove that the item found there is the one wanted, every lookup must compare

the full key once it gets there. A hash narrows the search to one slot; the

comparison confirms it.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Turning a Key Into an Address

Why it cannot be perfect

1 more paragraph to go

This is the reading half

Read alongside