algoadvance

Design a HashMap without using any built-in hash table libraries. Implement the following operations:

• put(key: int, value: int) -> None: Insert a (key, value) pair into the HashMap. If the key already exists, update the corresponding value.
• get(key: int) -> int: Return the value to which the specified key is mapped, or -1 if the HashMap contains no mapping for the key.
• remove(key: int) -> None: Remove the mapping for the specified key if it exists.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);         
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);         // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);         // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found) 

Constraints:

• All keys and values will be in the range of [0, 10^6].
• The number of operations will be in the range of [1, 10^4].

Clarifying Questions

1. Can I assume that all keys and values are non-negative integers?
2. Is there any particular constraint on the size of the underlying data structure?

Strategy

1. Data Structure:
   • Use a fixed-size array (bucket array) as the primary container to store the key-value pairs.
   • Each bucket will itself be a list to handle collisions using chaining.
2. Hash Function:
   • Use a simple modulo operation to assign keys to buckets.
3. Operations:
   • Put: Compute the hash index of the key, then iterate through the list in that bucket to check if the key exists. If it does, update the value. If not, append a new (key, value) pair.
   • Get: Compute the hash index of the key, then iterate through the list in that bucket to find the key. Return the value if found, otherwise return -1.
   • Remove: Compute the hash index of the key, then iterate through the list in that bucket to find the key. Remove the key-value pair if found.

Code

class MyHashMap:

    def __init__(self):
        # Define the number of buckets
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        hash_key = self._hash(key)
        for idx, (k, v) in enumerate(self.buckets[hash_key]):
            if k == key:
                self.buckets[hash_key][idx] = (key, value)
                return
        self.buckets[hash_key].append((key, value))

    def get(self, key: int) -> int:
        hash_key = self._hash(key)
        for k, v in self.buckets[hash_key]:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        hash_key = self._hash(key)
        bucket = self.buckets[hash_key]
        for idx, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[idx]
                return

Time Complexity

• Put: O(N/B) on average, where N is the number of keys inserted and B is the number of buckets. In the worst case, it could be O(N) if all keys hash to the same bucket.
• Get: O(N/B) on average. In the worst case, it could be O(N).
• Remove: O(N/B) on average. In the worst case, it could be O(N).

This design leverages an array of linked lists (or vectors) and provides average constant-time complexity for basic operations, assuming a good hash function and a large enough array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?