Skip to content

Instantly share code, notes, and snippets.

@octoberrust
Created March 1, 2020 12:47
Show Gist options
  • Save octoberrust/b6323840ce370167373b63c2240097b1 to your computer and use it in GitHub Desktop.
Save octoberrust/b6323840ce370167373b63c2240097b1 to your computer and use it in GitHub Desktop.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment