Implement HashTable
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
//IMPLEMENT HASHTABLE
class HashTable {
constructor(size){
this.data = new Array(size);
}
_hash(key) {
let hash = 0;
for (let i =0; i < key.length; i++){
hash = (hash + key.charCodeAt(i) * i) % this.data.length
}
return hash;
}
set(key,value){
if(!key || !value) return []
let index = this._hash(key);
this.data[index] = [key,value]
return this.data[index]
}
get(key){
if(!key) return 'no value found with this key'
let index = this._hash(key);
if(this.data[index]){
let val = this.data[index][1]
return val
}
return 'nothing found'
}
keys(){
let keys = [];
for(let i=0; i<this.data.length ; i++){
if(this.data[i]){
keys.push(this.data[i][0])
}
}
return keys
}
}
// WITH THIS WE ARE ONLY ABLE TO PASS STRING VALUE IN KEY NOT ANY OTHER VALUES LIKE INT , OBJ OR ANYTHING ELSE
const myHashTable = new HashTable(50);
// myHashTable.set('grapes', 10000)
// console.log(myHashTable.get('grapes'))
// myHashTable.set('apples', 9)
// console.log(myHashTable.get('apples'))
// myHashTable.set("1",4)
// console.log(myHashTable.get("1"))
// console.log(myHashTable.keys())
// Also above example is done by self this is not improved version because we have missed collision scenario in this like what if multiple items
// get same index this case need to be improved so for tommorow create this three method : get(key) , set(key,value) , keys() all in improved version
// which take care all scenarion including collision.
// Implement solution with collision situation.
class HashTableWithCollision {
constructor(size){
this.data = new Array(size);
}
_hash(key) {
let hash = 0;
for (let i =0; i < key.length; i++){
hash = (hash + key.charCodeAt(i) * i) % this.data.length
}
return hash;
}
set(key,value){
if(!key || !value) return
let index = this._hash(key)
if(!this.data[index]){
this.data[index] =[]
}
this.data[index].push([key,value])
}
get(key){
if(!key) return
let index = this._hash(key)
if(this.data[index]){
for(let i=0; i<this.data[index].length;i++){
if(this.data[index][i][0] === key){
return this.data[index][i][1]
}
}
}
}
//INCREDIBAL JOB HERE IT ALSO SOLVE COLLISION PROBLEM HERE
keys(){
let keys = [];
for(let i = 0 ; i < this.data.length; i++){
if(this.data[i] && this.data[i].length > 1){
for(let j =0 ; j<this.data[i].length;j++){
keys.push(this.data[i][j][0])
}
}else if(this.data[i]){
console.log(this.data[i][0][0])
keys.push(this.data[i][0][0])
}
}
return keys;
}
}
const hashWithCollision = new HashTableWithCollision(1);
hashWithCollision.set('grapes', 10000)
console.log(hashWithCollision.get('grapes'))
hashWithCollision.set('apples', 9)
hashWithCollision.set('ta', 9888)
hashWithCollision.set('tad', 9888)
hashWithCollision.set('taddd', 9888)
hashWithCollision.set('taddd', 9888)
hashWithCollision.set('addrad', 9888)
hashWithCollision.set('tadddd', 9888)
hashWithCollision.set('applesasd', 9888)
console.log(hashWithCollision.get('apples'))
console.log(hashWithCollision.get('applesasd'))
console.log(hashWithCollision.keys())
// ARRAYS AND HASHTABLE COMPARE
// 1. Search operation : In array search operarion is O(n) because if we want to access specific element into array then we need to loop through the
// items.In case of hashtable its O(1) just provide the key that you are trying to get value and it will return value all magic
// happening in hash function.
// 2. Insert : ln array insert value at specific index is O(n) operation where in case of hashtable its O(1) because we even don't know where value is
// going to get stored any at the time of access we just provide key to access that value.
// 3. Lookup : in both data structure lookups are O(1) : example array[index] will return value of that index as its ordered and hashatable.grapes will
// return value of key grapes whiout looking into any other thing.
// 4. Delete : In array delete opration is O(n) as we need to shift other items into that index and in case of hashtable its again O(1).
// NOTE : IN ABOVE ALL CASES FOR HASHTABLE WE ARE NOT CONSIDERING CASE OF COLISION.
JavaScript
INFO