AlgoScope

Hash Table

Turns a key into a slot number so lookup does not have to search.

Data structures, data structure, intermediate
Insert key 12. The hash of 12 is 1, so slot 1 is where the search starts.012345678910probe

Hash Table: Fill a table and watch it collide

Step, step 3 of 32

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.

Leads to

Topics that need this one first.

Taught by the same lesson

Hash Table covers these too, in the same run.