โ Final Challenge
โบ A Growing Map
50 ptsA fixed bucket count betrays you at scale: chains grow with the data and
O(1) quietly rots into O(n). Real maps watch their load factor โ
len / nbuckets โ and when it crosses a threshold they allocate a bigger
bucket array and rehash: every entry's home bucket is hash % nbuckets, so changing nbuckets moves entries; each one must be relinked
into its new bucket. Existing nodes and key copies can be reused โ resizing
moves entries, it doesn't recreate them.
Assemble the complete map. hm_new, bucket_index, and chain_find are
given; implement the rest:
hm_putโ as in lesson 3, but before inserting a new key, iflen >= nbucketsdouble the bucket count. Overwrites never trigger a resize.hm_getโ hash, index, walk.hm_resize(m, nbuckets)โ allocate the new bucket array, relink every existing node by its new index, free the old array. 0 on success, -1 on allocation failure (in which case the map must be left untouched and usable).
The tests push 100 keys through a map that starts with 4 buckets, so a missing or wrong rehash shows up immediately as lost keys.
Log in to submit a solution and earn points.