Data Structures in JavaScript [Hash Tables]

What is a Hash Tables?

Why Hash Tables?

How Hash Tables Work?

What is a Hash Function?

Hash Tables with Big O Notation

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

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

Hash Tables with Big O Notation

- Access    => O(1) || O(n).
- Insert    => O(1).
- Delete    => O(1).

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

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

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

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

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

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

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"]

Thank You

Data Structures in JavaScript [Hash Tables]

Related Posts