Data Structures in JavaScript [Hash Tables]
Published: 2021-07-04 16:01:24

- [What is a Hash Tables?](#what-is-a-hash-tables)
- [Why Hash Tables?](#why-hash-tables)
- [How Hash Tables Work?](#how-hash-tables-work)
- [What is a Hash Function?](#what-is-a-hash-function)
- [Hash Tables with Big O Notation](#hash-tables-with-big-o-notation)
- [Implementing Hash Tables](#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

```js
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](http://www.miraclesalad.com/webtools/md5.php)

**Example of a simple Hash Function**

```js
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**

```js
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.

```js
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*
```js
_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*
```js
  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*
```js
  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*
```js
  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**

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

<a href="https://www.linkedin.com/in/youssefzidan/" target="_blank">
    <img src="https://img.shields.io/badge/LinkedIn-%230077B5.svg?&style=flat-square&logo=linkedin&logoColor=white" alt="LinkedIn">