DEV Community

Cover image for Data Structures in JavaScript [Hash Tables]
Youssef Zidan
Youssef Zidan

Posted on • Edited on

Data Structures in JavaScript [Hash Tables]

What is a Hash Tables?

Hash Tables, Hashes, Maps, Unordered Maps or Objects, There are many names to call This Data Structure.

In JavaScript, Objects are a type of a Hash Table

Hash Tables don't maintain order, like Arrays.

Why Hash Tables?

Imagine that we want to store the number of active Users in a particular app.

Doing this in Arrays is not the cleanest way.
So we need Hash Tables or Objects to do so

const users = {
  activeUsers: 1000,
};
Enter fullscreen mode Exit fullscreen mode

How Hash Tables Work?

In Hash Tables we use keys and values.

keys instead of indexes to find the data in memory.

To make this happen we need a Hash Function.

First, We pass the key to the Hash Function

Then, the Hash Function will generate a hashed output to store the data in the memory.

What is a Hash Function?

A function that coverts inputs of any length into a fixed size string using a mathematical equation.

The output of a hash function has to be unique.

And the same input should always produce the same hashed output.

And there are many types of Hash Functions such as MD2, CRC23, SHA-1, ... and more.

You can try it here

Example of a simple Hash Function

function hashFunction(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = hash + key.charCodeAt(i);
  }
  return hash;
}
// Giving it the string "Hello"
console.log(hashFunction("Hello")); // 500
console.log(hashFunction("Hello")); // 500
console.log(hashFunction("Hello")); // 500

// Giving it the string "hello"
console.log(hashFunction("hello")); // 532
console.log(hashFunction("hello")); // 532
console.log(hashFunction("hello")); // 532
Enter fullscreen mode Exit fullscreen mode

Hash Tables with Big O Notation 

- Access    => O(1) || O(n).
- Insert    => O(1).
- Delete    => O(1).
Enter fullscreen mode Exit fullscreen mode

Later in the article we will know why Accessing might be O(n).

Example

const user = {
  firstName: "Youssef",
  lastName: "Zidan",
};

// Access // O(1)
console.log(user.firstName); // "Youssef"

// Insert // O(1)
user.job = "Web Developer";
console.log(user.job); // "Web Developer"

// Delete O(1)
delete user.lastName;
console.log(user.lastName); // undefined
Enter fullscreen mode Exit fullscreen mode

Implementing Hash Tables

In order to really understand Big O with Hash Tables, we are going to Implement one.

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }

  // hash function
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }

  // O(1)
  set(key, value) {
    let address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = []; // O(1)
      this.data[address].push([key, value]); // O(1)
    } else {
      this.data[address].push([key, value]); // O(1)
    }
  }

  // O(1) || O(n)
  get(key) {
    let address = this._hash(key); // O(1)
    let current = this.data[address]; // O(1)
    if (current) {
      for (let i = 0; i < current.length; i++) {
        // O(n)
        // O(1) if current.length === 1
        // or the ele is found in the first index
        if (current[i][0] === key) {
          return current[i][1];
        }
      }
    } else {
      // O(1)
      return undefined;
    }
  }

  keys() {
    if (!this.data.length) {
      return undefined;
    }
    const keys = [];
    for (let i = 0; i < this.data.length; i++) {
      if (this.data[i]) {
        if (this.data[i].length === 1) {
          keys.push(this.data[i][0][0]);
        }
        if (this.data[i].length > 1) {
          for (let j = 0; j < this.data[i].length; j++) {
            keys.push(this.data[i][j][0]);
          }
        }
      }
    }
    return keys;
  }
}
Enter fullscreen mode Exit fullscreen mode

Breaking Down

hash function

_hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }
Enter fullscreen mode Exit fullscreen mode

Using this specific algorithm to determine that the created element will not exceed the length of the Hash Table.

set

  set(key, value) {
    let address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = []; // O(1)
      this.data[address].push([key, value]); // O(1)
    } else {
      this.data[address].push([key, value]); // O(1)
    }
  }
Enter fullscreen mode Exit fullscreen mode
  • Getting the address using the hash function.
  • If the generated address doesn't exist in this.data object, Create an empty array of this address.
  • Push the key and the value passed inside another array to the created empty array.
  • If there is no data in this particular address just push an array contains the key and value.

get

  get(key) {
    let address = this._hash(key); // O(1)
    let current = this.data[address]; // O(1)
    if (current) {
      for (let i = 0; i < current.length; i++) {
        // O(n) or
        // O(1) if current.length === 1
        // or the ele is found in the first index
        if (current[i][0] === key) {
          return current[i][1];
        }
      }
    } else {
      // O(1)
      return undefined;
    }
  }
Enter fullscreen mode Exit fullscreen mode
  • Getting the address using the hash function.
  • Getting the current value of the generated address.
  • Checking if there is a value in this current position.
  • Looping through the current array.
  • Check for they key current[i][0] if it's equal the passed key and return the value current[i][1].
  • Return undefined if there is no current address found.

keys

  keys() {
    if (!this.data.length) {
      return undefined;
    }
    const keys = [];
    for (let i = 0; i < this.data.length; i++) {
      if (this.data[i]) {
        if (this.data[i].length === 1) {
          keys.push(this.data[i][0][0]);
        }
        if (this.data[i].length > 1) {
          for (let j = 0; j < this.data[i].length; j++) {
            keys.push(this.data[i][j][0]);
          }
        }
      }
    }
    return keys;
  }
Enter fullscreen mode Exit fullscreen mode
  • Checking for the length of the Hash Table and return undefined if there is no data.
  • Creating an empty keys array.
  • Checking if the current element has a value.
  • Checking if the length of this array element is 1 O(1) so we will push the key which will be this.data[i][0][0]
  • If the length is greater than 1 O(n), then this position has more than one array so we also loop through it and return the keys inside this.data[i][j][0].

Example

const ht = new HashTable(10);
ht.set("a", 1);
ht.set("b", 2);
ht.set("c", 3);
ht.set("d", 4);
ht.set("e", 5);
ht.set("f", 6);
ht.set("g", 7);
ht.set("h", 8);
ht.set("i", 9);
ht.set("j", 10);

console.log(ht); /* 0: Array[10]
                        0: Array[2]
                          0: "a"
                          1: 1
                        1: Array[2]
                        2: Array[2]
                        3: Array[2]
                        4: Array[2]
                        5: Array[2]
                        6: Array[2]
                        7: Array[2]
                        8: Array[2]
                        9: Array[2]
                    1: undefined
                    2: undefined
                    3: undefined
                    4: undefined
                    5: undefined
                    6: undefined
                    7: undefined
                    8: undefined
                    9: undefined
                  */

console.log(ht.get("g")); // 7
console.log(ht.keys()); // ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
Enter fullscreen mode Exit fullscreen mode


LinkedIn

Top comments (0)

Read next

p_p profile image

Submission for the DevCycle Feature Flag Challenge: Skip Controller Actions

pp -

kaustubh_adhav_6666f7b909 profile image

How I Tricked My Brain to Be Addicted to Coding

Kaustubh Adhav -

layssadev profile image

Integrating Storybook into an existing next.js project

Lay -

angelika_berd profile image

Privacy-First Crypto Exchanges: Benefits and Challenges

Angelika Berdochnyk -