Design Your Own HashMap
Design and implement your own hashmap
We'll cover the following...
Statement
Design a hashmap without using built-in hash libraries. We only need to cater for integer keys and values in the hashmap. Return -1 if the key does not exist.
It should support the three primary functions of a hashmap:
put()get()remove()
Example
Consider the following hashmap example where the key-value pairs are mapped according to their respective hash keys with modulus base as 11:
Sample Input
put(1, 1)
get(1)
get(3)
Expected output
1
-1
Try it yourself
Note: You also have to implement the bucket class for your hashmap.
#include <iostream>#include <vector>#include <queue>#include "Bucket.cpp"#include <bits/stdc++.h>using namespace std;class MyHashMap {public:int key_space;vector<Bucket> bucket_list;MyHashMap(int new_key_space) {//Write - Your - Code}void Put(int key, int value) {//Write - Your - Code}int Get(int key) {//Write - Your - Codereturn -1;}void Remove(int key) {//Write - Your - Code}};
Solution
In this solution, we’ll use the modulus approach, where a modulo operator is used as a hash function with a custom modulus base defined during the initialization of the hashmap.
We use large prime numbers in our test cases to minimize instances of collision.
If there is a collision where two or more different keys are mapped to the same hash key, we use a bucket data structure to store their corresponding values. We can either use an array or a linked list to implement our bucket.
For any hashmap method, it’s important to first locate the corresponding value of the given key. This search operation can be done in two steps:
-
First, we apply the hash function to the given key-value pair to generate a hash key. Using this hash key, we find the bucket where the desired value is or is to be stored.
-
After this, we iterate across the bucket to find the place where the value should be and perform the required process - retrieval, insertion, or ...