Skip to content

Instantly share code, notes, and snippets.

@scwood
Last active March 2, 2018 21:16
Show Gist options
  • Select an option

  • Save scwood/9704311f7868aaf5c153d76af9591203 to your computer and use it in GitHub Desktop.

Select an option

Save scwood/9704311f7868aaf5c153d76af9591203 to your computer and use it in GitHub Desktop.
Hash table implementation in JavaScript with linear probing
class HashTable {
constructor() {
this.table = [];
this.length = 0;
this.maxLength = 8;
this.maxLoadFactor = 0.75;
}
set(key, value) {
this.length++;
let hashedKey = this._hash(key);
while (this.table[hashedKey] !== undefined) {
if (this.table[hashedKey][0] === key) {
this.length--;
break;
}
hashedKey = this._incrementKey(hashedKey);
}
const tuple = [key, value];
this.table[hashedKey] = tuple;
if (this.length / this.maxLength >= this.maxLoadFactor) {
this._resize();
}
}
get(key) {
const index = this._findIndex(key);
return this.table[index][1];
}
delete(key) {
const index = this._findIndex(key);
this.table[index] = undefined;
this.length--;
}
_findIndex(key) {
let hashedKey = this._hash(key);
const originalHashedKey = hashedKey;
for (;;) {
if (this.table[hashedKey] === undefined) {
throw new Error(`Missing key: ${key}`);
}
if (this.table[hashedKey][0] === key) {
return hashedKey;
}
hashedKey = this._incrementKey(hashedKey);
if (hashedKey === originalHashedKey) {
throw new Error(`Missing key: ${key}`);
}
}
}
_hash(key) {
const string = String(key);
let hash = 0;
if (string.length === 0) {
return hash;
}
for (let i = 0; i < string.length; i++) {
const char = string.charCodeAt(i);
hash = ((hash << 5) - hash) + char;
hash |= 0;
}
return hash % this.maxLength;
}
_incrementKey(key) {
return (key + 1) % this.maxLength;
}
_resize() {
const oldTable = this.table;
this.table = [];
this.length = 0;
this.maxLength *= 2;
for (const tuple of oldTable) {
if (tuple !== undefined) {
const [key, value] = tuple;
this.set(key, value);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment