Created
March 12, 2020 05:40
-
-
Save Prottoy2938/e4d4c00eb508ad9eb2dae8ce21eab4f3 to your computer and use it in GitHub Desktop.
Simple Hash Table implementation in JavaScript
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
//Hash tables are collection of key value pairs. | |
//This hash function uses Array to store data and uses separate chaining to avoid key collusion. | |
//Only works on alphabetic character string keys. | |
class Hash { | |
constructor(size = 5) { | |
this.table = new Array(size); | |
} | |
//hashes the given key/value. Using the given key, it finds an index on the Table and returns that index. | |
_hash(key) { | |
let total = 0; | |
let primeNum = 31; | |
for (let i = 0; i < Math.min(key.length, 100); i++) { | |
let char = key[i]; | |
let value = char.charCodeAt(0) - 96; | |
total = (total * primeNum + value) % this.table.length; | |
} | |
return total; | |
} | |
//stores data in the table. Uses this._hash to get the index of the given key and pushes key - value pairs into that index. uses separate chaining to avoid key collusion. | |
set(key, value) { | |
let idx = this._hash(key); | |
if (!this.table[idx]) this.table[idx] = []; | |
this.table[idx].push([key, value]); | |
} | |
//Gets value of a given index. | |
get(key) { | |
let idx = this._hash(key); | |
if (this.table[idx]) { | |
for (let i = 0; i < this.table[idx].length; i++) { | |
if (this.table[idx][i][0] === key) { | |
return this.table[idx][i][1]; | |
} | |
} | |
} | |
return undefined; | |
} | |
//returns all the keys that are in the table, also it avoids duplicates. | |
keys() { | |
let obj = {}; | |
this.table.map(data => { | |
data && | |
data.map(d => { | |
!obj[d[0]] ? (obj[d[0]] = d[0]) : null; | |
}); | |
}); | |
return Object.keys(obj); | |
} | |
//returns all the values that are in the table. | |
values() { | |
const result = []; | |
this.table.map(data => { | |
data && | |
data.map(d => { | |
result.push(d[1]); | |
}); | |
}); | |
return result; | |
} | |
} | |
//EXAMPLE | |
const HashFunction = new Hash(); | |
HashFunction.set("name", "prottay"); | |
HashFunction.set("age", 16); | |
HashFunction.set("have anxiety", "yes"); | |
HashFunction.set("needs another laptop", "yes"); | |
console.log(HashFunction.get("name")); | |
console.log(HashFunction.keys()); | |
console.log(HashFunction.values()); | |
export default HashFunction; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment