Skip to content

Instantly share code, notes, and snippets.

@Lugriz
Created July 25, 2020 04:55
Show Gist options
  • Save Lugriz/a518745f526c0864878207706f3a3bc6 to your computer and use it in GitHub Desktop.
Save Lugriz/a518745f526c0864878207706f3a3bc6 to your computer and use it in GitHub Desktop.
Hashtable implementation
/**
* ht.set('myKey2', value);
* |
* v
* hash(key) -> index
* |
* v
* 0| (myKey2, value) -> (myKey, value) -> null,
* 1| ,
* 2| ,
*
* ===========================
* ht.get('myKey')
* |
* v
* hash(key) -> index
* |
* v
* 0| value,
* 1| ,
* 2| ,
*/
class HashNode {
public next: HashNode = null;
constructor(
public key: string,
public value: number
) {}
}
class HashTable {
public table: HashNode[] = new Array(2);
private length: number = 0;
public set(key: string, value: number): void {
const index = this.hash(key);
const foundNode = this.findNode(this.table[index], key);
if (foundNode) {
foundNode.value = value;
} else {
const node = new HashNode(key, value);
node.next = this.table[index]; // 2 -> 1 -> null
this.table[index] = node;
this.length++;
}
}
public get(key: string): number {
const index = this.hash(key);
const foundNode = this.findNode(this.table[index], key);
if (foundNode) {
return foundNode.value;
}
return null;
}
public delete(key: string): void {
const index = this.hash(key);
let currentNode: HashNode = this.table[index];
let previousNode: HashNode = null;
while (currentNode) {
if(currentNode.key === key) {
if (previousNode) {
previousNode.next = currentNode.next;
} else {
this.table[index] = currentNode.next;
}
this.length--;
return;
}
previousNode = currentNode;
currentNode = currentNode.next;
}
}
public size(): number {
return this.length;
}
private findNode(node: HashNode, key: string): HashNode {
while (node) {
if (node.key === key) {
return node;
}
node = node.next;
}
return null;
}
private hash(key: string): number {
return key.length % this.table.length;
}
}
const h = new HashTable();
console.log('SIZE:', h.size());
h.set('one', 1);
h.set('two', 2);
h.set('three', 3);
h.set('four', 4);
h.set('four', 45);
console.log('ONE:', h.get('one'));
console.log('TWO:', h.get('two'));
console.log('THREE:', h.get('three'));
console.log('FOUR:', h.get('four'));
console.log('NONE:', h.get('none'));
console.log('SIZE:', h.size());
h.delete('two');
h.delete('three');
h.delete('none');
console.log('=============');
console.log('ONE:', h.get('one'));
console.log('TWO:', h.get('two'));
console.log('THREE:', h.get('three'));
console.log('FOUR:', h.get('four'));
console.log('SIZE:', h.size());
console.log(h.table);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment