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;
}
Top comments (0)