Hashtables - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki

Hashtables

• https://reactgo.com/hashtable-javascript/

How Work?

• A hash table is a data structure which helps us to quickly find the data by using the keys. Hashtable uses the hash function to generate the indexes sometimes hash function generates the same index for the different data this is called collision.

• Fun fact - we will use an array because we can't use an object - we are literally implementing an object

• If the collision occurs there are different ways to resolve the collisions.

  • Linear Probing
  • Separate Chaining
  • coalesced chaining
  • double hashing
  • quadratic probing
  • For this example - separate chaining is used

Skeleton Code

class HashTable{
  // default bucket size 42
  constructor(size=42){
    this.buckets =  new Array(size)
    this.size = size
  }

}


hash(key){
       return key.toString().length % this.size;
   }

Methods

Set

• Create a new method called set which accepts two arguments key and value.
• Hash the key by using a hash function.
• push the key-value pairs into that bucket

set(key,value){

    let index = this.hash(key);

    if(!this.buckets[index]){
      this.buckets[index] = [ ];
    }

    this.buckets[index].push([key,value])

    return index

  }

Get

• It helps us to get the data by using the key.
• Create a new method called get which accepts one argument key.
• Hash the key and get the index of that bucket.
• if there is no bucket in that index return null
• for of loop and return value

 get(key){

     // index of the bucket
    let index = this.hash(key);

     // if there is no bucket
     if(!this.buckets[index])return null

        for(let bucket of this.buckets[index]){
          // if key  matches
          if(bucket [0] === key){
            // value
            return bucket [1]
           }
        }
  }

Time Complexity

• Insertion - O(1)
• Searching - O(1)
• Deletion - O(1)