So i tried implementing the HashMap data structure in JavaScript and i’m not really sure whether it’s the proper way of implementing it. If maybe you could give a better implementation or just improve my code, it’d be of great help.
Here is my implementation of the HashMap data structure with seperate chaining:
const Node = require('../../linear_data_structures/Node/Node_6');
const LinkedList = require('../../linear_data_structures/LinkedList/SinglyLinkedList/LinkedList_7');
class HashMap {
constructor(size = 1) {
this.hashmap = new Array(size)
.fill(null)
.map(() => new LinkedList());
}
hash(key) {
let hashCode = 0;
for (let i = 0; i < key.length; i++) {
hashCode += key.charCodeAt(i);
}
return hashCode % this.hashmap.length;
}
assign(key, value) {
const arrayIndex = this.hash(key);
const linkedList = this.hashmap[arrayIndex];
if (!linkedList.head) {
linkedList.addToHead({ key, value });
return;
}
let current = linkedList.head;
while (current) {
if (current.data.key === key) {
current.data = { key, value };
break;
}
if (current.getNextNode() === null) {
const lastNode = new Node({ key, value });
current.setNextNode(lastNode);
break;
}
current = current.getNextNode();
}
}
retrieve(key) {
const arrayIndex = this.hash(key);
let current = this.hashmap[arrayIndex].head;
while (current) {
if (current.data.key === key) {
return current.data.value;
}
current = current.getNextNode();
}
return null;
}
delete(key) {
const arrayIndex = this.hash(key);
let linkedList = this.hashmap[arrayIndex];
let current = linkedList.head;
let prev;
while (current) {
if (current.data.key === key) {
if (prev) {
prev.setNextNode(current.getNextNode());
} else {
linkedList.head = current.getNextNode();
}
return current.data.value;
}
prev = current;
current = current.getNextNode();
}
return null;
}
printListByKey(key) {
const arrayIndex = this.hash(key);
let current = this.hashmap[arrayIndex].head;
const output = [];
while (current) {
output.push(current.data.value);
current = current.getNextNode();
}
console.log('<head> ' + output.join(' --> ') + ' <tail>');
}
}
module.exports = HashMap;
Here is the Node class I used for the HashMap.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
setNextNode(data) {
if (data instanceof Node || data === null) {
this.next = data;
} else {
throw new Error("Expected Node instance or null");
}
}
getNextNode() {
return this.next;
}
}
module.exports = Node;
and, Here is the Singly Linked List class I used for the HashMap
const Node = require('../../Node/Node_6');
class LinkedList {
constructor() {
this.head = null;
}
addToHead(data) {
const newHead = new Node(data);
const currentHead = this.head;
this.head = newHead;
if (currentHead) {
this.head.setNextNode(currentHead);
}
}
addToTail(data) {
const lastNode = this.head;
if (!lastNode) {
this.head = new Node(data);
} else {
let temp = this.head;
while (temp.getNextNode() !== null) {
temp = temp.getNextNode();
}
temp.setNextNode(new Node(data));
}
}
removeHead() {
const removedHead = this.head;
if (!removedHead) {
return;
}
this.head = removedHead.getNextNode()
return removedHead.data;
}
removeTail() {
const lastNode = this.head;
if (!lastNode) {
return;
} else {
let removedTail = this.head;
let pred;
while (removedTail.getNextNode() !== null) {
pred = removedTail;
removedTail = removedTail.getNextNode();
}
if (pred) {
pred.setNextNode(null);
return removedTail.data;
} else {
return this.removeHead();
}
}
}
removeByData(data) {
let currentNode = this.head;
let removedNode;
if (currentNode.data === data) {
return this.removeHead();
}
while (currentNode.getNextNode().data !== data) {
currentNode = currentNode.getNextNode();
}
removedNode = currentNode.getNextNode();
currentNode.setNextNode(removedNode.getNextNode());
return removedNode.data;
}
printList() {
let currentNode = this.head;
let output = '<head> ';
while (currentNode) {
output += currentNode.data + ' ';
currentNode = currentNode.getNextNode();
}
output += '<tail>';
console.log(output);
}
}
module.exports = LinkedList;
New contributor