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