1
\$\begingroup\$

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) );
}

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Blindman67 Oct 7 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.