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.

**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

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;
}
```

## Discussion (0)