DEV Community

Cover image for Data Structures: Hash Tables II
Michael N.
Michael N.

Posted on • Originally published at m13ha.hashnode.dev

Data Structures: Hash Tables II

This is part 2 of a two-part article on hash tables. In the first part of this article we looked at what hash tables are, how they work, and the various parts of a hash table. In this part, we will implement a hash table in Javascript, so let's begin.

this-is-where-the-fun-begins-star-wars.gif

Our hash table is going to have 4 main methods and we are going to be using separate chaining to handle collisions. We will use Map objects in the buckets/slots to store the data (keys and values). The four main methods of our hash table are:

  • Put: Add a key and value to the table.

  • Get: Find and return the value of a key.

  • Remove: Delete a key and value from the table.

  • IsPresent: Check if a key is present in the table.

Hash Function

Before we start building our hash table, we need to first make our hash function.


const hashFunc = (key, size) => {
  let hash = 0;

  for (let i = 0; i < key.length; i++) {
     hash += key.charCodeAt(i)
  }

  return hash % size
}

Enter fullscreen mode Exit fullscreen mode

The hash function takes in 2 parameters, the key and the size of the table. Each character in the key is converted to UTF-16 code using the charCodeAT string method and added up, the resulting value is modded(%) by the size of the table, it is recommended that the size be a prime number to reduce the chances of collision. The value we get from the equation is returned and will be used in storing and retrieving data in other functions.

Hash Table


class HashTable {
  constructor(){
    this.size = 97,
    this.table = Array(this.size)
  }
}

Enter fullscreen mode Exit fullscreen mode

The class constructor has only 2 properties, the size of the table (97) and the array itself, hash tables use static arrays to store the data. The size of a static array is set when it is created and will not change unless explicitly changed, unlike dynamic arrays that change with an increase in the data inside them.

Put Method


  put(key, data){
    let hashCode = hashFunc(key, this.size)

    if(!this.table[hashCode]){
      this.table[hashCode] = new Map();
      this.table[hashCode].set(key, data);
    }else {
      this.table[hashCode].set(key, data)
    }
  }

Enter fullscreen mode Exit fullscreen mode

The first method of our hash table is the put method, as the name implies, it puts data into the table; it takes 2 parameters the key and the data. Let's break down how it works.

Method Break-Down

  • Get the hash code from the hashFunc by passing it the key and the table size property.
  • Check if that bucket is occupied; if it is not occupied create a new map object and set the data in it.
  • If that table is occupied then just insert the data into the map object that we know will be there.

Get Method


  get(key){
    let hashCode = hashFunc(key, this.size)

    if(this.table[hashCode]){
      return this.table[hashCode].get(key)
    }else {
      return "no such data"
    }
  }

Enter fullscreen mode Exit fullscreen mode

The get method takes a key and returns the data that is paired with that key in the table.

Method Break-Down

  • First, get the hash code from hashFunc.

  • Check if there is data in that position of the table; if yes, get the value of the key from the map object and return it.

  • If that position in the table is empty, let the user know the data doesn't exist.

Remove Method

  remove(key){
    let hashCode = hashFunc(key, this.size)

    if(this.table[hashCode]){
      let data = this.table[hashCode].get(key);
      this.table[hashCode].delete(key)
      return data
    }else {
      return "no such data"
    }
  }
Enter fullscreen mode Exit fullscreen mode

This method deletes data from a table.

Method Break-Down

  • First, get the hash code from hashFunc.

  • Check if there is data in that position of the table; if yes, get the value of the key from the map object and store it in a variable; delete the key and value from the map object, and return the variable.

  • If that position in the table is empty, let the user know the data doesn't exist.

IsPresent Method

 isPresent(key){
    let hashCode = hashFunc(key, this.size)

    if(this.table[hashCode]){
      return this.table[hashCode].has(key);
    }
  }

Enter fullscreen mode Exit fullscreen mode

This is a simple method to determine if a key already exists in the table.

Method Break-Down

  • First, get the hash code from hashFunc.

  • Check if there is data in that position of the table; if yes, check if the map object there has any keys that match the given key and return the result.

Complete Code


const hashFunc = (key, size) => {
  let hashCode = 0; 
  for (let i = 0; i < key.length; i++) {
     hashCode += key.charCodeAt(i)
  } 
  return hashCode % size
}


class HashTable {
  constructor(){
    this.size = 97,
    this.table = Array(this.size)
  }

  put(key, data){
    let hashCode = hashFunc(key, this.size)

    if(!this.table[hashCode]){
      this.table[hashCode] = new Map();
      this.table[hashCode].set(key, data);
    }else {
      this.table[hashCode].set(key, data)
    }
  }

  get(key){
    let hashCode = hashFunc(key, this.size)

    if(this.table[hashCode]){
      return this.table[hashCode].get(key)
    }else {
      return "no such data"
    }
  }

  remove(key){
    let hashCode = hashFunc(key, this.size)

    if(this.table[hashCode]){
      let data = this.table[hashCode].get(key);
      this.table[hashCode].delete(key)
      return data
    }else {
      return "no such data"
    }
  }

  isPresent(key){
    let hashCode = hashFunc(key, this.size)

    if(this.table[hashCode]){
      return this.table[hashCode].has(key);
    }
  }
}

Enter fullscreen mode Exit fullscreen mode

Conclusion

This brings us to the end of this article on Hash Tables and this series on data structures. I learned a lot from writing these articles and it has helped me better understand and internalize certain concepts about programming and what it means to be a developer. My next series will be on algorithms where ill cover topics such as recursion, time complexity, space complexity, sorting etc; I hope you'll give them a read. The code for this article can be found here. Thank you for making it this far and see you soon.

see-you-later-seal-you-later.gif

Top comments (0)