miku86

Intro 🌐

After we finished the small series about the Queue and compared our linear data structures, 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.:

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.:

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:

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:

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, there even isn't a 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, go to!

Further Reading 📖

• Simple Wiki: Hash Table
• Wikipedia: Hash Table
• Wikibooks: Hash Table

Questions ❔

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