Hash maps
Not met yet
A hash map, which is what Python's dict and set are, keeps a row of piles. A key goes in the pile its hash picks, as a pair with its value, and a lookup goes straight to that pile and compares keys along it. Each comparison is a probe. While piles stay short, a lookup is a probe or two however many keys there are: O(1) on average. When the keys outnumber three-quarters of the piles, the piles double and every key is moved to its new pile, because its pile number has changed.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks looking a key up in a dictionary compares it with every key stored, as in on a list does.
- Thinks a second key landing in an occupied pile replaces the first one, rather than joining it in the pile.
- Thinks that after a hash map doubles its piles, the keys can stay in the piles they were in.