Practice/Meta/Leetcode 706. Design HashMap

Leetcode 706. Design HashMap

CodingMust

Problem

Design and implement a hash table data structure from scratch that supports storing integer key-value pairs. Your implementation should provide three core operations: inserting or updating a key-value pair, retrieving the value associated with a key, and removing a key-value pair.

You must not use any built-in hash map or dictionary data structures. Instead, you need to implement the underlying data structure yourself, including a hash function and a collision resolution strategy.

Your hash table should efficiently handle the expected workload while managing potential hash collisions that occur when different keys map to the same bucket.

Requirements

1. Implement a CustomHashTable class with the following methods:

   • put(key, value): Insert a key-value pair into the hash table. If the key already exists, update its value.
   • get(key): Return the value associated with the key. If the key doesn't exist, return -1.
   • remove(key): Remove the key-value pair from the hash table if it exists.

2. Do not use built-in hash table, dictionary, or map data structures (e.g., Python's dict, JavaScript's Map/Object for storage).

3. Implement your own hash function to convert keys to bucket indices.

4. Handle hash collisions using an appropriate collision resolution technique (chaining with linked lists or arrays is recommended).

Constraints

• 0 <= key, value <= 1000000
• At most 10000 calls will be made to put, get, and remove methods
• All keys and values are non-negative integers
• Target time complexity: O(1) average case for each operation
• Target space complexity: O(n) where n is the number of key-value pairs stored

Examples

Example 1:

` Operations: ["put", "put", "get", "get", "put", "get", "remove", "get"] Arguments: [[1, 10], [2, 20], [1], [3], [2, 25], [2], [2], [2]] Output: [null, null, 10, -1, null, 25, null, -1]

Explanation: CustomHashTable hashTable = new CustomHashTable(); hashTable.put(1, 10); // Store key 1 with value 10 hashTable.put(2, 20); // Store key 2 with value 20 hashTable.get(1); // Returns 10 hashTable.get(3); // Returns -1 (key doesn't exist) hashTable.put(2, 25); // Update key 2 to value 25 hashTable.get(2); // Returns 25 hashTable.remove(2); // Remove key 2 hashTable.get(2); // Returns -1 (key was removed) `

Example 2:

` Operations: ["put", "put", "get", "get"] Arguments: [[1, 100], [1001, 200], [1], [1001]] Output: [null, null, 100, 200]

Explanation: Keys 1 and 1001 might hash to the same bucket depending on the hash function. The hash table must properly handle this collision and retrieve both values correctly. `