Last active
March 2, 2018 21:16
-
-
Save scwood/9704311f7868aaf5c153d76af9591203 to your computer and use it in GitHub Desktop.
Hash table implementation in JavaScript with linear probing
This file contains hidden or 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
| 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