3 min read algorithm

Designing your own Hash Map with Positive Numbers!

Designing your own Hash Map with Positive Numbers!

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!

Tirthankar Kundu