Hash Tables - full guide
Tags: webdev, algorithms, computerscience, javascript
Published: 2022-10-20 15:49:02

Hash Table is a data structure that maps keys to values. You can then retrieve a certain value by using its key.

#### The way Hash Table Work?
• It takes a **Key** and then runs it through a **Hash Function**.
• A Hash Function maps strings to numbers and these numbers 
  correspond to indices in an Array.

![hash function](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2rb5uux1col6s4ifdoh6.png)

### How to implement a Hash Table in JavaScript?
We will talk about **3** ways to implement a Hash Table in JS:

**1.** Using `Object` data type.
**2.** Using a `Map` Object.
**3.** Implement your own Hash Table.

---

## 1️⃣Using `Object` data type - simplest implementation 

![Object as HashTable](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/40s1qe9hlewokkd2p1a1.png)
#### <u>There are some downsides to this approach:</u>
**1.** The `Object` comes with its own properties and methods. The problem here is JS doesn't block an attempt to overwrite these methods, which may cause an error.

![code1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zu34h95ux3s8afauroow.png)

**2.** The keys are limited to `String` or `Symbol` data type.

**3.** The size of Object is not tracked, you need to manually determine it.
![determine object length](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1g3gkmak9jqg200evvxm.png)

---

## 2️⃣Using `Map` object
The `Map` object is created to implement Hash Table without downsides that appeared on basic `Object`.

#### <u>Unlike Object:</u>
• `Map `have `size `property to track its contents.
• Keys can be any data type.
• You can't overwrite built-in properties/methods.
• You must use the `set()` and `get()` methods to define and retrieve data.

![Map as HasTable](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/do9t4ijgz1nv9wtaw8dz.png)

---

## 3️⃣Implement your own Hash Table
You'll probably never have to implement Hash Table yourself, But writing your own Hash Table implementation is one of the most common JS interview questions.
![Write your own HashTable](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i7vuss7y58zz8onnzzdd.png)
Alright, all method work as expected. Let's try another insertion:
![another insertion](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2aja539dl99mzxe1b31w.png)
😨!! When I call `table.get('name');` it should retrieve `['name', 'Amr']`, **<u>So why is it not working as expected!?</u>**

• `hash()` function uses **ASCII** code to convert key to an index. So if the keys are the same set of letters <u>(name == mane)</u> the index will be the same. And this will cause overwriting the previous value with the new one.

• This is called **Collision** and needs to be handled in our implementation.

---

## How to Handle Collision?
Collision occurs when hash() function generate the same index for different keys.

#### <u>There are 2 main ways to handle collision:</u>
**1.** Separate Chaining
**2.** Open Addressing

Here we'll just learn Separate Chaining..

##⏩ Handle Collision - Separate Chaining
If multiple keys map to the same index, start a new `Array` at this index.
![Separate Chaining](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o8nk4bdkc284k8v7prh8.png)

Now, Let's improve our `set()` method to avoid collision:
![set method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vuauzyo9sogn6f4ihiet.png)

Also, update get() method
![get methpd](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ecd261xg5g67f6gf1jso.png)

and remove() method:
![remove method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hra2aho2rpw22qxfj0np.png)

Now, as a bonus let's add a display() method:

![display method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6oqbpf0gjejp6tt649kq.png)
---
## Conclusion
You have learned what Hash Table is and different ways to implement it in JavaScript.

You've also learned how to implement your own Hash Table class as well as how to Handle Collisions.

You'll commonly use a Hash Table because of its fast search, insertion, and delete operations:
![time complexity](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vlc7a1v67nv6f7gv8dmf.png)

---
### Main Resources
• Grokking Algorithms Book
• https://www.codecademy.com/resources/docs/javascript/hashtables
• https://www.youtube.com/watch?v=y3CcHKEM8r8