...
/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.
We'll cover the following...
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.6HashTable.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 slotsfor (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 capacityconsole.log(ht.slots);ht.resize();// New capacityconsole.log(ht.slots);