A hash index answers "find every row where column = X" in O(1) average time instead of scanning the whole table. Every key hashes to one of a fixed number of buckets; when two DIFFERENT keys happen to hash to the same bucket (a collision), they just both get appended to that bucket's list ("separate chaining") rather than overwriting each other.

_bucket_for (given) uses key % num_buckets as a simple, deterministic hash function (this exercise uses integer keys specifically so bucket assignment is reproducible). Implement:

• insert(key, row_id): add (key, row_id) to the bucket _bucket_for(key) picks. Multiple row_ids can share the same key (a non-unique index) -- both must remain findable later. After inserting, if the load factor (size / num_buckets) now exceeds MAX_LOAD_FACTOR, call self._grow().
• lookup(key): return the list of ALL row_ids ever inserted under key, in insertion order (empty list if never inserted). Only the ONE bucket _bucket_for(key) points to needs to be searched -- but that bucket may contain entries for OTHER keys too (collisions), so filter by key within it.
• delete(key, row_id): remove exactly that ONE (key, row_id) pair -- other row_ids under the same key are untouched. No-op if the exact pair isn't present.
• _grow(): double num_buckets, then re-insert every existing (key, row_id) pair into fresh buckets.

The missing link: a hash index that never grows silently rots

insert/lookup/delete alone are correct but incomplete -- a fixed num_buckets means the average chain length grows without bound as more rows are inserted, and "O(1) average lookup" quietly degrades toward O(n) (a linear scan of one very long chain) the more data you add. _grow is what keeps the average chain length bounded. It's also the one place a working-looking implementation can still be subtly wrong: _bucket_for computes key % self.num_buckets, so the instant num_buckets changes, EVERY existing entry's correct bucket changes too. Just replacing self.buckets with more empty buckets (without moving the old entries into them) leaves every previously-inserted row unfindable -- lookup would compute today's bucket index for a key that was placed according to yesterday's bucket count.

Example

idx = HashIndex(num_buckets=4)
idx.insert(1, "row-a")
idx.insert(5, "row-b")   # 5 % 4 == 1 % 4 -- same bucket as key 1, but a
                          # DIFFERENT key, so it must not interfere
idx.lookup(1)             # -> ["row-a"]
idx.lookup(5)             # -> ["row-b"]
idx.delete(1, "row-a")
idx.lookup(1)             # -> []

Constraints

• lookup must filter by the exact key within the bucket -- a bucket containing entries for multiple different keys (due to collisions) must never return another key's row_ids.
• delete removes one specific (key, row_id) pair, not every entry for that key.
• After any number of inserts (and any number of _grow calls they trigger), every previously-inserted, not-yet-deleted (key, row_id) pair must still be findable via lookup.

Real-world grounding

• Postgres's hash index access method: src/backend/access/hash/ -- see _hash_expandtable for the real version of this exercise's _grow: Postgres splits one bucket at a time rather than rehashing everything at once, to keep any single insert's worst-case latency bounded, but the underlying idea (more buckets means every key's bucket assignment must be recomputed) is identical.

Some real hash indexes use open addressing instead of chaining (probing for the next free slot instead of a linked list per bucket) -- but "hash the key, search only that bucket, handle collisions somehow, and grow before chains get too long" is the core idea underneath every hash index design.