|
/* |
|
* HashTable DC-Class |
|
* |
|
* Implementation of Hash Table (https://en.wikipedia.org/wiki/Hash_table) in JavaScritpt. |
|
* So, it is generate keys+values storage, whitch is splitted into buckets or slots: |
|
* storage= [[["keyI","valueI"],["keyI","valueI"],...],[],[["keyI","valueI"]],...] |
|
* |
|
* params (def): |
|
* - storageLimit(number)= no. of slots |
|
* - hashFunction(function)= if defined, is used to generate slots ids in storage |
|
* - debug(bool)= if true, shows debugging method "print" |
|
* methods: |
|
* .setItem= function(key, value) |
|
* .getItem= function(key) |
|
* .removeItem= function(key) |
|
* .exists= function(key) |
|
* |
|
* .entries= function() |
|
* .keys= function() |
|
* .values= function() |
|
* |
|
* .size= function() |
|
* .size= function() |
|
* .clear= function() |
|
* |
|
* (.var_dump= function()) |
|
* (.print= function()) |
|
* * */ |
|
function Classes_HashTable(def= {}){ |
|
const {storageLimit= 5, hashFunction= _hash, debug= false} = def; |
|
let _this= {}; let _storage= []; |
|
const external_hashFunction= typeof hashFunction === "function"; |
|
/* Hash id generation - if hashFunction is undefined */ |
|
function _hash(string){ |
|
let hash= 0; |
|
for(let i=0, i_length= string.length; i<i_length; i++){ |
|
hash+= string.charCodeAt(i); |
|
} |
|
return hash % storageLimit; |
|
} |
|
function getIndices(key){ |
|
const index= hashFunction(key); |
|
if(_storage[index]===undefined) return [-1,-1, index]; //no slot |
|
for(let i=0, i_length= _storage[index].length; i<i_length; i++){ |
|
if(_storage[index][i][0] === key){ |
|
return [index, i]; |
|
break; |
|
} |
|
} |
|
return [index, -1]; |
|
}; |
|
/* Print for debugging */ |
|
if(debug){ |
|
_this.print= function(){ |
|
let print= ""; |
|
for(let i=0, i_length= _storage.length; i<i_length; i++){ |
|
if(i) print+=","; |
|
if(_storage[i]!==undefined){ |
|
print+="["; |
|
for(let j=0, j_length= _storage[i].length; j<j_length; j++){ |
|
if(j) print+=","; |
|
print+="["+_storage[i][j].toString()+"]"; |
|
} |
|
print+="]"; |
|
} else { |
|
print+="[]"; |
|
} |
|
} |
|
console.log(print);; |
|
}; |
|
_this.var_dump= function(){console.log(_storage);} |
|
} |
|
/* Check if key exists */ |
|
_this.exists= function(key){ |
|
const indices= getIndices(key); |
|
return indices[0]===-1 || indices[1]===-1 ? false : true; |
|
}; |
|
/* Add into storage */ |
|
_this.setItem= function(key, value){ |
|
const indices= getIndices(key); |
|
if(indices[0]===-1) _storage[indices[2]]= [[key, value]]; |
|
else if(indices[1]===-1) _storage[indices[0]].push([key, value]); |
|
else _storage[indices[0]][indices[1]][1]= value; |
|
}; |
|
/* Get value from storage */ |
|
_this.getItem= function(key){ |
|
const indices= getIndices(key); |
|
if(indices[0]===-1 || indices[1]===-1) return undefined; |
|
else return _storage[indices[0]][indices[1]][1]; |
|
}; |
|
/* Remove from storage */ |
|
_this.removeItem= function(key){ |
|
const indices= getIndices(key); |
|
let _storage_length= 0; |
|
if(indices[0]!==-1 && indices[1]!==-1){ |
|
_storage_slot_length= _storage[indices[0]].length; |
|
if(_storage_slot_length===1&&_storage[indices[0]][0][0]===key){ |
|
delete _storage[indices[0]]; |
|
} else { |
|
for(let i=0; i<_storage_slot_length; i++){ |
|
if(_storage[indices[0]][i][0]===key){ |
|
delete _storage[indices[0]][i]; |
|
} |
|
} |
|
} |
|
} |
|
}; |
|
_this.keys= function(){ |
|
let keys= []; |
|
for(let i=0, i_length= _storage.length; i<i_length; i++){ |
|
if(_storage[i]!==undefined){ |
|
for(let j=0, j_length= _storage[i].length; j<j_length; j++){ |
|
keys[keys.length]= _storage[i][j][0]; |
|
} |
|
} |
|
} |
|
return keys; |
|
}; |
|
_this.values= function(){ |
|
let values= []; |
|
for(let i=0, i_length= _storage.length; i<i_length; i++){ |
|
if(_storage[i]!==undefined){ |
|
for(let j=0, j_length= _storage[i].length; j<j_length; j++){ |
|
values[values.length]= _storage[i][j][1]; |
|
} |
|
} |
|
} |
|
return values; |
|
}; |
|
_this.entries= function(){ |
|
let entries= []; |
|
for(let i=0, i_length= _storage.length; i<i_length; i++){ |
|
if(_storage[i]!==undefined){ |
|
for(let j=0, j_length= _storage[i].length; j<j_length; j++){ |
|
entries[entries.length]= _storage[i][j]; |
|
} |
|
} |
|
} |
|
return entries; |
|
}; |
|
/* Clear storage */ |
|
_this.clear= function(){ |
|
_storage= []; |
|
}; |
|
_this.size= function(){ |
|
let counter= 0; |
|
for(let i=0, i_length= _storage.length; i<i_length; i++){ |
|
if(_storage[i]!==undefined){ |
|
for(let j=0, j_length= _storage[i].length; j<j_length; j++){ |
|
counter++; |
|
} |
|
} |
|
} |
|
return counter; |
|
}; |
|
return Object.freeze(_this); |
|
} |
|
/* |
|
* Examples |
|
* * */ |
|
let ht= Classes_HashTable({debug: true, storageLimit: 10}); |
|
ht.setItem('Aaa', 'aaa'); |
|
ht.setItem('Fff', 'fff'); |
|
ht.setItem('Rrr', 'rrr'); |
|
ht.setItem('Kkk', 'kkk'); |
|
console.log(ht.getItem('Kkk')); |
|
console.log(ht.getItem('kkk')) |
|
ht.print();//= [[Rrr,rrr]],[],[],[],[[Fff,fff]],[],[],[],[],[[Aaa,aaa],[Kkk,kkk]] |