Explain how a lookup answers in the same time whether it is holding ten items or ten million, what a hash function has to do for that to hold, what happens when two keys land in the same place, and what this structure can never do

Finding It Instantly

The hash table, derived rather than used. Turning a key into an address, handling the collisions that follow, and knowing what you gave up to get an instant answer.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

This is course 2 of 8 in a reading track: tell in advance which approach survives a million rows. The track is an order, not a gate, and the rest of it is on one page.

01Finding One Thing Among ManyScanning a pile costs whatever the pile holds. Computing where the thing lives costs the same whatever the pile holds, and the whole subject is about earning that second option.
02Turning a Key Into an Addressopening onlyA 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.
03When Two Keys Collideopening onlyTwo keys land on the same position, which is certain to happen. There are exactly two serious answers: hang a list off the slot, or go looking for another slot, and they fail differently.
04How Full Is Too Fullopening onlyThe cost of a lookup depends on one number: how full the table is. Keeping that number low means rebuilding the table bigger before it fills, and the rebuild is cheaper than it looks.
05What Makes a Hash Function Goodopening onlyA hash for a table needs three things: it must spread keys evenly, it must be fast, and it must give the same answer every time it is asked. A hash for a password needs almost the opposite.
06Asking Only Whether It Is Thereopening onlyIf the only question is whether something has been seen before, the items need not be stored at all. A few bits each will do, at the cost of a wrong answer that only ever goes one way.
07What a Hash Table Cannot Doopening onlyThe hash that scattered the keys destroyed their order, and with it every question about nearest, next, between and in order. That missing half is what the next course on this shelf is for.
08The Same Trick Everywhere Elseopening onlyOnce a key can be turned into a number, the same move places data on machines, recognises files already stored, and names things by their contents. The table was only the first use.