In lesson 1, a linear search of a 100,000-item library cost 100,000 comparisons. In lesson 6, binary search cut that to 17 — but demanded sorted data, and the sorting cost lessons 7 to 9.

In this lesson a search will cost about one comparison. Whether the library holds a thousand items or a million.

How

Stop searching. Compute where the item must be.

A hash function turns a title into a number, and the number names a position in the table. One calculation, one position — no search at all.

That sounds too good, and it is: two different titles can produce the same number. That is a collision, and handling it is the entire engineering of this lesson.

What you pay

Every structure so far gave something up to get something. This one gives up the most:

A hash table buys O(1) and pays with ORDER.

An array knows what comes first. A sorted array supports binary search. A hash table knows nothing about order — only "is this key present".

No alphabetical listing. No ranges ("everything from B to D"). No "what comes after this one". No minimum, no maximum.

In step 8 you will ask your own index for the library in alphabetical order, and it will not answer. That unanswered question is where lesson 11 begins.

Guess before you read on

You will build a table of buckets and chains. When there are too few buckets, the chains get longer.

How many comparisons per lookup, on average, with 10,000 items and only 128 buckets?

Write the number down. Step 5 has a table with it in.