This is part 2 of a two-part article on hash tables. In the first part of this article we looked at what hash tables are, how they work, and the various parts of a hash table. In this part, we will implement a hash table in Javascript, so let's begin.
Our hash table is going to have 4 main methods and we are going to be using separate chaining to handle collisions. We will use Map objects in the buckets/slots to store the data (keys and values). The four main methods of our hash table are:
Put: Add a key and value to the table.
Get: Find and return the value of a key.
Remove: Delete a key and value from the table.
IsPresent: Check if a key is present in the table.
Hash Function
Before we start building our hash table, let's first make our hash function.
const hashFunc = (key, size) => {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i)
}
return hash % size
}
The hash function takes in 2 parameters, the key and the size of the table. Each character in the key is converted to UTF-16 code using the charCodeAT string method and added up, the resulting value is modded(%) by the size of the table, it is recommended that the size be a prime number to reduce the chances of collision. The value we get from the equation is returned and will be used in storing and retrieving data in other functions.
Hash Table
class HashTable {
constructor(){
this.size = 97,
this.table = Array(this.size)
}
}
The class constructor has only 2 properties, the size of the table (97) and the array itself, hash tables use static arrays to store the data. The size of a static array is set when it is created and will not change unless explicitly changed, unlike dynamic arrays that change with an increase in the data inside them.
Put Method
put(key, data){
let hashCode = hashFunc(key, this.size)
if(!this.table[hashCode]){
this.table[hashCode] = new Map();
this.table[hashCode].set(key, data);
}else {
this.table[hashCode].set(key, data)
}
}
The first method of our hash table is the put method, as the name implies, it puts data into the table; it takes 2 parameters the key and the data. Let's break down how it works.
Method Break-Down
- Get the hash code from the
hashFuncby passing it the key and the table size property. - Check if that bucket is occupied; if it is not occupied create a new map object and set the data in it.
- If that table is occupied then just insert the data into the map object that we know will be there.
Get Method
get(key){
let hashCode = hashFunc(key, this.size)
if(this.table[hashCode]){
return this.table[hashCode].get(key)
}else {
return "no such data"
}
}
The get method takes a key and returns the data that is paired with that key in the table.
Method Break-Down
First, get the hash code from
hashFunc.Check if there is data in that position of the table; if yes, get the value of the key from the map object and return it.
If that position in the table is empty, let the user know the data doesn't exist.
Remove Method
remove(key){
let hashCode = hashFunc(key, this.size)
if(this.table[hashCode]){
let data = this.table[hashCode].get(key);
this.table[hashCode].delete(key)
return data
}else {
return "no such data"
}
}
This method deletes data from a table.
Method Break-Down
First, get the hash code from
hashFunc.Check if there is data in that position of the table; if yes, get the value of the key from the map object and store it in a variable; delete the key and value from the map object, and return the variable.
If that position in the table is empty, let the user know the data doesn't exist.
IsPresent Method
isPresent(key){
let hashCode = hashFunc(key, this.size)
if(this.table[hashCode]){
return this.table[hashCode].has(key);
}
}
This is a simple method to determine if a key already exists in the table.
Method Break-Down
First, get the hash code from
hashFunc.Check if there is data in that position of the table; if yes, check if the map object there has any keys that match the given key and return the result.
Complete Code
const hashFunc = (key, size) => {
let hashCode = 0;
for (let i = 0; i < key.length; i++) {
hashCode += key.charCodeAt(i)
}
return hashCode % size
}
class HashTable {
constructor(){
this.size = 97,
this.table = Array(this.size)
}
put(key, data){
let hashCode = hashFunc(key, this.size)
if(!this.table[hashCode]){
this.table[hashCode] = new Map();
this.table[hashCode].set(key, data);
}else {
this.table[hashCode].set(key, data)
}
}
get(key){
let hashCode = hashFunc(key, this.size)
if(this.table[hashCode]){
return this.table[hashCode].get(key)
}else {
return "no such data"
}
}
remove(key){
let hashCode = hashFunc(key, this.size)
if(this.table[hashCode]){
let data = this.table[hashCode].get(key);
this.table[hashCode].delete(key)
return data
}else {
return "no such data"
}
}
isPresent(key){
let hashCode = hashFunc(key, this.size)
if(this.table[hashCode]){
return this.table[hashCode].has(key);
}
}
}
Conclusion
This brings us to the end of this article on Hash Tables and this series on data structures. I learned a lot from writing these articles and it has helped me better understand and internalize certain concepts about programming and what it means to be a developer. My next series will be on algorithms where I will cover topics such as recursion, time complexity, space complexity, sorting etc; I hope you'll give them a read. The code for this article can be found here. Thank you for making it this far and see you soon.
