Data Structures and How To Build It From Scratch (Hash Table) #2
A hash table is a data structure that can be utilized to map keys to their specific values, and it is also known as a Hash Map. Hash tables efficiently perform the insertion and deletion operations for a key-value pair and search for the value of a key within a hash table. By the way, JavaScript provides built-in functions to make a hash table. They are called Map() and Set().
trivia: A Set is a collection dataset that needs to be composed of unique values, where a Map is when you have pairs of associated data when we map the keys to the value
There are 2 components of Hash Table in JavaScript, Object and Hash Function.
- Object contains the hash table in which the data is stored, and it holds all the “key-value” pairs of the hash table.
- Hash Function is defined for a hash table to determine the “index” of the given key-value pair.
So we are going to make one class called HashTable and it contains four methods: hash(), set(), get(), and keys().
First, we have to make a class and its constructor. We need to create an attribute called data to determine the size of the hash map that we will make.
Then we will make a method called _hash(). This method basically returns a random integer (for example, if a given parameter is “grapes” and the size of the constructor is 50, it will return 23). We need this method as an address for other methods (we’ll see later).
After that, we will make a method called set() that will insert the data into a hash table with the key and value as a parameter.
First we need to make an address and use the _hash() method to determine the value itself. Then if this.data[address] is null, we will assign an empty array. And then we push the [key, value] to this.data[address]. Last, we have to return this.data.
Next we have to make a method called get(), this method, if data based on a given key exists, it will return a value based on that key, otherwise it will return undefined.
As always, we have to determine the address as a return of the _hash method. And we must create a variable called currentBucket as a this.data[address] variable. We have to make sure that currentBucket is not null, and if it is null, just return it as undefined.
To have a better understanding of what is going on inside the loop, we have to look at the currentBucket value.
Inside the loop, if currentBucket[i][0] or grapes is === given params key, we’re going to return currentBucket [i][1] or 3. Why do we need to do this? because there is a possibility that the address can be the same even if the key is different.
And the final method is keys(). keys() will return all of the keys inside this.data.
First we make a variable as a temp array, then we loop this.data.length and if this.data[i] is not null, we are going to push every key inside this.data to keyArray.
So, that’s it. We just made our own hash table with class. This is the full code of the Hash Table class.
I’ll see you on Data Structures and How To Build It From Scratch (Linked List) #3!
