Collisions

Here's how Python does handles collisions:

If you don't find what you are looking for, continue with a linear search.

• If you reach an empty slot, the search is over

Worst-case lookup time is also O(n)

• But again, this rarely occurs when the table is not too full

• If the table is ½ full, you expect to have to look at only 2 or 3 buckets before giving up

When the table starts to get too full, Python rebuilds it similarly to Perl