Custom implementation of hashMap in javascript
Introduction
HashMap is a data structure which stores data in the form of key & value. Every key of hashMap is unique.
If you will compare - Javascript by default provides object Literal which acts as hashMap.
var obj = { name:'ujjwal gupta'
}
Also javascript provides Map & WeakMap to store value in form of key, value.
How about creating your custom implementation of HashMap ?
Generally this is not needed but its good for understanding how hashMap works. In this article i am going to explain how hashMap works along with custom implementation of hashMap.
Let’s Code
A hash map is nothing but array where array index act as keys. So if we can somehow convert a key to index then we can store the key, value pair in array.
Convert key into Index
Here a hashing function is used which converts any value to a number which will be used as index.
A simple hashing function is convert a value to sum of character ascii value.
getHash(value) {
value = value.toString();
let sum = 0;
for (var i = 0, len = value.length; i < len; i++) {
sum += value.charCodeAt(i);
}
return sum;
}Simple right ?
Let’s now write code to create a HashMap
class HashMap {
constructor() {
this.store = [];
} getHash(value) {
value = value.toString();
let sum = 0;
for (var i = 0, len = value.length; i < len; i++) {
sum += value.charCodeAt(i);
}
return sum;
} set(key, value) {
const hashValue = this.getHash(key);
this.store[hashValue] = value;
} get(key) {
const hashValue = this.getHash(key);
return this.store[hashValue];
} isExist(key) {
const hashValue = this.getHash(key);
return this.store[hashValue] != null;
} remove(key) {
const hashValue = this.getHash(key);
this.store[hashValue] = null;
}
}const map = new HashMap();
map.set(5, 100);
map.set(8, 200);console.log(map.get(5));
console.log(map.get(8));
Now issue with above approach is - if a hash function generates the same value for different keys then we will replace one key with another loosing a key,value pair. This is called hash collision.
There are different approach to deal with problem. Here we will use a linked list to solve this problem.
So we will store multiple key,value pair of same hash value in a linked list and store linked list at array index.
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}class LinkedList {
constructor() {
this.data = null;
} set(key, value) {
const node = new Node(key, value);
if (this.root == null) {
this.root = node;
} else {
let root = this.root;
while (root.next != null) {
if (root.key === key) {
root.value = value;
return;
}
root = root.next;
}
root.next = node;
}
} get(key) {
let root = this.root;
while (root != null) {
if (root.key === key) {
return root.value;
}
root = root.next;
}
return null;
}
}class HashMap {
constructor() {
this.store = [];
} getHash(value) {
value = value.toString();
let sum = 0;
for (var i = 0, len = value.length; i < len; i++) {
sum += value.charCodeAt(i);
}
return sum;
} set(key, value) {
const hashValue = this.getHash(key);
if (this.store[hashValue] == null) {
this.store[hashValue] = new LinkedList();
}
// add or update key,value to linked list
this.store[hashValue].set(key, value);
} get(key) {
const hashValue = this.getHash(key);
if (this.store[hashValue]) {
return this.store[hashValue].get(key);
}
return null;
} isExist(key) {
const hashValue = this.getHash(key);
return this.store[hashValue] != null;
} remove(key) {
const hashValue = this.getHash(key);
this.store[hashValue] = null;
// Note :- here removing will remove all values which is not a good solution
// we will have to use double linked list in order to remove a value from linked list
// I am not doing here, to make program simple
}
}const map = new HashMap();
map.set("lies", 100);
map.set("foes", 200);console.log(map.get("lies")); // 100
console.log(map.get("foes")); // 200
Thanks for reading it guys. If you have enjoyed, please clap and share with your friends.
