Hash Table
Turns a key into a slot number so lookup does not have to search.
Hash Table: Fill a table and watch it collide
Insert 12. Its hash is 12 mod 11, which is slot 1.
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.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Hash Table covers these too, in the same run.