Introduction to data structures: Map

Learn about the map data structure in an intuitive way

November 19th, 2024 3 minute read

The map data structure is also know as "dictionary" and "associative array".
It's a really useful data structure that uses keys to store and retrieve values (i.e. it maps keys to values). Another way to look at it is that it associates keys with values (hence the name "associative array").
Let's learn what the map data structure is and how it works.

Let's give a few examples of using maps in our daily lifes:

When we order food in a restaurant and the menu has numbers for each dish. We could order dish 151 and the chef would prepare us spaghetti 🍝. The chef "maps" or "associates" the key 151 with the value spaghetti. The menu is basically a map that maps numbers to dishes 🔢 => 🍽️. The number is the key and the dish is the value.
When we use a phonebook to find someone's phone number (I know that we don't do this now, but people did in the past 😀). The phonebook is a map that maps a person's name to their phonenumber. The person's name is the key and the person's phone number is the value.

The map data structure usually provides the following operations:

put - used to insert a key/value pair into the map.
get - used to exchange a key for a value in the map.
remove - used to remove a key/value pair from the map.

A map's key and value can be of any data type (e.g. number, string, object).
If you remember, an array provides access to elements using indices (i.e. integers starting from zero). The indices are basically the array's keys and we can use them to get the corresponding value.
In contrast, the map data structure allows us to use any data type as a key. Of course, this comes with a price. Arrays are faster than maps in terms of data access.

The map data structure is useful when there is a large dataset that needs to be accessed efficiently. Let's give a few examples:

Data cache - data that is frequently needed can be cached (i.e. placed in a faster memory) using the map data structure. Each data item that needs to be cached will have a corresponding key that will be used to retrieve it from the cache.
Web session management - a server can map session IDs to users. When a request comes with a specific session ID, the server can use it as a key to find the corresponding user.

How do maps work internally?
The map data structure usually uses an array internally. When a key is provided to put/get/remove a value, the map converts the key to an array index. It then uses this index to access the internal array. The operation of converting the key to an array index is called hashing and these types of maps are called hash maps.
There are other types of maps as well and maybe we will cover some of them in future articles.

If you enjoy my articles, please consider supporting me.