Building a HashMap
You'll learn to
- -Implement put, get, delete, and contains using separate chaining
- -Explain load factor and why real hashmaps resize as they fill up
- -Reason about the amortized average-case O(1) cost of hashmap operations
This chapter assembles the last chapter's pieces into a complete, working HashMap: a fixed array of buckets, the hash-and-modulo step to choose one, and a short linear scan within that one bucket to handle whatever collisions land there.
The Bucket Array
put, get, delete, and contains
Every one of put, get, delete, and contains follows the same two-step shape: hash the key once to find the right bucket (O(1)), then scan only that one bucket rather than the whole table. As long as buckets stay short, that scan stays close to free, which is why the overall operation is described as average-case O(1) - not because there is zero scanning, but because the scan only ever touches a tiny slice of the data.
Load Factor & Resizing
Load factor is the number of stored entries divided by the number of buckets - effectively the average chain length. As it climbs past roughly 0.7 to 0.75, buckets routinely start holding multiple entries, and the per-bucket scan stops being negligible. Real hashmaps, including Python's own dict, monitor load factor and, once it crosses a threshold, allocate a larger bucket array (commonly double the previous size) and rehash every existing key into it. That rehashing pass is O(n), but it happens only occasionally - amortized across all the puts that led up to it, it barely dents the average-case O(1).
Python's real dict implementation is far more optimized than this - open addressing rather than chaining, plus guaranteed insertion-order preservation since Python 3.7 - but the average-case O(1), resize-on-load-factor idea built here is the same mental model underneath every hashmap you will ever reach for.
In separate chaining, what does each bucket in the underlying array hold?
Level 4: HashMap from Scratch asks you to implement exactly this - a HashMap class with put, get, delete, contains, size, and load_factor, using separate chaining for collision resolution. Build it directly from the class above.