...

/

Add/Remove & Search in Hash Table (Implementation)

Add/Remove & Search in Hash Table (Implementation)

This lesson will cover the JavaScript Implementation for search, insertion and deletion in hash tables.

Resizing in a Hash Table

To start things off​, we will make sure that the hash table doesn’t get loaded beyond a certain threshold. Whenever it crosses the threshold, we shift the elements from the current table to a new table with double the capacity. This helps us avoid collisions.

To implement this, we will make the resize() function:

Press + to interact
index.js
HashTable.js
HashEntry.js
"use strict";
const HashEntry = require('./HashEntry.js');
const HashTable = require('./HashTable.js');
let threshold = 0.6
HashTable.prototype.resize = function (){
let new_slots = this.slots * 2;
let new_bucket = [];
for(var n=0; n<new_slots; n++){
new_bucket[n]=null;
}
this.slots = new_slots;
// rehash all items into new slots
for (var i=0; i<this.bucket.length; i++){
let head = this.bucket[i];
while (head != null){
let new_index = this.getIndex(head.key);
if (new_bucket[new_index] == null){
new_bucket[new_index] = new HashEntry(head.key, head.value);
}
else{
let node = new_bucket[new_index];
while (node != null){
if (node.key == head.key){
node.value = head.value;
node = null;
}
else if (node.next == null){
node.next = new HashEntry(head.key, head.value);
node = null;
}
else{
node = node.next;
}
}
}
head = head.next
}
}
this.bucket = null;
this.bucket = new_bucket;
}
let ht = new HashTable();
// Current capacity
console.log(ht.slots);
ht.resize();
// New capacity
console.log(ht.slots);

Insertion in Table

...