โ˜… Final Challenge

โ€บ A Growing Map

50 pts

A 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.

before (nbuckets = 4)after (nbuckets = 8)buckets0123buckets01234567 double + rehashhash % new nbuckets
before (nbuckets = 4)after (nbuckets = 8)buckets0123buckets01234567 double + rehashhash % new nbuckets

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, if len >= nbuckets double 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.