AlgoScope

Hash Table Insert

Hash the key to a slot, then walk forward past anything already there.

Hashing, algorithm, intermediate
Insert key 45. The hash of 45 is 1, so slot 1 is where the search starts.0121232133445678910probe

Hash Table: Insert that walks past a collision

Step, step 2 of 8

Insert 45. Its hash is 45 mod 11, which is slot 1.

How hash table works

Cost

Best
O(1)
Average
O(1)
Worst
O(n)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Hash Table covers these too, in the same run.