What are and how to use dictionaries

DICTIONARY, also called 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 SET, dictionaries use an internal hash structure which allows quick and efficient value search and retrieval.

Therefore, the only operations that a DICTIONARY allows are adding, deleting, and verifying 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 simply improve by using a dictionary correctly.

Dictionaries are used to build indexes. Imagine a book in which you have an index, so you can quickly search for which page you have 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 (one million) and you have to access them many times, always searching by ID.

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

It’s 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. This way, it’s a kind of “cache” to improve searches.

Obviously, if you only have to search once, it’s not worth building a dictionary. Because building the DICTIONARY requires a cost, you have to go through the entire collection and fill the dictionary.

Similarly, if your collection only has 10 people, you won’t notice a big improvement either. You might notice it, but you won’t dazzle anyone either.

But if you have to search multiple times, in a “reasonably long” collection, the DICTIONARY is your star collection.

Examples of dictionaries in different languages

The syntax for using a dictionary can vary depending on the programming language. Next, we’ll see examples in some popular languages:

// Declaration and use of a dictionary in :span[C#]{.badge .yellow}
Dictionary<string, int> edades = new Dictionary<string, int>();
edades.Add("Juan", 25);
edades.Add("María", 30);
edades.Add("Pedro", 28);

Console.WriteLine(edades["Juan"]); // Prints 25

// Declaration and use of a dictionary in :span[C++]{.badge .yellow}
#include <iostream>
#include <unordered_map>
using namespace std;

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

    cout << edades["Juan"] << endl; // Prints 25

    return 0;
}

// Using a dictionary in :span[JavaScript]{.badge .yellow} (using an object)
const edades = {
    Juan: 25,
    María: 30,
    Pedro: 28,
};

console.log(edades["Juan"]); // Prints 25

# Using a dictionary in :span[Python]{.badge .yellow}
edades = {
    "Juan": 25,
    "María": 30,
    "Pedro": 28,
}

print(edades["Juan"])  # Prints 25

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

Internal operation Advanced

Internally, a DICTIONARY works 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. Then, at this position, the element we are adding is saved.

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

Efficiency

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

In the case of the DICTIONARY, it doesn’t make sense to talk about sequential access, adding at the beginning, or deleting at the beginning, since the elements are not in a specific order and cannot be directly accessed by index. It also doesn’t make sense to talk about adding or deleting at the end, since the elements are not in a specific order.

It is possible to add elements “in the order they belong”. This 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 fast and constant access to search for elements by their value, which is O(1).

Read more about collection efficiency read more ⯈