Intro 🌐
After we 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) orDictionary
(Python) - each data entry has a (human-readable) key that is matched to a value, e.g. the key
name
is matched to the valuemiku86
- 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 anindex
- 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
, 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!
Further Reading 📖
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)?
Top comments (0)