Solution: Design HashMap

Let's solve the Design HashMap problem using the Hash Map pattern.

We'll cover the following

Statement

Design a HashMap data structure that supports the following operations:

  • Constructor(): Initializes the hash map object with an empty map to store the key-value pairs.

  • Put(key, value): Inserts a key-value pair into the hash map. If the specified key is already present in the hash map, the associated value is updated. Otherwise, the key-value pair is added to the hash map.

  • Get(key): Returns the value associated with the specified key if the key exists in the hash map. Otherwise, it returns −1-1, indicating the absence of a mapping for the key.

  • Remove(key): Removes the entry for the specified key from the hash map, effectively removing both the key and its associated value. This elimination only takes place when the key exists in the hash map.

Note: Your implementation should not utilize the built-in hash table libraries.

Constraints:

  • 00 ≤\le key ≤\le 10610^6
  • 00 ≤\le value ≤\le 10610^6
  • At most, 10410^4 calls can be made to the Put, Get, and Remove functions.

Solution

A hash map is a fundamental data structure found in various programming languages. Its key feature is facilitating fast access to a value associated with a given key. Designing an efficient hash map involves addressing two main challenges:

  1. Hash function design: The hash function serves to map a key to a location in the storage space. A good hash function ensures that keys are evenly distributed across the storage space, preventing the clustering of keys in certain locations. This even distribution helps maintain efficient access to stored values.

  2. Collision handling: Despite efforts to evenly distribute keys, collisions—where two distinct keys map to the same storage location—are inevitable due to the finite nature of the storage space compared to the potentially infinite key space. Effective collision-handling strategies are crucial to ensure data integrity and efficient retrieval. To deal with collisions, we can use methods like chaining, where we link multiple values together at that location, or open addressing, where we find another empty location for the key.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

The first step is to design a hash function using the modulo operator, particularly suitable for integer-type keys. The modulo operator, denoted by %\%, is a mathematical operation that returns the remainder of dividing one number by another. When selecting a modulo base, it’s advisable to choose a prime number. This is because choosing a prime number as the modulo base helps minimize collisions. Since prime numbers offer better distribution of hash codes, reducing the likelihood of collisions (where two different keys hash to the same value).

Here’s the implementation of a hash function using a prime number, 20692069, as the modulo base. This particular prime number is likely chosen because it is relatively large, offering a wide range of possible hash codes and reducing the chance of collisions.

class Solution {
    public static int calculateHash(int key) {
        int keyBase = 2069;
        return key % keyBase;
    }
    public static void main(String[] args) {
        int[] keys = {1, 2068, 2070};
        for (int i = 0; i < keys.length; i++) {
            int hashedValue = calculateHash(keys[i]);
            System.out.println((i + 1) + ".\tKey: " + keys[i]);
            System.out.println("\tHashed value: " + hashedValue);
        }
    }
}
Design hash function

In the code provided above, collisions occur because when taking the modulo of keys with the base value of 20692069, both keys 11 and 20702070 yield the same hash value of 11, leading to a collision.

Now, let’s look at a visual representation of hash collision:

Press + to interact

In the scenario illustrated in the diagram above, when two distinct keys are assigned to the same address, it results in a collision. Therefore, the second step is to handle collision by using a storage space where each element is indexed by the output of the hash function. To address this, we use a container, bucket, designed to store all values that are assigned the same hash value by the hash function.

Let’s look at the diagram below to visualize collision handling through the use of buckets:

Press + to interact

Now, let’s design a Bucket for collision handling supporting primary operations: Get, Update, and Remove. These operations allow for efficient management of key-value pairs within each bucket, accommodating cases where multiple keys hash to the same index.

  • Get(key): Searches the bucket for a key-value pair where the key matches the provided argument. If such a pair is found, the method returns the corresponding value. If the key does not exist within the bucket, the method returns −1-1. This functionality is crucial for retrieval operations in a hash table, allowing for efficient access to stored data based on keys.

  • Update(key, value): Looks for the specified key in the bucket. If the key is found, the method updates the existing key-value pair with the new value provided. If the key is not found, the method adds a new key-value pair to the bucket. This dual functionality ensures that the bucket can dynamically adjust to changes in data, either by updating existing entries or adding new ones to accommodate new keys.

  • Remove(key): Searches the bucket for a key-value pair matching the specified key. If such a pair is found, the method removes it from the bucket, effectively handling the deletion of entries.

