Qué son y cómo usar los diccionarios

Los DICCIONARIOS, también llamados maps, son colecciones no ordenadas que almacenan pares clave-valor, donde cada valor está asociado a una clave única.

Cada elemento en un diccionario tiene una clave única asociada. La clave se utiliza para acceder y buscar rápidamente el valor correspondiente.

Al igual que sus “hermanos” los HASH SET, los DICCIONARIOS utilizan una estructura de hash interna lo que permite una búsqueda y recuperación de valores rápida y eficiente.

Por tanto, las únicas operaciones que permite un DICCIONARIO es la agregar, eliminar y verificar la existencia de un elemento en la colección.

Propiedades

Cuando usar un diccionario

Los DICCIONARIOS son la tu mejor aliado en cuanto a eficiencia de búsqueda. Muchos muchos algoritmos y programas mejoran simplemente por usar un diccionario correctamente.

Los DICCIONARIOS sirve para construir índices. Imagina un libro en el que tienes un índice, el que puedes buscar rápidamente a qué hoja tienes que ir para leer algo. Pues algo parecido.

Ahora supón que tienes una colección de personas, y quieres buscarlas por el DNI. Tienes muchas muchas personas (un millón) y tienes que acceder muchas veces, buscando siempre por el DNI.

En este caso, tener un Array con todas las personas y buscar cada vez a lo largo del millón de personas, te va a matar la eficiencia del programa.

Es mucho mejor si pre-calculas un diccionario, donde guardas la relacción DNI-Persona. Ahora, buscar una persona por DNI es casi instantáneo. De esta forma, es una especie de “cache” para mejorar las búsquedas.

Evidentemente, si sólo tienes que buscar una vez, no te merece la pena construir un diccionario. Porque construir el DICCIONARIO requiere un coste, tienes que recorrer toda la colección y rellenar el diccionario.

De forma simular, si tu colección solo tiene 10 personas, tampoco vas a notar una gran mejora. Posiblemente la notes, pero tampoco no deslumbrarás a nadie.

Pero si tienes que buscar múltiples veces, en una colección “medianamente larga”, el DICCIONARIO es tu colección estrella.

Ejemplos de diccionario en distintos lenguajes

La sintaxis para utilizar un diccionario puede variar según el lenguaje de programación. A continuación vamos a ver ejemplos en algunos lenguajes populares:

// Declaración y uso de un diccionario en :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"]); // Imprime 25

// Declaración y uso de un diccionario en :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; // Imprime 25

    return 0;
}

// Uso de un diccionario en :span[JavaScript]{.badge .yellow} (mediante un objeto)
const edades = {
    Juan: 25,
    María: 30,
    Pedro: 28,
};

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

# Uso de un diccionario en :span[Python]{.badge .yellow}
edades = {
    "Juan": 25,
    "María": 30,
    "Pedro": 28,
}

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

En los ejemplos anteriores, creamos un diccionario y agregamos pares clave-valor a él. Luego, accedemos al valor correspondiente utilizando la clave.

Funcionamiento interno Advanced

Internamente, un DICCIONARIO funciona de manera similar a un HASH SET. Ambos usan una función hash para asignar una clave única a cada valor y almacenarlo en una ubicación específica en la estructura de datos.

Sin embargo, a diferencia de un HashSet que usa el propio elemento que queremos guardar como clave, el diccionario usa otro valor independiente para calcular el Hash.

Cuando se agrega un par clave-valor al DICCIONARIO, se aplica la función hash a la clave para determinar su ubicación de almacenamiento. Después en esta posición, se guarda el elemento que estamos añadiendo.

Si en algún momento el DICCIONARIO se llena, este se expande automáticamente si tener que hacerlo nosotros manualmente. En ese momento, internamente se copian todos los elementos al nuevo diccionario, y se recalculan las funciones de hash.

Eficiencia

Para un DICCIONARIO, que es una estructura de datos en la que los elementos se almacenan en pares clave-valor, la tabla quedaría así:

En el caso del DICCIONARIO, no tiene sentido hablar de acceso secuencial, añadir al principio o eliminar al principio, ya que los elementos no están en un orden específico y no se pueden acceder directamente por índice. Tampoco tiene sentido hablar de añadir o eliminar al final, ya que los elementos no están en un orden específico.

Si es posible añadir elementos “en el orden que le toca”. Esa operación es O(1), salvo que tengamos que expandir el HASH SET en cuyo caso es O(n).

La operación más relevante para un DICCIONARIO es la búsqueda, que es está basado en el hashing. Esto permite un acceso rápido y constante para buscar elementos por su valor, que son O(1).

Leer más sobre eficiencia de colecciones leer más ⯈