Question

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;

How to properly implement the HashMap data structure class with seperate chaining using linked lists in JavaScript?

LEAVE A COMMENT Hủy