Hash Tables

Hash tables is a data structure in which every value is associated with a key and we can find that key using hash function.

⚠️ Read more about the basics of Hashing and Hash tables. Click here

❗️All the code snippets you will see below are just Pseudo code.

Lets’ begin!!

Core

⚜️ The list

1. Put

2. Remove

3. Search

4. Size

5. IsEmpty

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

❗️The technique which I am using to find out size is very time consuming. This is one way but the better one will be to use a counter for size. Just increment that counter whenever we put an item in Hash table and decrement it when we delete an item. Just return that counter in the size function so that we do not have to iterate over whole Hash Table very time we call it ( Some geek pointed this on reddit thread… thank you) and in next post I will implement this.

Then why are you still using it here ? I am still using this because you can use this piece of code for a lot of other things i.e you can use this to traverse over whole Hash Table and implement a function ( may be by some reason you want every value to be in a lowercase or uppercase) over each item which will help you do a lot of other things when you are practicing this. So, this code is just to show that this is one way to do this but as I mentioned that this is not one of the best way to this sort of work. Use pointers instead.

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 —

In the example above, I am using a very simple Hash Function which is —

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
}

⚠️ In the function above, I am using a prime number. I know a lot of you are scratching their heads that why I used this. Well, it is playing a great role here.

There are a lot of ways you can design your own Hash Functions but no matter how complex you make you Hash Function but there is always high possibility that they will face one issue and that is —

🤜 Hash Table Collisions 🤛

…means when Hash Function returns same hash for more than one values.

There are various solutions to this problem —

• Open Addressing 🔹 Linear Probing 🔹 Quadratic Probing 🔹 Double Hashing
• Separate Chaining, etc…

but in this post, we will go through one of major of them — Separate chaining.

Hash Tables — Separate Chaining Method

In this method, the hash table will contain links to linked-lists and we will search and insert the item by iterating over these linked-lists.

Core

⚜️ The list

1. Put

2. Remove

3. Contains

4. Size

5. IsEmpty

6. Traverse

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.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.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i];
      while( current ) {
        fn( current );
        current = current.next;
      }
    }
  }
}

Practice

• LeetCode — Hash Tables
• GeekForGeeks — Hashing Data Structures
• HackerEarth — Hash Tables