Hash Tables
Tags: javascript, webdev
Published: 2020-04-17 19:04:53

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](https://dev-to-uploads.s3.amazonaws.com/i/3eyl8i9dbctmttaii8h7.png)

**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](https://dev-to-uploads.s3.amazonaws.com/i/5iexd1tgfh0r689qgozu.png)

1.Create Node class and hash table class

```javascript
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**
```javascript
 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**
```javascript
 // 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**
```javascript
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**
```javascript
 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](https://github.com/Ivy-Walobwa/DataStructure-n-Algorithms-JavaScript).