Hash Table implementation using javascript

Question

I am trying to implement a hash table using javascript. At the moment, everything is working so far, but I am having trouble with my get method to retrieve a value in the hash table given a specific key. I am using linear probing in order to avoid collisions. When I hash the key "Alejandro" I map the key to the 0 index. Then I add it into my hash table. Then I try "Rosalby" which also maps to 0 index. I used linear probing to find the next available slot, in my case the empty index is 1 and I put Rosalby's value in that slot. So far it seems that I am managing my collision well. However; when I try to get the values in my get method, I am unable to get the right values here is what my hash table looks like.

Also, I would like to mention that I have made my hash table bigger in size and I get the right value given specific key, simply because I do not have collision. Thank you in advance.

// Hash table implementation
class HashTable {
 // constructor functio
 constructor(size) {
 this.size = size;
 this.buckets = this.initArray(size);
 this.limit = 0;
 }
 // init array function
 initArray(size) {
 // init an array
 const array = [];
 // populate the array base on the size
 for (let i = 0; i < size; i++) {
 // push null to the array
 array.push(null);
 }
 // return the array
 return array;
 }
 // mapping key to index
 hash(key) {
 let total = 0;
 // get unique code of character in the string
 for (let i = 0; i < key.length; i++) {
 let keyCode = key.charCodeAt(i)
 // console.log("Key code:", keyCode)
 // sum up the unique code
 total += keyCode;
 // console.log(total); 
 }
 // mod the total to the size of the hash table
 const hashIndex = total % this.size;
 // return that index
 return hashIndex;
 }
 // put method
 put(key, value) {
 // throw an erro if hashTable is full
 if (this.limit >= this.size) throw "Hash Table is full";
 // hash the key
 let hashIndex = this.hash(key);
 // console.log(hashIndex);
 // linear probing
 while (this.buckets[hashIndex] != null) {
 hashIndex++;
 hashIndex = hashIndex % this.size;
 }
 // add the value at that key to the buckets array
 this.buckets[hashIndex] = value;
 // increase the limit
 this.limit++;
 }
 // get method
 get(key) {
 // hash the key
 let hashIndex = this.hash(key);
 let value = this.buckets[hashIndex];
 // return the value at that index
 return value;
 }
} // end of hash table
// sanity check
const ht = new HashTable(3);
console.log(ht);
// ht.hash("Rosalby");
console.log();
ht.put("Alejandro", "555-5555");
ht.put("Rosalby", "123-1231");
ht.put("Lalaland", "000-0000");
// ht.put("Lalaland", "919-1919");
console.log();
console.log(ht);
console.log("Alejandro:", ht.get("Alejandro"), "Rosalby:", ht.get("Rosalby"), "Lalaland:", ht.get("Lalaland"));

Hash Table console logs

Answer 1

Here is a quick working implementation of a hash table:

class HashTable
{
 constructor(getHash)
 {
 if(!getHash) throw "Argument is null: getHash";
 
 this.getHash = getHash;
 this.buckets = {};
 this._count = 0;
 }
 
 // throws an exception if the key already exists
 add(key, value)
 {
 const hashCode = this.getHash(key);
 const bucket = this.buckets[hashCode];
 if(!bucket)
 {
 this.buckets[hashCode] = [{key, value}];
 ++this._count;
 return;
 }
 for(let length = bucket.length, i = 0; i < length; ++i)
 {
 const item = bucket[i];
 if(item.key == key) throw "Duplicate key.";
 }
 bucket.push({key, value});
 ++this._count;
 }
 
 // replaces the value if the key already exists
 set(key, value)
 {
 const hashCode = this.getHash(key);
 const bucket = this.buckets[hashCode];
 if(!bucket)
 {
 this.buckets[hashCode] = [{key, value}];
 ++this._count;
 return;
 }
 for(let length = bucket.length, i = 0; i < length; ++i)
 {
 const item = bucket[i];
 if(item.key == key) 
 {
 item.value = value;
 return;
 }
 }
 bucket.push({key, value});
 ++this._count;
 }
 get(key, defaultValue)
 {
 const hashCode = this.getHash(key);
 const bucket = this.buckets[hashCode];
 if(!bucket) return defaultValue;
 for(let length = bucket.length, i = 0; i < length; ++i)
 {
 const item = bucket[i];
 if(item.key == key) return item.value;
 }
 return defaultValue;
 }
 has(key)
 {
 const hashCode = this.getHash(key);
 const bucket = this.buckets[hashCode];
 if(!bucket) return false;
 for(let length = bucket.length, i = 0; i < length; ++i)
 {
 const item = bucket[i];
 if(item.key == key) return true;
 }
 return false;
 }
 
