Hashing search algorithm in JavaScript

November 15, 2014

Reading time ~3 minutes

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

See the Pen hashing search algorithm in JavaScript by Tomoyuki kashiro (@Tkashiro) on CodePen.

add ticket number to git commit automatically

Most of ticket tracker like Github, pivotal tracker have function to connect your commit to ticket(story).But every time when you commit ...… Continue reading

I will build frontend and backend separately

Published on September 28, 2016

order of angular controller's initialisation

Published on October 05, 2015