Skip to content

Instantly share code, notes, and snippets.

@Prottoy2938
Created March 12, 2020 05:40
Show Gist options
  • Save Prottoy2938/e4d4c00eb508ad9eb2dae8ce21eab4f3 to your computer and use it in GitHub Desktop.
Save Prottoy2938/e4d4c00eb508ad9eb2dae8ce21eab4f3 to your computer and use it in GitHub Desktop.
Simple Hash Table implementation in JavaScript
//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