Let’s look at the implementation of the Bucket discussed above:

import java.util.ArrayList;
class Bucket {
    private ArrayList<Pair<Integer, Integer>> bucket;
    public Bucket() {
        // Constructor to initialize an empty list to store key-value pairs
        bucket = new ArrayList<>();
    }
    // Method to get the value corresponding to the given key
    public int get(int key) {
        // Iterate through each key-value pair in the bucket
        for (Pair<Integer, Integer> kv : bucket) {
            // If the key matches the provided key, return the corresponding value
            if (kv.getKey() == key) {
                return kv.getValue();
            }
        }
        // If the key is not found, return -1
        return -1;
    }
    // Method to update the value for the given key
    public void update(int key, int value) {
        // Flag to indicate whether the key is found in the bucket
        boolean found = false;
        // Iterate through each key-value pair in the bucket
        for (int i = 0; i < bucket.size(); i++) {
            Pair<Integer, Integer> kv = bucket.get(i);
            // If the key matches the key of the current key-value pair
            if (key == kv.getKey()) {
                // Update the value of the key-value pair
                bucket.set(i, new Pair<>(key, value));
                // Set the flag to true, indicating that the key is found
                found = true;
                break;
            }
        }
        // If the key is not found in the bucket, add it along with its value
        if (!found) {
            bucket.add(new Pair<>(key, value));
        }
    }
    // Method to remove the key-value pair with the given key
    public void remove(int key) {
        // Iterate through each key-value pair in the bucket
        for (int i = 0; i < bucket.size(); i++) {
            Pair<Integer, Integer> kv = bucket.get(i);
            // If the key matches the key of the current key-value pair
            if (key == kv.getKey()) {
                // Delete the key-value pair from the bucket
                bucket.remove(i);
                // Exit the loop as the key has been removed
                break;
            }
        }
    }
}
// Define Pair class to store key-value pairs
class Pair<K, V> {
    private K key;
    private V value;
    // Constructor to initialize key-value pair
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    // Getter methods for key and value
    public K getKey() {
        return key;
    }
    public V getValue() {
        return value;
    }
}
class Solution {
    // Method to calculate hash value for a given key
    public static int calculateHash(int key) {
        int keyBase = 2069;
        return key % keyBase;
    }
    public static void main(String[] args) {
        // Create an array of Bucket objects
        Bucket[] buckets = new Bucket[2069];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new Bucket();
        }
        // Example usage:
        int[][] keyValuePair = {{1, 1000}, {2070, 2000}, {2068, 3000}};
        int i = 1;
        for (int[] pair : keyValuePair) {
            int key = pair[0];
            int value = pair[1];
            int hashKey = calculateHash(key);
            System.out.println(i + ".\tInserting key-value pair: Key = " + key + ", Value = " + value + ", HashKey = " + hashKey);
            buckets[hashKey].update(key, value);
            // Retrieving values
            System.out.println("\tRetrieving value for key " + key + ": " + buckets[hashKey].get(key) + "\n");
            i++;
        }
        // Removing a key
        int keyToRemove = keyValuePair[keyValuePair.length - 1][0];
        System.out.println(i + ".\tRemoving key " + keyToRemove);
        buckets[calculateHash(keyToRemove)].remove(keyToRemove);
        System.out.println("\tValue for key " + keyToRemove + " after removal: " + buckets[calculateHash(keyToRemove)].get(keyToRemove));  // Output: -1 (removed)
    }
}
Design bucket

In the code above, collision handling occurs implicitly within the Update function of the Bucket. It effectively handles collisions by allowing multiple key-value pairs with the same hash value (i.e., the same bucket index) to coexist within the bucket.

Moving forward, the third step involves designing a hash map by utilizing the hash function and the Bucket designed earlier.

To design a hash map, the core operation involves locating stored values by key. Therefore, for each hash map method—Get, Put, and Remove—the primary task revolves around locating stored values by key. This process involves two steps:

  1. Applying the hash function to generate a hash key for a given key value, determining the address in the main storage, and finding the corresponding bucket.
  2. Iterating through the bucket to check if the desired key-value pair exists.