 get count()
 {
 return this._count;
 }
}
HashTable.unitTests = function()
{
 function getHash(value)
 {
 const stringValue = String(value);
 let result = 0;
 for(let length = stringValue.length, i = 0; i < length; ++i) result ^= stringValue.charCodeAt(i);
 return result;
 }
 
 let ht;
 
 // empty
 ht = new HashTable(getHash);
 if (ht.count != 0) throw "failed";
 if (ht.has(null)) throw "failed";
 if (ht.has("")) throw "failed";
 if (ht.get(null) != void (0)) throw "failed";
 if (ht.get("") != void (0)) throw "failed";
 if (ht.get(null, 1) != 1) throw "failed";
 // add new
 ht = new HashTable(getHash);
 ht.add("a", 1);
 if (ht.count != 1) throw "failed";
 if (!ht.has("a")) throw "failed";
 if (ht.get("a") != 1) throw "failed";
 // set new
 ht = new HashTable(getHash);
 ht.set("a", 1);
 if (ht.count != 1) throw "failed";
 if (!ht.has("a")) throw "failed";
 if (ht.get("a") != 1) throw "failed";
 // add duplicate
 ht = new HashTable(getHash);
 ht.add("a", 1);
 try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }
 // add+set duplicate
 ht = new HashTable(getHash);
 ht.add("a", 1);
 ht.set("a", 1);
 if (ht.count != 1) throw "failed";
 if (!ht.has("a")) throw "failed";
 if (ht.get("a") != 1) throw "failed";
 // set+add duplicate
 ht = new HashTable(getHash);
 ht.set("a", 1);
 try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }
 // set duplicate
 ht = new HashTable(getHash);
 ht.set("a", 1);
 ht.set("a", 1);
 if (ht.count != 1) throw "failed";
 if (!ht.has("a")) throw "failed";
 if (ht.get("a") != 1) throw "failed";
 // add multiple
 ht = new HashTable(getHash);
 ht.add("a", 1);
 ht.add("b", 2);
 if (ht.count != 2) throw "failed";
 if (!ht.has("a")) throw "failed";
 if (!ht.has("b")) throw "failed";
 if (ht.get("a") != 1) throw "failed";
 if (ht.get("b") != 2) throw "failed";
 // add with collision
 ht = new HashTable(getHash);
 ht.add("ab", 1); // hash code 3
 ht.add("ba", 2); // hash code 3
 if (ht.count != 2) throw "failed";
 if (!ht.has("ab")) throw "failed";
 if (!ht.has("ba")) throw "failed";
 if (ht.get("ab") != 1) throw "failed";
 if (ht.get("ba") != 2) throw "failed";
 // set with collision
 ht = new HashTable(getHash);
 ht.set("ab", 1); // hash code 3
 ht.set("ba", 2); // hash code 3
 if (ht.count != 2) throw "failed";
 if (!ht.has("ab")) throw "failed";
 if (!ht.has("ba")) throw "failed";
 if (ht.get("ab") != 1) throw "failed";
 if (ht.get("ba") != 2) throw "failed";
}
HashTable.unitTests();
console.log("OK");

<html>
<head>
<script src="HashTable.js"></script>
</head>
<body>
</body>
</html>

Some clarifications:

• The hashing function is intentionally provided as a configuration for the hash table; makes the class more reusable;
• Using this._count is a better way to enforce capacity limit (not implemented, easy to add, though);
• The unit tests could be extended a bit more. What we have here is, though, sufficient to show that the HashTable class is operational;
• The ^ operator (bitwise XOR) usually provides a better distribution of the generated hash codes. See Why are XOR often used in java hashCode() but another bitwise operators are used rarely?.

• Alejandro E Rodriguez: Thank you so much Daniel, really went above and beyond answering my question. The clarifications helped me understand the parts I did not understand from your solution. Again, thank you so much!

Answer 2

class HashTable {
 constructor(size){
 this.data = new Array(size);
 // this.data = [];
 }
 _hash(key) {
 let hash = 0;
 for (let i =0; i < key.length; i++){
 hash = (hash + key.charCodeAt(i) * i) % this.data.length
 }
 return hash;
 }
 set(key, value) {
 let address = this._hash(key);
 if (!this.data[address]) {
 this.data[address] = [];
 }
 this.data[address].push([key, value]);
 return this.data;
 }
 get(key){
 const address = this._hash(key);
 const currentBucket = this.data[address]
 if (currentBucket) {
 for(let i = 0; i < currentBucket.length; i++){
 if(currentBucket[i][0] === key) {
 return currentBucket[i][1]
 }
 }
 }
 return undefined;
 }
 
 keys(){
 const keysArray = [];
 console.log(this.data.length);
 for (let i = 0; i < this.data.length; i++){
 if(this.data[i]){
 keysArray.push(this.data[i][0][0])
 }
 }
 return keysArray;
 }
}
const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')
myHashTable.keys()

• Alejandro E Rodriguez: Nice, thank you. Question what does the underscore character ( _variableName ) in front of the variable means?