In computing Hash Table or Hash Maps are amazing. For me, it's the 9th wonder of the world. Compounding is still the 8th one 😄

So let's understand what is hashing.

Hashing

Hashing is the process of converting a given key into another value. A hash function is used to generate the new value according to a mathematical algorithm. The result of a hash function is known as a hash value or simply, a hash.

There are many theories behind hashing like one-way hashing, two-way hashing, collisions, etc. but let's not dive too deep. That's for another day.

Any programming language has rich sets of APIs(not the REST API mind you 😁).

We usually have Lists, Maps, Sets etc. One such is a Hash Map and Hash Table.

Both of them are used to save and retrieve data.

The time complexities are as follows:

• Search : O(1) 🔍
• Insert : O(1) ✔
• Delete : O(1) ❌

You can see why I am calling it the 9th Wonder. O(1) is the favorite of any programmer!

Okay, now let's focus on the problem at hand.

The Problem

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

• `put(key, value)` : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
• `get(key)`: Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• `remove(key)` : Remove the mapping for the value key if this map contains the mapping for the key.

Note:

• All keys and values will be in the range of `[0, 1000000]`.
• The number of operations will be in the range of `[1, 10000]`.
• Do not use the built-in HashMap library.

Here we cannot use any in-built libraries and so this makes it a bit difficult. But the notes above will give us some hints. So the key and values are in a confined range.

Let's see a JAVA implementation of the problem:

``````class MyOwnHashMap {

private int[] values;

/**
* Initialize the data structure here.
*/
public MyHashMap() {
this.values = new int[1000001];
}

/**
* Value will always be non-negative.
*/
public void put(int key, int value) {
this.values[key] = value + 1;
}

/**
* Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
*/
public int get(int key) {
return this.values[key] - 1;

}

/**
* Removes the mapping of the specified value key if this map contains a mapping for the key
*/
public void remove(int key) {
this.values[key] = 0;
}
}``````

So what did I do?

I used a simple int array with a predefined length of 1000001.

By default, all values are 0 in Java. So we keep it the way it is and do not flash fill to -1 which can be another way.

While inserting the values we increment the value to plus 1 and while returning we decrease it to -1.

This helps us to tackle the boundary case that if the key is not present, return -1.

Let's go through an example:

put(1, 5) -> This will insert 6 at index 1 as we are adding 1 to it while inserting.

So array becomes: values [0, 6, .... ]

get(1) -> This will return the value at index 1 and decrease 1 from it.

So we return values[1]: 6 - 1 which is 5. This is equal to what we tried inserting earlier.

remove(1) -> This will make the value at location 1 to 0.

So array becomes: values [0, 0, .... ]

Now if we do a get(1), it returns values[1] : 0 - 1 which is -1.

Thus this satisfies the boundary condition.

Hope you like this. Cheers!