Hashing search algorithm in JavaScript

By Tomoyuki Kashiro

What is Hashing search algorithm ?

  • generate key from value by using certain function.
  • the key is called hash.
  • if same key is generated the key is incremented.
  • you can use same function when you find and set value.

in the following example the key is generated by that function.

key = value % (length of values * 2)

Code

/***************************************
 * util
 ***************************************/
var initData = function(list){
  for(var i = 0; i < list.length; i++){
    list[i] = 0;
  }
  return list;
};

/***************************************
 * set
 ***************************************/
var setData = function(data, targets){
  var key,
      length = targets.length,
      max = targets.length-1;
  data.forEach(function(value){
    key = value % length;
    if(targets[key] === 0){
      targets[key] = value;
    }else{
      while(true){
        key++; // next to or start
        if(key === max){
          key = 0;
        }
        
        if(targets[key] === 0){
          targets[key] = value;
          break;
        }
      }
    }
  });
  return targets;
};

/***************************************
 * search
 ***************************************/
var hashSearch = function(value, list){
  var length = list.length,
      max = list.length -1,
      key = value % length,
      target;
  
  while(true){
    target = list[key];
    if(target === value){
      break;
    }
    if(key === max){
      key = 0;
    }else{
      key++;
    }
  }
  return key;
};

/***************************************
 * main
 ***************************************/
var rawData = [12,25,36,20,30,8,41],
    data = new Array(rawData.length * 2), // prepare * 1.5 - 2 length
    target = 36,
    result;

data = initData(data);
data = setData(rawData, data); // [0, 0, 30, 0, 0, 0, 20, 0, 36, 8, 0, 25, 12, 41] 

result = hashSearch(target, data);
console.log('index of tartget(' + target + ') is ' + result);

Test

/***************************************
 * util
 ***************************************/
var initData = function(list){
  for(var i = 0; i < list.length; i++){
    list[i] = 0;
  }
  return list;
};

/***

  • set
    ***/
    var setData = function(data, targets){
    var key,
    length = targets.length,
    max = targets.length-1;
    data.forEach(function(value){
    key = value % length;
    if(targets[key] === 0){
    targets[key] = value;
    }else{
    while(true){
    key++; // next to or start
    if(key === max){
    key = 0;
    }

    if(targets[key] === 0){
      targets[key] = value;
      break;
    }

    }
    }
    });
    return targets;
    };

/***

  • search
    ***/
    var hashSearch = function(value, list){
    var length = list.length,
    max = list.length -1,
    key = value % length,
    target;

while(true){
target = list[key];
if(target === value){
break;
}
if(key === max){
key = 0;
}else{
key++;
}
}
return key;
};

/***

  • main
    ***/
    var rawData = [12,25,36,20,30,8,41],
    data = new Array(rawData.length * 2), // prepare * 1.5 - 2 length
    target = 36,
    result;

data = initData(data);
data = setData(rawData, data); // [0, 0, 30, 0, 0, 0, 20, 0, 36, 8, 0, 25, 12, 41]

result = hashSearch(target, data);
console.log(’index of tartget(’ + target + ’) is ’ + result);

https://codepen.io/Tkashiro/embed/xbxjeQ/?height=300&theme-id=9575&default-tab=result&embed-version=2