Definition of Hash Table JavaScript
Hash Table is a data structure that basically maps the keys to values. It stores the data in an associative manner. In the Hash Table, each value of the associative key is stored at a particular index and this index is generated through some arithmetic operation. This data structure makes the insertion, deletion, and searching operations very efficient no matter how big data size is. It uses the array as a storage medium and the hash function in order to generate the indexes. Hash function takes the key as an input and results in the indices at which the respective values are stored.
Syntax:
As already explained above, a hash table uses the hash function which takes the key and results in the indices at which the particular value of the key will get stored. Hash Function can be implemented in various ways. It depends on the particular algorithm the programmer is using.
In order to create the hash table in Javascript, one needs the Hash class, hash function, and a method implementing the key/value pairs. Given below is the basic syntax of Hash Table in Javascript:
class Hash Table:
class HashTab{
constructor() {
this.size= 0;
this.items = {};
}
}Hash function:
function hashfunc(key)
{
return key% this.size; // this function can be anything
}Function to implement key/value pair:
add(key, value)
{
const index = this.hashfunc();
// function to add the key / value pairs
//logic to handle some condition of collisions
if (some condition)
{
this.items[index];
}
this.items[index][key]= value;
}How does the Hash table work in Javascript?
Let us understand the working of hash table in JavaScript in detail:
1. The first and the foremost task is to convert the key values in the indices/ hash using a hash function implementing some algorithms. These indices will store the values of the respective keys. The value of indices depends on the implementation of the hash function. Not all hash functions are the same.
For example, we are calculating the hash values in the program using the below mechanism:
function hash func(key)
{
return key%9;
}For the (key, value) pairs, hash values would be:
1. (20,9) = 2
2. (65,9) = 2
3. (1,9) = 1
4. (7,9) = 72. If no value is stored at a particular index (position in an array is empty), the value of the respective key is stored and the size of the hash table is incremented.
3. But if there is a collision,i.e. Two or more (key, value) pairs have the same hash value as shown in the above case where (20, 9) and (65, 9) have the same hash 2, the programmer uses the collision mechanism to handle such a situation.
There are a number of collision resolution algorithms already defined like Linear Probing, Separate Chaining, etc. It depends on the requirements and the choice of the programmer to choose any of them or develop the specific one.
Examples
Below given is the Javascript code implementing Hash Table to store the (key, value) pair of the marks of the students in college. Search function is implemented to search the marks of the given student. If the student will not be found, it will return ‘null’.
<!DOCTYPE html>
<html>
<body>
<h1>My First Javascript Hash Table code</h1>
<script>
//Hash Table class having the constructor defining all the variables
class HashTab {
constructor() {
this.len = 0;
this.size = 0;
//array ‘items’ to store the 'values' of the respective keys at the calculated indices
this.items = {};
}
//Hash Function implementing logic to calculate indices with the key passed
hashFunction(key) {
return key.toString().length % 9;
}
//Add function to n store the (key, values) according to the collision mechanism
addingValues(key, value) {
const hash_val = this.hashFunction(key);
if (!this.items.hasOwnProperty(hash_val)) {
this.items[hash_val] = {};
}
//check if the calculated index position is empty or not for collision resolution
if (!this.items[hash_val].hasOwnProperty(key)) {
this.len++;
}
this.items[hash_val][key] = value;
}
//Search function to search the value of the ‘key’ provided
searching(key) {
const hash_val = this.hashFunction(key);
if (this.items.hasOwnProperty(hash_val) && this.items[hash_val].hasOwnProperty(key)) {
return this.items[hash_val][key];
} else {
return null;
}
}
}
//creating the object ‘htab’ of the type hash table
const htab = new HashTab();
//adding marks of students to the hash table htab
htab.addingValues("Yashika", "300");
htab.addingValues("Gourank", "100");
htab.addingValues("Shipra", "250");
htab.addingValues("Shra", "270");
//searching the 'value' of the key 'Gourank'
document.write(htab.searching("Gourank"));
</script>
</body>
</html>Output:
Explanation:
As discussed above in the working of Hash Table in Javascript, the same steps are followed in the code, i.e.
Class of Hash Table with the name ‘HashTab’ is created having the variables and the array ‘item’ defined.
Next the hash function with the name ‘hash function()’ is created in order to calculate the hash value using ‘key.toString().length % 9’ (for Gourank, the hash value would be 7).
Then the ‘addingValues()’ function is created by passing the key and values. First, the hash value is retrieved and check if it does not already exist, if not we will store it in the object-store. Then the second check is made on the hash, if it does not have the key saved, we will store the (key, value) pair and increment the size of the table.
Once the implementation of the Hash table is done, search function ‘searching’ is implemented to find the value of the key provided. It again calculates the hash value and performs the check if the hash value and the required key at that hash value are present or not. If found, it will return the value of the key given else it will return ‘null’.
Objects of the class ‘HashTab’ ‘htab’ are created and values are passed through them using the function ‘adddingValues’ by passing the (key, value) pairs. Search is then performed using the key.
Conclusion
The above description clearly explains what the Hash Table is and how it works in Javascript. Basically, Hash table is nothing but the implementation of associative arrays. Though many programming languages support associative arrays, Javascript does not. In Javascript, arrays use numbered indexes only, so in order to store the (key, value) pairs, a Hash table is used with the help of a hash function.