Implement a hashmap and set

Problem Implement a hashmap and a hash set from scratch: put/get/remove (map) and add/contains/remove (set), with collision handling and complexity analysis.

Requirements

• Map API: put(k, v) (upsert), get(k), remove(k); Set API: add/contains/remove; both handle collisions correctly and resize as they fill.

Core design

• Bucket array of size M; index = hash(key) mod M (mask with power-of-two M). Collisions via SEPARATE CHAINING: each bucket a linked list (or BST past a threshold, à la Java 8) of entries — walk the chain comparing keys with equals. Alternative to discuss: open addressing (linear probing) with tombstones on delete.
• Resize at load factor ~0.75: allocate 2M, REHASH every entry (indices change — copying buckets is wrong); amortized O(1).
• Set = map with dummy values (say it explicitly), or a thinner entry type.

Discussion points

• Complexities: O(1) average, O(n) worst per op (all keys one bucket — adversarial hashing); chaining vs open addressing trade-offs (cache locality vs memory per entry, deletion complexity).
• hashCode/equals contract as correctness precondition; mutating a key after insert breaks retrieval.
• Load factor tuning, why capacities are powers of two (cheap masking) vs primes (mitigating bad hashes), and treeified buckets as DoS defense.