Hashing search algorithm in JavaScript
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
/***************************************
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);