I'm creating this Hash Table in JavaScript and I want it warn me each time I'm adding existing values in the array. I tried my own implementation, but it isn't working.
function hashFunction(s,tableSize){
let hash = 17;
for(let i = 0; i<s.length; i++){
hash = (13*hash * s.charCodeAt(i)) % tableSize;
}
return hash;
};
class HashTable {
table = new Array(2000);
numItems = 0;
loadFactor = this.numItems/this.table.length;
setItem = (key,value)=>{
const idx = hashFunction(key, this.table.length);
if(this.table.includes(key)){
return "already exists"
}else this.numItems++
if(this.table[idx]){
this.table[idx].push([key,value])
}else this.table[idx]=[[key,value]];
};
getItem = (key)=>{
const idx = hashFunction(key,this.table.length);
if(!this.table[idx]){
return "Key doesn't exist";
}else
return this.table[idx].find(x=>x[0]===key)[1];
};
};
let myHash = new HashTable
myHash.setItem("first","daniel")
myHash.setItem("last","esposito")
myHash.setItem("age","21")
myHash.setItem("height","1,90")
It would be beneficial to review implementing pseudo code and existing implementations. There were numerous errors which can summarized as the original implementation failing to correctly handle pairs within a bucket.
Here is a working update which salvages some of the structure while discarding most of the inconsistent and/or incorrect implementation - I've left comments as reference points to understand why the original was incorrect. The code has been structured to illustrate access/creation of buckets, access/creation of pairs within the buckets, and behavior selection depending on the case.
YMMV.
function hashFunction(s, tableSize){
let hash = 17;
for (let i = 0; i < s.length; i++){
hash = (13 * hash + s.charCodeAt(i)) % tableSize;
// ^-- Ry suggests the original * is a typo.
}
return hash;
};
class HashTable {
// I've eliminated 'load factor' to cover a basic implementation.
// See rebalancing, good table size selection, alternative collision
// resolution strategies, etc.
// This implementation might pass a CS101 course.
// Yes, for THIS EXAMPLE the TABLE SIZE IS CHOSEN AS 2.
// This ensures that there are multiple items per bucket
// which guarantees the collision resolution paths are invoked.
// This is a terrible choice in practice.
table = new Array(2);
numItems = 0;
setItem = (key, value)=>{
const idx = hashFunction(key, this.table.length);
// set/get should ONLY access simple properties or
// a BUCKET from the hash code as top-level structures.
// (Using table.includes(..) here is fundamentally INCORRECT.)
let bucket = this.table[idx];
if (bucket) {
// Existing bucket. Search in HERE to see if the key exists.
// This should generally be the same code as the "get".
let pair = bucket.find(x => x[0] === key);
if (pair) {
// Same pair, update value.
pair[1] = value;
return false; // "existing"
} else {
// Add new pair to bucket.
bucket.push([key, value]);
this.numItems += 1;
return true; // "new"
}
} else {
// Create a new bucket and item pair.
this.table[idx] = [[key, value]];
this.numItems += 1;
return true; // "new"
}
};
getItem = (key) =>{
const idx = hashFunction(key, this.table.length);
// Code should match close to 'set'
let bucket = this.table[idx];
if (bucket) {
let pair = bucket.find(x => x[0] === key);
if (pair) {
// Bucket exists and key exists within bucket.
return pair[1];
}
}
// The result should be the same if the key doesn't exist because
// bucket is not found, or if the bucket is found and the
// key does not exist within the bucket..
return undefined;
};
}
let myHash = new HashTable
var items = [
["first", "daniel"],
["last", "esposito"],
["age", 21],
["height", 1.9]
]
// Insert multiple values:
// Check to see inserted report true/not,
// and that the numItems is increased appropriately.
for (let run of [1, 2]) {
for (let i of items) {
let [k, v] = i;
var inserted = myHash.setItem(k, v);
var found = myHash.getItem(k) === v;
console.log(`run=${run} key=${k} value=${v} inserted=${inserted} numItems=${myHash.numItems} found=${found}` )
}
}
Output:
run=1 key=first value=daniel inserted=true numItems=1 found=true
run=1 key=last value=esposito inserted=true numItems=2 found=true
run=1 key=age value=21 inserted=true numItems=3 found=true
run=1 key=height value=1.9 inserted=true numItems=4 found=true
run=2 key=first value=daniel inserted=false numItems=4 found=true
run=2 key=last value=esposito inserted=false numItems=4 found=true
run=2 key=age value=21 inserted=false numItems=4 found=true
run=2 key=height value=1.9 inserted=false numItems=4 found=true