JavaScript Data Structures: Hash Table: Intro
Tags: beginners, tutorial, javascript, webdev
Published: 2020-02-17 08:01:35

---
title: "JavaScript Data Structures: Hash Table: Intro"
description: "JavaScript Data Structures: Hash Table: Intro"
published: true
tags: ["Beginners", "Tutorial", "JavaScript", "Webdev"]
series: JavaScript Data Structures
---

## Intro 🌐

After we [compared our linear data structures](https://dev.to/miku86/javascript-data-structures-recap-lists-stack-queue-2can), we start with the Hash Table.

---

## Problem: WHY do we need a Hash Table?

If we want to store user data, we could use an array, e.g.:

```js
const user = ['miku86', 'Germany', 33]
```

This works, but it could be hard to understand.

The first value could be my name,
the second one could be my home country (are you sure?),
but what is the meaning of the third one?

A lot of guessing here, because we don't have a lot of context.
The second element could have various meanings,
e.g. my home country, my current location, my favorite country to travel to or the best soccer team in the world.

It would be awesome, if we could give every value a context, e.g.:

```js
const user = {
  name: 'miku86',
  homeCountry: 'Germany',
  age: 33,
}
```

This is a data structure that gives every value a context.
Each `value` has a context, because each has a `key` that is human-readable.

If you did some JavaScript stuff, you've already seen this data structure,
JavaScript calls it an `object`, the broader term is **Hash Table**.

## What is a Hash Table? ▶️

- most languages have (a variation of) a hash table built-in
- Example: `object` (JavaScript) or `Dictionary` (Python)
- each data entry has a (human-readable) key that is matched to a value, e.g. the key `name` is matched to the value `miku86`
- keys are not ordered
- fast: search, add, remove
- because we use a hash function (explanation later), it is called a **Hash Table**

## How do we build a Hash Table (without using the built-in `object`)? 🛠

- we'll use an array
- we want to find a value by using its key, e.g. `user.name => "miku86"`
- to find an array index by using a key, we have to connect a `key` to an `index`
- to convert a human-readable `key` into an array index, we use a **hash function**
- because we use a hash function, the data structure is called **Hash Table**

## Thoughts 💭

Let's use the example from above:

```js
const user = {
  name: 'miku86',
  homeCountry: 'Germany',
  age: 33,
}
```

We want to get my name value by using the key `name`.
Because we want to use an array under the hood, we should think about it like that:

```js
const user = ['miku86', 'Germany', '33']
```

We have 3 array items, each array item has exactly one value in it, e.g. the array item with index 0 has the value 'miku86'.

So to access the correct value, we always have to know the correct array index.

But we don't want to work with the index, we want to work with the key, e.g. `name`, but there is no key 🤷

We need a function that takes our key, e.g. `name`, and converts it into the correct index of the array item our value lives in, e.g. `0`.

This is where the hash functions comes into play.

---

## Next Part ➡️

We will learn how to build our own simple hash function for the Hash Table.

Don't miss interesting stuff, [read here](https://miku86.com/)!

---

## Further Reading 📖

- [Simple Wiki: Hash Table](https://simple.wikipedia.org/wiki/Hash_table)
- [Wikipedia: Hash Table](https://en.wikipedia.org/wiki/Hash_table)
- [Wikibooks: Hash Table](https://en.wikibooks.org/wiki/Data_Structures/Hash_Tables)

---

## Questions ❔

- Do you understand the bigger concept of the Hash Table?
- Can you explain the concept to another person?
- Can you think about the Big O of a Hash Table (without looking it up)?