Implement a Hash Map with Separate Chaining and Resizing
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a hash map data structure from scratch, without using any built-in hash table types from your language's standard library (no `dict`, `HashMap`, `unordered_map`, `Map`, `set`, etc.). Plain arrays/lists and your own linked-list nodes are allowed.
Your hash map must support two operations:
- `put(key, value)` — insert the key-value pair. If the key already exists, update its value.
- `get(key)` — return the value associated with the key, or `-1` if the key is not present.
Design requirements:
1. **Collision handling.** Use a bucket array where each bucket holds a linked list (separate chaining). Multiple keys that hash to the same bucket must all be stored and retrievable correctly.
2. **Dynamic resizing.** Track the load factor (number of stored entries divided by the number of buckets). When an insertion pushes the load factor above `0.75`, grow the bucket array (e.g., double its size) and rehash every existing entry into the new array, so that operations remain average-case $O(1)$.
You are given a sequence of operations to process. For every `get` operation, output the returned value.
**Example**
```
put(1, 10)
put(2, 20)
get(1) -> 10
get(3) -> -1
put(2, 30) (update: key 2 now maps to 30)
get(2) -> 30
```
**Constraints**
- $1 \le$ number of operations $\le 10^5$
- $0 \le key, value \le 10^9$
- `get` and `put` must run in average-case $O(1)$ time; a full rehash may take $O(n)$ but must be amortized across insertions.
- Do not use any built-in hash table / dictionary / map / set container anywhere in your implementation.
Quick Answer: This question evaluates understanding of hash table fundamentals, including hashing, separate chaining collision resolution, linked-list bucket management, dynamic resizing, and rehashing to maintain load factor and amortized performance.
Implement a hash map **from scratch** (no built-in `dict`/`HashMap`/`unordered_map`/`Map`/`set`). Use a bucket array with **separate chaining** (each bucket is a linked list) for collisions, and **dynamic resizing**: when an insert pushes the load factor above `0.75`, double the bucket array and rehash every entry so operations stay average-case O(1).
Support two operations:
- `put(key, value)` — insert the pair; if the key exists, update its value.
- `get(key)` — return the value for `key`, or `-1` if absent.
**Driver / I-O format.** You are given `operations`, a list where each element is a triple `[type, key, value]`:
- `type == 1` means `put(key, value)`.
- `type == 2` means `get(key)` (the third field is unused; pass `0`).
Return a list containing the result of **every `get`**, in the order they occur.
**Example**
```
put(1, 10)
put(2, 20)
get(1) -> 10
get(3) -> -1
put(2, 30) # update: key 2 now maps to 30
get(2) -> 30
```
Encoded as `operations = [[1,1,10],[1,2,20],[2,1,0],[2,3,0],[1,2,30],[2,2,0]]`, the answer is `[10, -1, 30]`.
Constraints
- 1 <= number of operations <= 10^5
- 0 <= key, value <= 10^9
- operations[i] = [type, key, value] with type in {1 (put), 2 (get)}
- get and put must run in average-case O(1) time (amortized rehash)
- Do NOT use any built-in hash table / dictionary / map / set container anywhere
Examples
Input: [[1,1,10],[1,2,20],[2,1,0],[2,3,0],[1,2,30],[2,2,0]]
Expected Output: [10, -1, 30]
Explanation: put(1,10), put(2,20). get(1)->10. get(3)->-1 (absent). put(2,30) updates key 2. get(2)->30.
Input: [[1,5,1],[1,5,2],[1,5,3],[2,5,0]]
Expected Output: [3]
Explanation: Repeated puts on the same key overwrite the value; the final get(5) returns the latest value 3.
Hints
- Keep a bucket array of linked-list heads. For a key, its bucket index is hash(key) % capacity; a good simple hash is (key * 2654435761) % capacity.
- On put, walk the bucket's chain first: if the key is already there, overwrite its value; otherwise prepend a new node and increment the size counter.
- Track load factor = size / capacity. When an insert makes it exceed 0.75, allocate a new array of double the capacity and rehash every existing node into it (indices change because capacity changed).
- get walks the chain of the key's bucket and returns the matching value, or -1 if it reaches the end. Remember a stored value of 0 is different from 'not found' (-1).