algoadvance

Leetcode 706. Design HashMap

Problem Statement

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

Clarifying Questions

  1. Range of keys and values: What are the possible ranges for keys and values?
    • Typically, we consider the range as 0 <= key, value <= 1,000,000 for this problem.
  2. Collision handling: How should we handle collisions?
    • We can use separate chaining (linked lists) to resolve collisions.
  3. Capacity and Space complexity: Do we need to handle dynamic resizing of the underlying storage?
    • For simplicity, a fixed size of the array (e.g., 10000) can be used, assuming it as reasonably large enough and not requiring dynamic resizing.

Strategy

  1. Hash Function: Use a simple modulo operation for the hash function: hash = key % capacity.
  2. Storing Collisions: Use linked lists to handle collisions. Each bucket (index of the array) will hold a linked list of key-value pairs.
  3. Operations:
    • put: Calculate the hash and store the key-value pair in the corresponding bucket, handling updates if the key already exists.
    • get: Calculate the hash and search the linked list in the corresponding bucket to find the value for the key.
    • remove: Calculate the hash and remove the key-value pair from the linked list in the corresponding bucket.

Code

#include <vector>
#include <list>
#include <utility>

class MyHashMap {
private:
    static const int capacity = 10000;  // Capacity of the HashMap
    std::vector<std::list<std::pair<int, int>>> data;

    int hash(int key) {
        return key % capacity;  // Simple hash function
    }
    
public:
    MyHashMap() : data(capacity) {}

    void put(int key, int value) {
        int hashedKey = hash(key);
        for (auto& [k, v] : data[hashedKey]) {
            if (k == key) {
                v = value;
                return;
            }
        }
        data[hashedKey].emplace_back(key, value);
    }
    
    int get(int key) {
        int hashedKey = hash(key);
        for (const auto& [k, v] : data[hashedKey]) {
            if (k == key) return v;
        }
        return -1;
    }
    
    void remove(int key) {
        int hashedKey = hash(key);
        auto& list = data[hashedKey];
        for (auto it = list.begin(); it != list.end(); ++it) {
            if (it->first == key) {
                list.erase(it);
                return;
            }
        }
    }
};

Time Complexity

  1. Initialization (MyHashMap()): O(1) - Initializing the vector with a fixed capacity.
  2. put(key, value): O(1) on average; O(n) in the worst-case scenario if all keys hash to the same bucket.
  3. get(key): O(1) on average; O(n) in the worst-case scenario.
  4. remove(key): O(1) on average; O(n) in the worst-case scenario.

Here, n refers to the number of key-value pairs in a single bucket (linked list), but typically due to the hash function, operations should be average O(1) if the keys are distributed uniformly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI