hashtable search in JavaScript

Question

I've implemented the search/insert part of a hashtable in JavaScript. This is in linear probing style. It resizes when the array is out of space.

var share = { bucketSize: 10 };
function hash(key){
 return key % share.bucketSize;
}
function expandArr(arr){
 share.bucketSize = share.bucketSize * 2;
 let newArr = [];
 for(let i=0; i<arr.length; i++){
 let item = arr[i];
 let key = item.key;
 hashInsert(key, item, newArr);
 }
 arr = newArr;
}
function hashInsert(key, data, arr){
 let bucketKey = hash(key);
 let hasReset = false;
 let pointer = bucketKey;
 while(true){
 if(pointer >= share.bucketSize){ // bound check
 pointer = 0;
 hasReset = true;
 }
 if(pointer === bucketKey && hasReset){ // all full
 expandArr(arr);
 bucketKey = hash(key);
 pointer = bucketKey;
 hasReset = false;
 }
 if(arr[pointer] === undefined){ // found space
 arr[pointer] = { key: key, data: data };
 break;
 }
 pointer++;
 }
}
function hashSearch(key, arr){
 let bucketKey = hash(key);
 let hasReset = false;
 let pointer = bucketKey;
 while(true){
 if(pointer === bucketKey && hasReset){ // complete cycle
 return undefined;
 }
 if(pointer >= share.bucketSize){ // bound check
 pointer = 0;
 hasReset = true;
 }
 let curr = arr[pointer];
 if(curr === undefined){ // not found
 return undefined;
 }
 if(curr.key === key){ // found it
 return curr;
 }
 pointer++;
 }
}
var arr = [];
for(var i=0; i<100; i++){
 hashInsert(i, 'data ' + i, arr);
 console.log( hashSearch(i, arr) );
}

Answer 1

Looks good. I'm not sure what feedback you are looking for, but here's a little:

• use const where you can, instead of let
• the naming is a little confusing at times, hash vs. key. Maybe if you call the hash function calcHash then you can call the value it returns a hash and not have to call it a bucketKey... or maybe the function should be calcBucketKey.
• it seems like the scoping of arr may be off... especially in expandArr. I believe the argument is going to override the global definition, so I don't think that the last line that re-assigns arr is going to change the global, but rather a local variable going out of scope.
• consider using the modulo operator to loop around the array. It can save some checks against the array size.

• Blindman67: Your point 3 is correct. arr is an argument of the function expandArr and thus is scoped to that function. The last line of that function arr = newArr; is redundant. Point 4, referring to %. It is called the "remainder operator" developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… not (modulo or sometimes modulus) operator. The behaviours are distinct in that -3 % 4 === -3 while -3 mod 4 == 1 (Note mod is not a JS operator) It is unfortunate that % has been called modulo in many languages.