Let’s look at the implementation of a hash map:

Main.java
Bucket.java
HashPrint.java
import java.util.*;
// Define DesignHashMap class to implement the HashMap functionality
class DesignHashMap {
    public int keySpace;
    public Bucket[] buckets;
    // Constructor to initialize the HashMap
    public DesignHashMap() {
        // Initialize the hash map with a prime number of key spaces to reduce collisions
        keySpace = 2069;
        // Create an array of buckets to store key-value pairs, using the initialized prime number
        buckets = new Bucket[keySpace];
        for (int i = 0; i < keySpace; i++) {
            buckets[i] = new Bucket();
        }
    }
    // Function to add a key-value pair to the hash map
    public void put(int key, int value) {
        // Calculate the hash key using modulo operation with the key space
        int hashKey = key % keySpace;
        // Update the bucket at the hashed key with the key-value pair
        buckets[hashKey].update(key, value);
    }
    // Function to retrieve the value associated with a given key from the hash map
    public int get(int key) {
        // Calculate the hash key using modulo operation with the key space
        int hashKey = key % keySpace;
        // Return the value associated with the key from the corresponding bucket
        return buckets[hashKey].get(key);
    }
    // Function to remove a key-value pair from the hash map given a key
    public void remove(int key) {
        // Calculate the hash key using modulo operation with the key space
        int hashKey = key % keySpace;
        // Remove the key-value pair from the corresponding bucket
        buckets[hashKey].remove(key);
    }
    // Main method to demonstrate the usage of the HashMap
    public static void main(String args[]) {
        
        DesignHashMap inputHashMap = new DesignHashMap();
        List<Integer> keys = Arrays.asList(5, 2069, 2070, 2073, 4138, 2068);
        List<Integer> keysList = new ArrayList<>(Arrays.asList(5, 2069, 2070, 2073, 4138, 2068));
        List<Integer> values = Arrays.asList(100, 200, 400, 500, 1000, 5000);
        List<String> funcs = Arrays.asList("Get", "Get", "Put", "Get", "Put", "Get", "Get", "Remove", "Get", "Get", "Remove", "Get");
        List<List<Integer>> funcKeys = Arrays.asList(
            Arrays.asList(5), 
            Arrays.asList(2073), 
            Arrays.asList(2073, 50), 
            Arrays.asList(2073), 
            Arrays.asList(121, 110), 
            Arrays.asList(121), 
            Arrays.asList(2068), 
            Arrays.asList(2069), 
            Arrays.asList(2069), 
            Arrays.asList(2071), 
            Arrays.asList(2071), 
            Arrays.asList(2071)
        );
        
        for (int i = 0; i < keys.size(); i++) {
            inputHashMap.put(keys.get(i), values.get(i));
        }
        
        for (int i = 0; i < funcs.size(); i++) {
            if (funcs.get(i) == "Put") {
                System.out.println(i + 1 + ".\t put(" + funcKeys.get(i).get(0) + ", " + funcKeys.get(i).get(1) + ")");
                if (!(keysList.contains(funcKeys.get(i).get(0)))) {
                    keysList.add(funcKeys.get(i).get(0));
                }
                inputHashMap.put(funcKeys.get(i).get(0), funcKeys.get(i).get(1));
            } else if (funcs.get(i) == "Get") {
                System.out.println(i + 1 + ".\t get(" + funcKeys.get(i).get(0) + ")");
                System.out.println("\t Value returned: " + inputHashMap.get(funcKeys.get(i).get(0)));
            } else if (funcs.get(i) == "Remove") {
                System.out.println(i + 1 + ". \t remove(" + funcKeys.get(i).get(0) + ")");
                inputHashMap.remove(funcKeys.get(i).get(0));
            }
            // Printing the hashmap using our custom print function
            System.out.println("\nHash map:\n");
            HashPrint.print(inputHashMap, keysList);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Design HashMap

The slides below illustrate how the designed hash map works:

Press + to interact
canvasAnimation-image
1 of 11

Just the code

Here’s the complete solution to this problem:

Main.java
Bucket.java
import java.util.*;
// Define DesignHashMap class to implement the HashMap functionality
class DesignHashMap {
    public int keySpace;
    public Bucket[] buckets;
    // Constructor to initialize the HashMap
    public DesignHashMap() {
        keySpace = 2069;
        buckets = new Bucket[keySpace];
        for (int i = 0; i < keySpace; i++) {
            buckets[i] = new Bucket();
        }
    }
    // Function to add a key-value pair to the hash map
    public void put(int key, int value) {
        int hashKey = key % keySpace;
        buckets[hashKey].update(key, value);
    }
    // Function to retrieve the value associated with a given key from the hash map
    public int get(int key) {
        int hashKey = key % keySpace;
        return buckets[hashKey].get(key);
    }
    // Function to remove a key-value pair from the hash map given a key
    public void remove(int key) {
        int hashKey = key % keySpace;
        buckets[hashKey].remove(key);
    }
    // Main method to demonstrate the usage of the HashMap
    public static void main(String args[]) {
        
        DesignHashMap inputHashMap = new DesignHashMap();
        List<Integer> keys = Arrays.asList(5, 2069, 2070, 2073, 4138, 2068);
        List<Integer> keysList = new ArrayList<>(Arrays.asList(5, 2069, 2070, 2073, 4138, 2068));
        List<Integer> values = Arrays.asList(100, 200, 400, 500, 1000, 5000);
        List<String> funcs = Arrays.asList("Get", "Get", "Put", "Get", "Put", "Get", "Get", "Remove", "Get", "Get", "Remove", "Get");
        List<List<Integer>> funcKeys = Arrays.asList(
            Arrays.asList(5), 
            Arrays.asList(2073), 
            Arrays.asList(2073, 50), 
            Arrays.asList(2073), 
            Arrays.asList(121, 110), 
            Arrays.asList(121), 
            Arrays.asList(2068), 
            Arrays.asList(2069), 
            Arrays.asList(2069), 
            Arrays.asList(2071), 
            Arrays.asList(2071), 
            Arrays.asList(2071)
        );
        
        for (int i = 0; i < keys.size(); i++) {
            inputHashMap.put(keys.get(i), values.get(i));
        }
        
        for (int i = 0; i < funcs.size(); i++) {
            if (funcs.get(i) == "Put") {
                System.out.println(i + 1 + ".\t put(" + funcKeys.get(i).get(0) + ", " + funcKeys.get(i).get(1) + ")");
                if (!(keysList.contains(funcKeys.get(i).get(0)))) {
                    keysList.add(funcKeys.get(i).get(0));
                }
                inputHashMap.put(funcKeys.get(i).get(0), funcKeys.get(i).get(1));
            } else if (funcs.get(i) == "Get") {
                System.out.println(i + 1 + ".\t get(" + funcKeys.get(i).get(0) + ")");
                System.out.println("\t Value returned: " + inputHashMap.get(funcKeys.get(i).get(0)));
            } else if (funcs.get(i) == "Remove") {
                System.out.println(i + 1 + ". \t remove(" + funcKeys.get(i).get(0) + ")");
                inputHashMap.remove(funcKeys.get(i).get(0));
            }
  
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Design HashMap

Solution summary

  1. Choose a prime number for the key space size (preferably a large one).

  2. Create an array and initialize it with empty buckets equal to the key space size.

  3. Generate a hash key by taking the modulus of the input key with the key space size.

  4. Implement the following functions:

    • Put(key, value): Inserts the value into the bucket at the computed hash key index

    • Get(key): Searches for the key in the bucket and returns the associated value

    • Remove(key): Deletes the element at the specified key from the bucket and the hash map

Time Complexity

Each method of the hash map has a time complexity of O(NK)O( \frac{N}{K}), where NN represents the total number of possible keys, and KK represents the key space size, which in our case is 20692069.

In an ideal scenario with evenly distributed keys, the average size of each bucket can be considered as NK\frac{N}{K}. However, in the worst-case scenario, we may need to iterate through an entire bucket to find the desired value, resulting in a time complexity of O(N)O(N) for each method.

Space Complexity

The space complexity is O(K+M)O(K+M), where KK denotes the key space size, and MM represents the number of unique keys that have been inserted into the hashmap.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.