Implement a hash table with put/get

Problem

Implement a simplified hash table (hash map) data structure from scratch.

Required API

Design a class HashTable with:

• HashTable(int numBuckets) (constructor): initialize internal storage with a fixed number of buckets.
• void put(K key, V value): insert a key/value pair. If the key already exists, overwrite its value.
• V get(K key): return the value for key, or a sentinel (e.g., null / -1) if the key is not present.

Note: delete/remove is not required.

Assumptions / Constraints

• You may assume keys are non-null.
• You must handle hash collisions correctly.
• Target average time complexity: O(1) for put and get (amortized/expected).
• You may not use a built-in hash map/dictionary.

Follow-up discussion (conceptual)

1. What makes a hash function “good,” and how does key distribution affect performance?
2. How does the choice of numBuckets (and the load factor) impact collisions and runtime?
3. Compare common collision-resolution strategies:
   • Separate chaining (buckets)
   • Open addressing (e.g., linear/quadratic probing, double hashing)
4. If using open addressing, describe how probing (“hopping”) works and what pitfalls it introduces (e.g., clustering, tombstones).

Hash Table Put Get Simulator

Implement fixed-bucket separate chaining for put/get operations without using a built-in dictionary for storage. Return get outputs.

Examples

Example 1

Input: (2, [["put","a",1],["put","b",2],["get","a"],["get","c"]])
Output: [1, None]

Explanation: Put and get values with missing returning None.

Example 2

Input: (1, [["put","a",1],["put","b",2],["get","a"],["get","b"],["put","a",3],["get","a"]])
Output: [1, 2, 3]

Explanation: A single bucket forces collision handling and update.

Hints

1. Use a list for each bucket.
2. Scan a bucket to update or find a key.