octoberrust
3/1/2020 - 12:47 PM

hash table and linked list

hash table and linked list

//https://medium.com/everything-javascript/implementing-a-hash-table-in-javascript-29aca1edfe2b

import { LinkedList } from "./LinkedList";
//function to turn a key into a "unique identifier";

export class HashTable {
  size: number;
  private table = [];

  constructor(size: number) {
    this.size = size;
    for (let i = 0; i < size; i++) {
      this.table[i] = new LinkedList();
    }
    // console.log
    this.table;
  }

  hash = (key: string): string => {
    var id: number = 0;
    for (let i = 0; i < key.length; i++) {
      id += key.charCodeAt(i) * 100 - key.charCodeAt(i - 1 < 0 ? 0 : i - 1);
    }
    return (id % this.size) + "";
  };

  insert(key: string, value: any) {
    var id: string = this.hash(key);
    var bucket: LinkedList = this.table[id];

    bucket.insert(value, key);
  }
  get(key: string) {
    var id = this.hash(key);
    var bucket: LinkedList = this.table[id];

    if (!bucket.empty()) {
      var value: any = bucket.find(key);
      if (value) return value;
    }
    return "key does not exist";
  }

  print(): void {
    console.log(this.table);
  }
}
//
export class LinkedList {
  private head: any = null;

  empty(): boolean {
    if (this.head) return false;
    return true;
  }

  last(): ListNode {
    var dummy: ListNode = this.head;
    while (dummy.getNext()) {
      dummy = dummy.getNext();
    }
    return dummy;
  }
  find(key: string): any {
    var dummy: ListNode = this.head;
    while (dummy) {
      if (dummy.getKey() == key) return dummy.value();
      dummy = dummy.getNext();
    }
    return false;
  }
  insert(value: any, key: string): void {
    var node: ListNode = new ListNode(value, key);
    if (!this.head) this.head = node;
    else this.last().next(node);
  }

  print(): void {
    var dummy: ListNode = this.head;
    while (dummy) {
      console.log(dummy.value() + " ");
      dummy = dummy.getNext();
    }
  }
}

//node
class ListNode {
  private val: any;
  private key: string;
  private nextNode: any;

  constructor(value: any, key: string) {
    this.nextNode = null;
    this.key = key;
    this.val = value;
  }
  getNext(): ListNode {
    return this.nextNode;
  }
  next(node: ListNode) {
    this.nextNode = node;
  }
  getKey(): string {
    return this.key;
  }

  value(): any {
    return this.val;
  }
}