Custom implementation of hashMap in javascript

Introduction

HashMap is a data structure which stores data in the form of key & value. Every key of hashMap is unique.

If you will compare - Javascript by default provides object Literal which acts as hashMap.

var obj = {
      name:'ujjwal gupta'
}

Also javascript provides Map & WeakMap to store value in form of key, value.

How about creating your custom implementation of HashMap ?

Generally this is not needed but its good for understanding how hashMap works. In this article i am going to explain how hashMap works along with custom implementation of hashMap.

Let’s Code

A hash map is nothing but array where array index act as keys. So if we can somehow convert a key to index then we can store the key, value pair in array.

Convert key into Index

Here a hashing function is used which converts any value to a number which will be used as index.

A simple hashing function is convert a value to sum of character ascii value.

getHash(value) {
    value = value.toString();
    let sum = 0;
    for (var i = 0, len = value.length; i < len; i++) {
        sum += value.charCodeAt(i);
    }
    return sum;
}

Simple right ?

Let’s now write code to create a HashMap

class HashMap {
    constructor() {
        this.store = [];
    }
    getHash(value) {
        value = value.toString();
        let sum = 0;
        for (var i = 0, len = value.length; i < len; i++) {
            sum += value.charCodeAt(i);
        }
        return sum;
    }
    set(key, value) {
        const hashValue = this.getHash(key);
        this.store[hashValue] = value;
    }
    get(key) {
        const hashValue = this.getHash(key);
        return this.store[hashValue];
    }
    isExist(key) {
        const hashValue = this.getHash(key);
        return this.store[hashValue] != null;
    }
    remove(key) {
        const hashValue = this.getHash(key);
        this.store[hashValue] = null;
    }
}
const map = new HashMap();
map.set(5, 100);
map.set(8, 200);
console.log(map.get(5));
console.log(map.get(8)); 

Now issue with above approach is - if a hash function generates the same value for different keys then we will replace one key with another loosing a key,value pair. This is called hash collision.

There are different approach to deal with problem. Here we will use a linked list to solve this problem.

So we will store multiple key,value pair of same hash value in a linked list and store linked list at array index.

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.data = null;
    }
    set(key, value) {
        const node = new Node(key, value);
        if (this.root == null) {
            this.root = node;
        } else {
            let root = this.root;
            while (root.next != null) {
                if (root.key === key) {
                    root.value = value;
                    return;
                }
                root = root.next;
            }
            root.next = node;
        }
    }
    get(key) {
        let root = this.root;
        while (root != null) {
            if (root.key === key) {
                return root.value;
            }
            root = root.next;
        }
        return null;
    }
}
class HashMap {
    constructor() {
        this.store = [];
    }
    getHash(value) {
        value = value.toString();
        let sum = 0;
        for (var i = 0, len = value.length; i < len; i++) {
            sum += value.charCodeAt(i);
        }
        return sum;
    }
    set(key, value) {
        const hashValue = this.getHash(key);
        if (this.store[hashValue] == null) {
            this.store[hashValue] = new LinkedList();
        }
        // add or update key,value to linked list
        this.store[hashValue].set(key, value);
    }
    get(key) {
        const hashValue = this.getHash(key);
        if (this.store[hashValue]) {
            return this.store[hashValue].get(key);
        }
        return null;
    }
    isExist(key) {
        const hashValue = this.getHash(key);
        return this.store[hashValue] != null;
    }
    remove(key) {
        const hashValue = this.getHash(key);
        this.store[hashValue] = null;
        // Note :-  here removing will remove all values which is    not a good solution
        // we will have to use double linked list in order to remove a value from linked list
        // I am not doing here, to make program simple
    }
}
const map = new HashMap();
map.set("lies", 100);
map.set("foes", 200);
console.log(map.get("lies")); // 100
console.log(map.get("foes")); // 200

Thanks for reading it guys. If you have enjoyed, please clap and share with your friends.

References

• https://www.interviewcake.com/concept/java/hash-map