We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design HashMap

Difficulty: Easy

Problem Description

Design a HashMap without using any built-in hash table libraries. Implement the MyHashMap class with the following methods:

  • 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(key) removes the key and its corresponding value if the map contains the mapping for the key.

Key Insights

  • A hash map is a data structure that maps keys to values for efficient retrieval.
  • The key is transformed into an index using a hash function to determine where to store the value.
  • Collision resolution techniques (like chaining or open addressing) are necessary to handle cases where multiple keys hash to the same index.

Space and Time Complexity

Time Complexity:

  • Average case: O(1) for put, get, and remove operations.
  • Worst case: O(n) for all operations in case of many collisions.

Space Complexity:

  • O(n), where n is the number of key-value pairs in the HashMap.

Solution

To implement a HashMap, we can use an array of linked lists (or buckets) for collision resolution. Each index in the array corresponds to a hashed value of the key. When inserting a key-value pair, we compute the hash value of the key, and place the pair in the appropriate bucket. If a collision occurs (i.e., the bucket already contains a key), we update the value if the key exists or add a new entry if it does not. The get operation retrieves the value by hashing the key and searching the corresponding bucket, while the remove operation involves finding and deleting the entry from the bucket.

Code Solutions

class MyHashMap:
    def __init__(self):
        # Initialize the hashmap with a fixed size of buckets and empty lists
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key):
        # Hash function to determine the index for the key
        return key % self.size

    def put(self, key: int, value: int) -> None:
        index = self._hash(key)
        # Check if the key already exists and update the value
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)
                return
        # If key does not exist, append the new key-value pair
        self.buckets[index].append((key, value))

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

    def remove(self, key: int) -> None:
        index = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                del self.buckets[index][i]  # Remove the entry
                return
← Back to All Questions