Data Structures & Algorithms in JavaScript(Hash Table)

Hello, I’m back with another Data Structure Hash Table. It is a widely used data structure for its faster lookup. Like Arrays where data is stored in an indexed structure, whereas hashtable use hash mapped layout.

So, in general, it consists of two things :

• Table: holds the data in an array or an object.
• Hash function: To calculate the hash for the elements in the hash table.

What is Hash Table?

A Hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to value. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. - wikipedia

What is Hash Function?

A hash function is any function that can be used to map a data set of arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes. - wikipedia

Different of Hash Function :

• djb2
• loose loose
• sdbm

for more information here.

List of Available Methods :

• put: Insert an element (it can also update)
• remove: Remove an element
• get: Get the inserted element

Implementation of Hash Table in JavaScript

if you just want the source code find here.

So, let’s started with defining a class ES6 HashTable; It will be the same as Dictionary.

class HashTable {
    constructor() {
        this.table = {};
    }
}

Hash Function

we will use the lose lose hash function, but you can use any of the above hash function

1. If its a number return number
2. If it's not a number then, stringify the key add up all the char with its ASCII value, we can use charCodeAt and divide it with an arbitrary number to work with lower numbers.

    _loseloseHashCode(key) {
        if (typeof key == "number") {
            return key;
        }
        const keyString = toStringFunc(key);
        let code = 0;
        for (let index = 0; keyString < key.length; index++) {
            code += keyString.charCodeAt(index);
        }
        return code % 37;
    }

Before implementing other methods, I want to clarify the differences between a HashMap and HashSet. HashMap behavior is more like a Map or dictionary, whereas elements are hash and stored as key-value pairs. In HashSet is stored as Set. For more information visit here or here.But in this article ,I will explain using hashmap.

Put

1. Check whether the keys and value in not NULL if yes return false.
2. If key and value is not null then calculate the hash using the above hash function method.
3. Set the table property's key as a hash value and value as key-value pairs same as KeyValue class of dictionary.

    put(key, value) {
        if (key != null && value != null) {
            const keyHash = this.getHashCode(key);
            this.table[keyHash] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

Remove

1. Calculate the hash using the above hash function method.
2. Check whether the element with the key is present in the table property if not return undefined.
3. If it's present delete the key in the table.

    remove(key) {
        const keyHash = this.getHashCode(key);
        if (this.table[keyHash]) {
            const value = this.table[keyHash];
            delete this.table[keyHash];
            return value;
        }
        return undefined;
    }

Get

1. Calculate the hash using the above hash function method.
2. Check whether the element with the key is present in the table property if not return undefined.

    get(key) {
        const keyHash = this.getHashCode(key);
        return this.table[keyHash] != null ? this.table[keyHash].value : undefined;
    }

you get the full source here.

So, in an ideal case, the Hash function always produces a different hash for any given key.

Eg: Let say , we want to store the list of email address against its name

dave : dave@gmail.com 

john : john@gmail.com 

so its hash value will be dave: 9 and john:24 use above hash function.
But that's not the case, it may produce the same set of the hash value for two or more keys. This phenomenon is also known as Collision or Hash collision.

Eg: Now, for

nathan: nathan@gmail.com

sargeras: sargeras@gmail.com

Fig: Hash Collision in Hashtable

for both the hash value will be 5 respectively use above hash function.

What is Hash Collision?

In computer science a hash collision or clash is when two pieces of data in a hash table share the same hash value. The hash value, in this case, is derived from a hash function that takes a data input and returns a fixed length of bits - wikipedia

They are various methods to resolve hash collision :

• Open Addressing
  • Some types of probing are linear probing, double hashing, and quadratic probing
• Separate Chaining
• Cache-Conscious Collision Resolution

I will explain in detail in my next blogs.

Conclusion

So, stay tuned for the next blog, in which I will cover linear probing.