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