Hashing is a popular technique used for storing and retrieving data as fast as possible. The main reason behind using hashing is that it performs insertion, deletion, searching, and other operations
Why use Hashing?
In hashing, all the operations like inserting, searching, and deleting can be performed in O(1) i.e. constant time. The worst case time complexity for hashing remains O(n) but the average case time complexity is O(1).
Basic Operations with Syntax:
HashTable: Used in order to create a new hash table.
// function to delete a key from the hashtable
delete (key) {
const index = this._setKey(key);
if (this.table[index]) {
this.table[index] = [];
this.size--;
return true;
} else {
return false;
}
}
Get: Used to search a key inside the hash table and return the value that is associated with that key.
// function inside hashtable class to
// access a value using its key
get(key) {
const target = this._setKey(key);
return this.table[target];
}
Insert: Used to insert a new key-value pair inside the hash table.
// function to insert a value in the
// hash table using setKey function
insert(value) {
const index = this._setKey(value);
this.table[index] = value;
this.size++;
}
Search: Used to search for a value.
// search a value (by getting its
// key using setKey function)
search(value){
const index = this._setKey(value);
if(this.table[index]==value)
console.log("The value is found at index : ",index);
else
console.log("Not found");
}
Delete: Used in order to delete a particular key-value pair from the hash table.
// function to delete a key from the hashtable
delete (key) {
const index = this._setKey(key);
if (this.table[index]) {
this.table[index] = [];
this.size--;
return true;
} else {
return false;
}
}
Components of Hashing in Javascript:
1. Hash Table: A hash table is a generalization of the array. It gives the functionality in which a collection of data is stored in such a way that it is easy to find those items later if required. This makes searching for an element very efficient.
2. Hash Function: A hash function is used to transform a given key into a specific slot index. it is used to map each and every possible key into a unique slot index. If every key is mapped into a unique slot index, then the hash function is known as a perfect hash function. It is very difficult to create a perfect hash function but our job as a programmer is to create such a hash function with the help of which the number of collisions is as few as possible.
A good hash function should have the following properties:
- Efficiently computable.
- Should uniformly distribute the keys (Each table position is equally likely for each).
- Should minimize collisions.
- Should have a low load factor(the number of items in the table divided by the size of the table).
3. Collision Handling: Since a hash function gets us a small number for a big key, there is a possibility that two keys result in the same value. The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision and must be handled using some collision handling technique. Following are the ways to handle collisions:
- Chaining: The idea is to make each cell of the hash table point to a linked list of records that have the same hash function value. Chaining is simple but requires additional memory outside the table.
- Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we examine the table slots one by one until the desired element is found or it is clear that the element is not in the table.
Implementation with Example:
Step 1: Create a HashTable class with table and size initial properties.
Step 2: Add a private setKey(key) function to transform keys into indices.
Step 3: Add the insert() and get()functions for adding and accessing key-value pairs from the table.
Step 4: Add a remove() function to remove a key from the hash table.
Example 1: Suppose we have to store 5 numbers 100,87,86,12,25 and 9 in a hashtable. In this case, we will create a setKey function in which we will take the value as an argument and convert it to an index of the hash table. Below is the implementation.
Javascript
<script> // HashTable Implementation class HashTable { constructor() { this.table = new Array(10); this.size = 0; } // private function to convert key to index // _ shows that the function is private _setKey(key) { return key % 10; } // insert value in the hashtable insert(value) { const index = this._setKey(value); this.table[index] = value; this.size++; } get(key) { const target = this._setKey(key); return this.table[target]; } search(value) { const index = this._setKey(value); if (this.table[index] == value) console.log("The value is found at index : ", index); else console.log("Not found"); } delete(key) { const index = this._setKey(key); if (this.table[index]) { this.table[index] = []; this.size--; return true; } else { return false; } } } const hashExample = new HashTable(); // insert hashExample.insert(100); hashExample.insert(87); hashExample.insert(86); hashExample.insert(12); hashExample.insert(9); console.log(hashExample.table); // -> shows the hash table // search hashExample.search(87); // found hashExample.search(10); // not found // delete hashExample.delete(12); // showing table after deletion console.log(hashExample.table); </script> |
Output:
[ 100, <1 empty item>, 12, <3 empty items>, 86, 87, <1 empty item>, 9 ] The value is found at index : 7 Not found [ 100, <1 empty item>, [], <3 empty items>, 86, 87, <1 empty item>, 9 ]
In output <1 empty item> or <3 empty item> shows that the table is having 1 or 3 consecutive empty spaces/indexes.
Example 2: Suppose we want to store the contact numbers of a family of 5 members in a hash table. For this, we’ll create a hash table of size 10 and store the contact details. The index will be set using the setKey private function which will convert the last digit of the contact number as the index of the hash table.
Javascript
<script> // HashTable Implementation class HashTable { constructor() { this.table = new Array(10); this.size = 0; } // private function to convert key to index // _ shows that the function is private _setKey(key) { const lastDigit = key % 10; return lastDigit; } // insert value in the hashtable insert(value) { const index = this._setKey(value); this.table[index] = value; this.size++; } get(key) { const target = this._setKey(key); return this.table[target]; } search(value) { const index = this._setKey(value); if (this.table[index] == value) console.log("The contact number is found at index : ", index); else console.log("Contact Number not found"); } delete(key) { const index = this._setKey(key); if (this.table[index]) { this.table[index] = []; this.size--; return true; } else { return false; } } } const hashExample = new HashTable(); // insert hashExample.insert(98754525); hashExample.insert(98747512); hashExample.insert(94755523); hashExample.insert(92752521); hashExample.insert(98556529); console.log(hashExample.table); // -> shows the hash table // search hashExample.search(92752521); // found hashExample.search(92755784); // not found // delete hashExample.delete(92752521); // showing table after deletion console.log(hashExample.table); </script> |
Output:
[ <1 empty item>, 92752521, 98747512, 94755523, <1 empty item>, 98754525, <3 empty items>, 98556529 ] The contact number is found at index : 1 Contact Number not found [ <1 empty item>, [], 98747512, 94755523, <1 empty item>, 98754525, <3 empty items>, 98556529 ]
In output <1 empty item> or <3 empty item> shows that the table is having 1 or 3 consecutive empty spaces/indexes.