Created
March 1, 2020 12:47
-
-
Save octoberrust/b6323840ce370167373b63c2240097b1 to your computer and use it in GitHub Desktop.
hash table and linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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