Implement a Hash Map with Separate Chaining and Resizing

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.