Design HashMap

Problem Implement a HashMap without built-in hash tables: put(key, value), get(key), remove(key). Expect internal-workings probes — including why a large prime is used as the hash modulus.

Input / Output

• Operations on integer (or generic) keys; get returns -1/absent for missing keys.

Constraints

• Ops up to 10^4; O(1) average per operation expected; collisions must be handled, not assumed away.

Example

• put(1, 10), put(1, 20) → get(1) = 20 (upsert); remove(1) → get(1) = -1.

Expected approach

• Bucket array + separate chaining: index = hash(key) mod M; each bucket a linked list of (key, value) nodes — put walks the chain to upsert, get/remove likewise. Resize (double + rehash all entries) past load factor ~0.75 for amortized O(1). Probing questions to be ready for: WHY a prime modulus — when keys share factors with M (patterned inputs, e.g. all even keys with even M), composite M concentrates them in a subset of buckets; a prime modulus spreads residues uniformly regardless of input stride. Also: chaining vs open addressing, equals/hashCode contract, worst case O(n) chains and treeification as the defense.