This content originally appeared on DEV Community and was authored by AvishkarDalvi
We often use Hashtables/Maps/Dictionaries to store data as they provide fast lookups at O(1). Even arrays provide O(1) lookups but only if you are aware of the index of the element that you are trying to access, otherwise you have to loop through the array and check every element to finally find a match thereby making the time complexity O(n).
In JavaScript, even objects are like maps as even they store data in key-value pairs but the only difference is objects can only have strings as keys whereas maps can have any data type as a key.
Let's implement our very own HashTable.For this, we will declare a JavaScript class with a constructor with just one property that will be an array(an array of arrays to be fair).
class HashTable {
constructor(size){
this.data = new Array(size);
}
As we know for O(1) lookup we need to store the key-value pair at a particular index in this array so that we can access the same using that index. Thus whenever we insert a key-value pair in the HashTable, the key is passed to a hash function that generates an array index location where the key will be stored. This particular hash function has to be an idempotent hash function, which means that a given input will always generate the same output. (example: if it generates 104 for 'mango' then it will always generate 104 for 'mango', the output will not change over time).
Let's implement the hash function, I am using the below logic you can use any hashing logic you wish.
hash(key) {
let hash = 0;
for (let i =0; i < key.length; i++){
hash = (hash + key.charCodeAt(i) * i) % this.data.length
}
return hash;
}
Java guys can make this hash function private, as it will only be used internally. Notice that we use % this.data.length so that the hash value which will be used as the array index of the list this.data does exceed the length of this.data.
Now, let's use this hash function to insert key-value pairs in our HashTable by implementing the set method. This method takes two parameters namely the key and value, in which the key is passed to the hash function which generates a number that is the index position of the this.data array and we will store this key-value pair as an array at the index location i.e [key, value] at this.data[hashValueOfKey].
set(key, value) {
let address = this.hash(key);
if (!this.data[address]) {
this.data[address] = [];
}
this.data[address].push([key, value]);
return this.data;
}
Here we calculate the hash for the key, check if something exists at that calculated hash index of that array, if not then we create an array at that index place the key-value pair inside it. If the array index already holds an array of key-value pairs then we push the new array of key-value pairs inside the array present at that index of this.data.
Lastly, let's implement the get function that accepts the key as a parameter and retrieves the value that we inserted alongside that key. In this function first, we calculate the hash for key passed as our hash function is an idempotent function thus it will generate the same value(index of this.data) that was generated at the time of insertion of the key-value pair in case of set method. Then if we find an array present that at the generated index location of this.data then we iterate over that array(this array contains arrays that have two elements key and value i.e [key, value]) and check if the key passe to our get function matches with the first element of any of the subarrays, as the first element is the key and the second element is the value. If we find a match then we return the second element i.e value of that array else we return undefined.
get(key){
const address = this.hash(key);
const currentBucket = this.data[address]
if (currentBucket) {
for(let i = 0; i < currentBucket.length; i++){
if(currentBucket[i][0] === key) {
return currentBucket[i][1]
}
}
}
return undefined;
}
In this way, we have implemented the HashTable with O(1) insertion and lookup, below is the full code
class HashTable {
constructor(size){
this.data = new Array(size);
}
hash(key) {
let hash = 0;
for (let i =0; i < key.length; i++){
hash = (hash + key.charCodeAt(i) * i) % this.data.length
}
return hash;
}
set(key, value) {
let address = this.hash(key);
if (!this.data[address]) {
this.data[address] = [];
}
this.data[address].push([key, value]);
return this.data;
}
get(key){
const address = this.hash(key);
const currentBucket = this.data[address]
if (currentBucket) {
for(let i = 0; i < currentBucket.length; i++){
if(currentBucket[i][0] === key) {
return currentBucket[i][1]
}
}
}
return undefined;
}
}
const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')
This content originally appeared on DEV Community and was authored by AvishkarDalvi
AvishkarDalvi | Sciencx (2021-08-19T18:39:32+00:00) Your own HashTable/Dictionary/Map in JavaScript. Retrieved from https://www.scien.cx/2021/08/19/your-own-hashtable-dictionary-map-in-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.