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