Hash Map

Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.

Build a map that stores a value for each whole-number key. A hash picks a starting slot for a key. If two keys want the same starting slot, move the second one forward to the next open slot, one slot at a time, until you find it or find an empty one. Implement New(), Put(k, v) -> (old, existed), Get(k) -> (v, ok), Delete(k) -> ok, and Len() -> int using your language's names. Build the table yourself over a flat array of slots. Do not use your language's own map, dict, or set to store the data. Keys and values are whole numbers, including 0 and negative numbers. Your map receives one call at a time. For help with the ideas, read the notes.

Where it is used

• Python's dict keeps its entries in a flat table. When a key's slot is taken, it tries other slots (this is called open addressing), like you will here.
• Go's built-in map, since Go 1.24, is a Swiss Table, another open addressing table over flat arrays.
• Redis keeps its data in its own hash tables, which move keys to a bigger table a few at a time, so growing the table is spread over many small steps instead of one big copy.

When you delete a key, Python leaves a "dummy" marker in the slot instead of making it empty. An empty slot would cut the search short and lose the keys stored after it.

Stages

hm1: Store and read a value (very easy)

Store a value with Put, then return it with Get. Report missing for a key you never stored. Example: Put(1, 10) -> (0, false) (a brand new key). Get(1) -> (10, true). Get(2) -> (0, false) (never stored).

The tester will verify: Get returns the value you stored and reports that it found the key, and reports missing for a key that was never stored.

hm2: Update a key in place (easy)

Put on a key that already exists must replace its value, not add a second entry. Len counts the number of different keys you have stored, not the number of times you called Put. Example: Put(2, 20) -> (0, false). Put(2, 21) -> (20, true). Get(2) -> (21, true). Len() -> 1.

The tester will verify: updating a key returns its old value and reports that it existed, Get returns the new value, and Len still counts it once.

hm3: Delete a key without losing others (medium)

When you delete a key, don't just empty its slot. A search for a different key might need to pass through that slot to reach a key stored further along, and an empty slot would stop the search too early. Leave a small marker there instead, so a search knows to keep going.

slots:  [ A ][ B ][   ]      A and B both want slot 0. B sits in slot 1 instead.
delete A:
slots:  [ X ][ B ][   ]      X = a marker left behind. A search for B still checks slot 1.

Len must count only keys that are still there. A marker left by a delete is not one of them. Example: store A and B so they want the same starting slot, with B one slot after A. Delete A. Get(B) must still return its value. Len() must not count the deleted slot.

The tester will verify: deleting a key never hides a different key stored further along, and Len only counts keys that are still there.

hm4: Grow without losing keys (medium)

Start small and double the table when it gets full. When you grow, add every key that is still there into the bigger table again the same way you did the first time: use its hash and find it an open slot. Don't just copy each old slot to the same position in the new table. The new table is a different size, so a key's hash often points to a different slot now.

old table (4 slots):  [ A ][   ][ B ][   ]
new table (8 slots):  [   ][   ][ A ][   ][   ][   ][ B ][   ]   A and B land in new slots, not their old spots.

A marker left by a delete must not come back as a stored key just because its old slot got copied forward. Example: fill a small table until it must grow, then read back every key you stored before the growth. Every one must still return its value.

The tester will verify: after the table grows, every key you stored earlier still returns its value, and no deleted key comes back as found.

hm5: Stay correct under heavy use (hard)

Keep every answer correct over many calls: thousands of puts, deletes, and updates, with keys spanning the full range of a 32-bit whole number, including 0 and negative numbers. At this point many keys share the same slots, so a mistake in delete or growth that a small test would miss shows up here. Example: fill the table with thousands of keys, delete half of them, then check that the deleted keys report missing and the rest still return their values.

The tester will verify: every answer across the whole run is correct, including for 0 and negative keys.

hm6: Make it fast (L2, hard)

Keep Put, Get, and Delete fast even as the table fills up with real use. Keep every answer correct. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct.

Rules

• Build the table yourself over a flat array of slots. No built-in map, dict, set, or hash table for the storage (for example Python dict/set, JavaScript Map/Set, Ruby Hash, Go map, Rust HashMap). Write your own hash (starting with the key itself is fine), your own way to find an open slot, your own delete, and your own growth.
• Start small, for example 8 to 16 slots, and double the table when it gets full.
• Keep enough empty space so searches stay short as the table fills up. Count deleted markers too when you decide the table is getting full, not just stored keys.
• Keep answers correct for 0 and negative keys. Check how your language's % operator handles negative numbers.
• Standard library only.

Read the Hash Map notes in the wiki