How to Build Your Own Hashmap in Javascript? | A Beginners Guide

By Prajwal Haniya

Tech-letter #17 | April 3, 2023

Hashmap

Now, let’s implement a hashmap


class Hashmap() {
    constructor() {
        this.hashmap = {};
    }

    set(key, value) {
        this.hashmap[key] = value;
    }

    get(key) {
        return this.hashmap[key];
    }

    contains(key) {
        return this.hashmap.hasOwnProperty(key);
    }

    clear() {
        this.hashmap = {};
    }
}

The above code is a simple implementation of a hashmap in javascript. It is simple because the keys are not hashed using a hash function. You can also create a hashmap using inbuilt Map() function. The following code shows how to implement a hashmap using Map()

const myMap = new Map();

myMap.set('key1', 'value1');

const value1 = myMap.get('key1'); 

const hasKey1 = myMap.has('key1'); // true
const hasKey2 = myMap.has('key3'); // false

console.log(myMap);

What are collisions? How to avoide it?

Now, we will implement a hashmap which is basically collision free. A collision-free hash map is also known as a perfect hash map.

class PerfectHashMap {
    constructor(keys, values) {
        this.size = keys.length;
        this.array = new Array(this.size).fill(null);
        
        const hashValues = keys.map(key => this.hash(key));
        const collisions = this.findCollisions(hashvalues);

        if (collisions === 0) {
            hashValues.forEach((hashValue, index) => {
                this.array[hashValue] = values[index];
            });
        } else {
            collisions.forEach((collision, index) => {
                const subkeys = keys.filter((key, i) => collision.includes(hashValues[i]));
                const subValues = values.filter((value, i) => collision.includes(hashValues[i]));
                this.array[collision[0]] = new PerfectHashMap(subKeys, subValues);
            });
        }
    }

}

Explanation:

Hope this much is clear. There is no complexity till now. The complexity occurs when you get a collision. So what to do when you have a collision. The code in the else block does the work when you encounter with collisions.

    collisions.forEach((collision, index) => {
        const subkeys = keys.filter((key, i) => collision.includes(hashValues[i]));
        const subValues = values.filter((value, i) => collision.includes(hashValues[i]));
        this.array[collision[0]] = new PerfectHashMap(subKeys, subValues);
    });

Let’s continue implementing a perfect hashmap.


class PerfectHashMap {
    constructor(keys, values) {
        // all the code mentioned above
    }

    hash (key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % this.size;
    }
}

Steps:

1. The hash code hash is initialized to 0.
2. The loop iterates over each character in the key string, one at a time.
3. For each character, the Unicode value of that character is added to the hash code.
4. After all characters have been processed, the hash code is returned modulo the size of the hash table.  This ensures that the hash code falls within the range of valid indices for the hash table.

For example, let’s say we have a hash table with a size of 10 and we want to hash the key “apple”. Here’s how the hash function works with each iteration of the loop:

// size of hash table is 10

hash("apple") 

// 1
i = 0
hash = 0 + 97 = 97

// 2
i = 1
hash = 97 + 112 = 209

// 3
i = 2
hash = 209 + 112 = 321

// 4
i = 3
hash = 321 + 108 = 429

// 5
i = 4
hash = 429 + 101 = 530

// Return the hash code modulo the size of the hash table
hash % 10 = 0
// Output: 1

Understanding the findCollisions method

class PerfectHashMap {
    constructor(keys, values) {
        // contructor
    }

    hash(key) {
        // hash method 
    }

    findCollisions(hashValues) {
        const collisions = [];
        hashValues.forEach((hashValue, index) => {
            const otherIndices = hashValues.filter((value, i) => i !== index);
            const collision = otherIndices.findIndex(value => value === hashValue);
            if (collision >= 0) {
                collisions.push([index, collision + 1]);
            }
        });
        return collisions;
    }
}

Now let’s write other methods that is set and get methods to complete the perfect hash map:

    class PerfectHashMap {
        constructor(keys, values) {
            // constructor
        }

        hash(key) {
            // hash
        }

        findCollisions(hashValues) {
            // findCollisions
        }

        get(key) {
            const hashValue = this.hash(key);
            const value = this.array[hashValue];
            if (value instanceof PerfectHashMap) {
                return value.get(key);
            }
            return value;
        }

        set(key, value) {
            const hashValue = this.hash(key);
            const currentValue = this.array[hashValue];
            if (currentValue instanceof PerfectHashMap) {
                currentValue.set(key, value);
            } else {
                this.array[hashValue] = value;
            }
        }
    }

Building an application using Hashmap

Let’s build a simple function which counts the vowels and return the highest vowel used based on it’s count.

    function countVowels(sentence) {
        const vowels = 'aeiou';
        const vMap = new Map();

        let highestCount = 0;
        let highestVowel = '';

        for (let char of sentence) {
            char = char.toLowerCase()
            if (vowels.includes(char)) {
                const count = vMap.get(char) || 0;
                const newCount = count + 1;
                vMap.set(char, newCount);

                if (newCount > highestCount) {
                    highestCount = newCount;
                    highestVowel = char;
                }
            }
        }

        return { highestVowel, highestCount};
    }

    const sentence = 'This is a sentence used to test the above function';
    const result = countVowels(sentence);
    console.log(result); // { highestVowel: 'e', highestCount: 7 }