DS with JS — Hash Tables— I

Data Structures with JavaScript — Chapter Four — Hash tables — I

Gaurav Mehla
Apr 21, 2018 · 6 min read

Prerequisites

Lets’ begin!!

Core

⚜️ The list

Initial Hash table

🔅 Put

put( item ) {
  let key = this.computeHash( item )
  return !this.table[key] ? this.table[key] = item : false;
}
Put Operation

🔅 Remove

remove( item ) {
  let key = this.computeHash( item )
  return this.table[key] = undefined
}
Remove Operation

🔅 Search & Size

search( item ) {
  let key = this.computeHash( item )
  return this.table[key] === item
}size() {
  let counter = 0;
  for( let i=0, len = this.table.length; i < len; i++) {
   if( this.table[i] ) { counter++ }
  }
  return counter;
}
Search & Size Operation

🔅 IsEmpty

isEmpty() {
  for( let i=0, len = this.table.length; i < len; i++) {
   if( this.table[i] ) { return false };
  }
  return true
}
IsEmpty Operation

It’s just the beginning with hash tables…

Let us see the real issue with Hash Functions —

computeHash( string ) {
  let H = this.findPrime( this.table.length )
  let total = 0;
  for (let i = 0; i < string.length; ++i) {
    total += H * total + string.charCodeAt(i)
  }
  return total % this.table.length
}

Hash Tables — Separate Chaining Method

Core

⚜️ The list

Lets write some lines of code now.. 🤓

Hash Table before all operations

🔅 Put

put( item ) {
   let key = this.computeHash( item )
   let node = new Node(item)
   if ( this.table[key] ) {
     node.next = this.table[key]
   }
   this.table[key] = node
}
Put Operation

🔅 Remove

remove( item ) {
  let key = this.computeHash( item )
  if( this.table[key] ) {
     if( this.table[key].data === item ) {
        this.table[key] = this.table[key].next
     } else {
       let current = this.table[key].next
       let prev = this.table[key]
       while( current ) {
         if( current.data === item ) {
           prev.next = current.next
         }
         prev = current
         current = current.next
       }
     }
  }
}
Deletion in Separate Chaining Method — algs4.cs.princeton.edu
Remove Operation

🔅 Contains

contains( item ) {
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i];
      while( current ) {
        if( current.data === item ) {
          return true;
        }
        current = current.next;
      }
    }
  }
  return false;
}
Contains Opeartion

🔅 Size & IsEmpty

size( item ) {
  let counter = 0
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i]
      while( current ) {
        counter++
        current = current.next
      }
    }
  }
  return counter
}isEmpty() {
  return this.size() < 1
}
Size & IsEmpty Operation

🔅 Traverse

traverse( fn ) {
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i];
      while( current ) {
        fn( current );
        current = current.next;
      }
    }
  }
}
Traverse Operation

Practice

Last most important thing..

That’s It

About this post

Happy Coding !!


_devblogs

Stories for Full-Stack Web developers which help them in pursuing their goals as a developer, mastering the modern web technologies and *hacking the web.

Gaurav Mehla

Written by

Software engineer & Web hacker. Spent 30+% of life on playing with JS

_devblogs

_devblogs

Stories for Full-Stack Web developers which help them in pursuing their goals as a developer, mastering the modern web technologies and *hacking the web.