AlgoScope

Hash Map

A hash table storing key-value pairs. The key picks the bucket and the value travels with it.

Data structures, data structure, intermediateAlso called dictionary, associative array
put 12: bucket 2.01234
put 12: bucket 2.01234

Hash Map: Filling buckets, with collisions

Decision, step 2 of 12

put 12 5: hash the key. 12 mod 5 = 2, so bucket 2 is the only place this key can be. It is empty.

Cost

Put
O(1) expected
Get
O(1) expected
Remove
O(1) expected
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Hash Map covers these too, in the same run.