Hash Table
Turns a key into a slot number so lookup does not have to search.
Decision · step 4 of 32Hash Table: Fill a table and watch it collide
Slot 1 is empty, so 12 goes here.
What you will see
KEY -> HASH -> SLOT. When the slot is taken, the key walks forward to the next free one.
Cost
| insert | O(1) expected |
|---|---|
| search | O(1) expected |
| delete | O(1) expected |
| worst case op | O(n) |
| Space | O(n) |
Expected bounds assume a good hash function and bounded load factor.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Hash Table covers these too, in the same run.