706. Design HashMap - Detailed Explanation

Problem Statement

Design a HashMap without using any built-in hash table libraries. You need to implement the MyHashMap class with the following functionalities:

• MyHashMap(): Initializes the object with an empty map.

• void put(int key, int value): Inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.

• int get(int key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

• void remove(int key): Removes the key and its corresponding value if the map contains the mapping for the key.

Example

Input:

["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output:

[null, null, null, 1, -1, null, 1, null, -1]

Explanation:

MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1);       // The map is now [[1,1]]
myHashMap.put(2, 2);       // The map is now [[1,1], [2,2]]
myHashMap.get(1);          // returns 1
myHashMap.get(3);          // returns -1 (not found)
myHashMap.put(2, 1);       // update the existing value: The map becomes [[1,1], [2,1]]
myHashMap.get(2);          // returns 1
myHashMap.remove(2);       // remove the mapping for 2: The map is now [[1,1]]
myHashMap.get(2);          // returns -1 (not found)

Hints

1. Hash Function and Buckets:
   Use a simple hash function such as key % size to map keys to buckets. Each bucket can be implemented as a list (or linked list) to handle collisions via separate chaining.

2. Collision Handling:
   When two keys hash to the same index, store both entries in the same bucket. You need to check the bucket for an existing key when performing put, get, or remove operations.

Approach: Using Separate Chaining

Explanation

We can design our HashMap by maintaining an array (or list) of buckets. Each bucket is a list that will store key-value pairs. The main operations are implemented as follows:

• put(key, value):
  1. Compute the bucket index using the hash function (e.g., index = key % size).
  2. Iterate through the bucket:
     • If the key already exists, update its value.
     • If the key does not exist, append the new (key, value) pair.
• get(key):
  1. Compute the bucket index.
  2. Search through the bucket for the key.
  3. Return the corresponding value if found; otherwise, return -1.
• remove(key):
  1. Compute the bucket index.
  2. Find and remove the key-value pair from the bucket if it exists.

Step-by-Step Walkthrough

Consider performing the following operations:

1. Initialization:
   Create an array of fixed size (e.g., 1000 buckets). Each bucket is initially empty.

2. put(1, 1):

   • Hash key 1 using 1 % 1000 = 1.
   • Bucket at index 1 is empty; add (1, 1).

3. put(2, 2):

   • Hash key 2 using 2 % 1000 = 2.
   • Bucket at index 2 is empty; add (2, 2).

4. get(1):

   • Hash key 1; check bucket index 1.
   • Find (1, 1) and return 1.

5. put(2, 1):

   • Hash key 2; check bucket index 2.
   • Update the value for key 2 to 1.

6. remove(2):

   • Hash key 2; check bucket index 2.
   • Remove the key-value pair (2, 1).

Python Code