DEV Community

loading...

Hash Tables

ivywalobwa profile image Ivy-Walobwa ・3 min read

Hash Tables store data in associative arrays. Data is stored in key/value pairs.
Each key is unique and is mapped to an index where an element can be inserted or removed from array.

Hashing
Hashing involves deriving a fixed size result from an input.
Method of hashing should be;
1.Stable - same input generates same output every time
2.Uniform - hash value should be uniformly distributed through available space
3.Efficient - cost of generating a hash must be balanced with application needs.
4.Secure - cost of finding data that produces a given hash is prohibitive.

Hashing a String
Hashing algorithms are pretty hard to design, pick an existing one right for the job.
The hashing algorithm I picked involves converting a string into an integer and generating indices for the table.

hashing

Handling Collisions
Collisions occur when two distinct keys have the same hash values.

Two common strategies can be used to handle collisions;
1.Open Addressing - here the new item is moved to the next index in table

while (array[index] !== null)
    index++
array[index] = item  

2.Chaining - here the items are stored in linked list

array[index].addToList(item)

Implementation
I will be handling collision using chaining

hash table

1.Create Node class and hash table class

class Node {
    constructor(key, data) {
        this.key = key;
        this.data = data;
        this.next = null;
        this.previous = null;
    }
}

class HashTable{
    constructor() {
        this.buckets = [];
        this.maxBucketCount = 100;
    }
 // add methods   
}

Our hash table creates the bucket which we'll store our key/value pairs. We also set the maximum count to 100. The higher the bucket size, the less number of collisions.

2.Add methods to hash table class

Hashing

 hashCode(val) {
        let i;
        let hashCode = 0;
        let character;

        // If value to be hashed is already an integer, return it.
        if (val.length === 0 || val.length === undefined) {
            return val;
        }

        for (i = 0; i < val.length; i++) {
            character = val.charCodeAt(i);
            hashCode = ((hashCode << 5) - hashCode) + character;
            hashCode = hashCode & hashCode;
        }

        return hashCode % this.maxBucketCount;
    };

The return value is the index in bucket.

Add

 // add key/data pair to bucket
    add(key, data) {
        let newNode = new Node(key, data);
        let hashCode = this.hashCode(key); // get hashcode of key

        // if no element exists at hashcode of key, add to table
        if (this.buckets[hashCode] === undefined) {
            this.buckets[hashCode] = newNode;
            return;
        } 

        // if an element exists at hashcode of key, but keys are same
        // update key with given data
        if (this.buckets[hashCode].key === key) {
            this.buckets[hashCode].data = data;
            return;
        }

        // if an element exists at hashcode of key, but keys are different
        // collision has occured
        // store in linked list
        let current = this.buckets[hashCode];
        while (current.next !== null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.previous = current
    }

Remove

remove(key) {
        let hashCode = this.hashCode(key); // get hashcode of key
        let first = this.buckets[hashCode] //select key/data pair at index

        if (first !== undefined) {
            // if it exists and no has linked list at index
            // (A)
            if (first.next === null) {
                this.buckets[hashCode] = undefined; // remove item
                return;
            } else {
                while (first !== null && first.next !== null && first.key !== key) {
                    first = first.next;
                }
                // if removed is first node in list
                // (A) - B - C - D
                if (first.previous === null && first.next !==null) {
                    while (first.next !== null) {
                        first.key = first.next.key;
                        first.data = first.next.data;
                        first.next.previous.data = first.data
                        first.next.previous.key = first.key
                        first = first.next;
                    }
                }

                // if removed is last node in list
                // A - B - (C)
                if (first.previous !== null && first.next === null) {
                    first.previous.next = null
                    first = null
                    return;
                }

                // if removed is middle node
                // A - (B) - C
                if (first.previous !== null && first.next !== null) {
                    first.previous.next = first.next;
                    first.next.previous = first.previous;
                    first = null;
                    return;
                }
                return;
            }
        }
        return undefined;
    }

We get the index of the array, and remove item from linked list. We also update the previous and next values of the removed node accordingly.

Find

 find(key) {
        let hashCode = this.hashCode(key);
        let current = this.buckets[hashCode];
        if (current !== undefined) {
             // if it's the first item in list
            if (current.next === null && current.key === key) {
                return current.data;
            } else {
                while (current != null && current.next != null && current.key !== key) {
                    current = current.next;
                }
                if (current.key === key) {
                    return current.data;
                }
                return undefined;
            }

        }
        return undefined;

    }

Check out my repository here.

Discussion (0)

pic
Editor guide