What are and how to use dictionaries

Dictionaries, also known as maps, are unordered collections that store key-value pairs, where each value is associated with a unique key.

Each element in a dictionary has a unique associated key. The key is used to quickly access and search for the corresponding value.

Like their “siblings” the Hash Sets, dictionaries use an internal hash structure which allows quick and efficient value searching and retrieval.

Therefore, the only operations that a dictionary allows are adding, removing, and checking the existence of an element in the collection.

Properties

When to use a dictionary

Dictionaries are your best ally in terms of search efficiency. Many algorithms and programs improve simply by using a dictionary correctly.

Dictionaries are used to build indexes. Imagine a book where you have an index, which you can quickly search to find out which page you need to go to read something (something similar).

Now suppose you have a collection of people, and you want to search for them by their ID number. You have many, many people (a million) and you need to access them many times, always searching by ID number.

In this case, having an Array with all the people and searching each time through a million people will kill the efficiency of the program.

It is much better if you pre-calculate a dictionary, where you store the ID-Person relationship. Now, searching for a person by ID is almost instantaneous. In this way, it serves as a kind of “cache” to improve searches.

Dictionary examples in different languages

The syntax for using a dictionary can vary depending on the programming language. Below we will see examples in some popular languages:

// Declaration and use of a dictionary in :lang[C#]
Dictionary<string, int> ages = new Dictionary<string, int>();
ages.Add("Luis", 25);
ages.Add("María", 30);
ages.Add("Pedro", 28);

Console.WriteLine(ages["Luis"]); // Prints 25

// Declaration and use of a dictionary in :lang[C++]
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<string, int> ages;
    ages["Luis"] = 25;
    ages["María"] = 30;
    ages["Pedro"] = 28;

    cout << ages["Luis"] << endl; // Prints 25

    return 0;
}

// Use of a dictionary in :lang[JavaScript] (through an object)
const ages = {
    Luis: 25,
    María: 30,
    Pedro: 28,
};

console.log(ages["Luis"]); // Prints 25

# Use of a dictionary in :lang[Python]
ages = {
    "Luis": 25,
    "María": 30,
    "Pedro": 28,
}

print(ages["Luis"])  # Prints 25

In the previous examples, we created a dictionary and added key-value pairs to it. Then, we accessed the corresponding value using the key.

Internal operation Advanced

Internally, a dictionary functions similarly to a Hash Set. Both use a hash function to assign a unique key to each value and store it in a specific location in the data structure.

However, unlike a HashSet that uses the element we want to store as the key, the dictionary uses another independent value to calculate the Hash.

When a key-value pair is added to the dictionary, the hash function is applied to the key to determine its storage location. After that, the element we are adding is stored at this position.

If at any point the dictionary gets full, it automatically expands without us having to do it manually. At that moment, all elements are internally copied to the new dictionary, and hash functions are recalculated.

Efficiency

For a dictionary, which is a data structure where elements are stored in key-value pairs, the table would look like this:

In the case of the dictionary, it makes no sense to talk about sequential access, adding to the beginning, or removing from the beginning, since the elements are not in a specific order and cannot be accessed directly by index. It also makes no sense to talk about adding or removing from the end, as the elements are not in a specific order.

It is possible to add elements “in the order they belong.” That operation is O(1), unless we have to expand the Hash Set, in which case it is O(n).

The most relevant operation for a dictionary is searching, which is based on hashing. This allows for quick and constant access to search for elements by their value, which is O(1).