Los mapas asociativos almacenan pares clave-valor y permiten acceder a valores mediante sus claves. Son fundamentales en programación.

En este artículo, aprenderás cómo implementar un mapa en Python, incluyendo sus operaciones y características principales. Esta entrega complementa lo que ya viste sobre arreglos, pilas y conjuntos.

Puedes encontrar el código Python de este artículo en el repositorio de ejemplos de Python Scouts. ¡Te agradeceríamos mucho si nos dejas una estrella (⭐) en el repositorio!

Contenidos

¿Qué es un mapa o map?

Un mapa, también conocido como arreglo asociativo, es una colección que almacena pares clave-valor. Cada clave se asocia a un valor correspondiente, lo que facilita la búsqueda de valores a través de sus claves. Las claves deben ser únicas y, generalmente, deben ser objetos hashables.

En Python, la implementación integrada de los mapas se llama dict y suele nombrarse como diccionario. En este artículo usarás mapa para referirte a la estructura de datos en general.

Las características fundamentales de un mapa incluyen las siguientes:

  • Pares clave-valor: Cada entrada consta de una clave única y un valor asociado.
  • Claves únicas: No puede haber claves duplicadas. Asignar un nuevo valor a una clave existente sobrescribe el valor anterior.
  • Acceso por clave: Puedes acceder a cualquier valor directamente a través de su clave.

En Python, los mapas están integrados como el tipo dict, pero en este artículo implementarás tu propio mapa usando dos listas paralelas para comprender su funcionamiento interno.

Operaciones comunes en un mapa

A continuación, un resumen de las operaciones que soportará tu mapa:

Operación Descripción
m = Map() Construye un mapa vacío.
m = Map(mapping) Construye un mapa con pares clave-valor de mapping.
m = Map(**kwargs) Construye un mapa a partir de argumentos por nombre.
m[key] Devuelve el valor asociado a key.
m[key] = value Asigna value a key.
del m[key] Elimina el par clave-valor de key.
m.keys() Devuelve un iterador sobre las claves del mapa.
m.values() Devuelve un iterador sobre los valores del mapa.
m.items() Devuelve un iterador que produce tuplas clave-valor.
m.update(other) Actualiza el mapa con los elementos de other.
m.set_default(key[, default]) Inserta un par clave-valor si la clave no existe. Devuelve el valor de la clave.
m.pop(key) Elimina un par clave-valor y devuelve el valor.
m.popitem() Elimina y devuelve un par clave-valor como una tupla.
m.clear() Elimina todos los pares clave-valor del mapa.
Map.fromkeys(iterable[, value]) Construye un nuevo mapa con claves de iterable y valores de value.
m == other Devuelve True si ambos mapas contienen los mismos pares clave-valor.
len(m) Devuelve el número de pares clave-valor en el mapa.
key in m Devuelve True si key está en el mapa, False en caso contrario, usando el operador in.

Implementación de un mapa en Python

A continuación encontrarás la implementación del mapa en Python:

Python - map_adt.py
from typing import Any, Iterator, Mapping, Optional, Sequence, Tuple

class Map:
    """Implement a Map (associative array) abstract data type."""

    def __init__(
        self, mapping: Optional[Mapping[Any, Any]] = None, /, **kwargs
    ) -> None:
        self._keys: list[Any] = []
        self._values: list[Any] = []
        self.__update(mapping, **kwargs)

    def keys(self) -> Iterator[Any]:
        """Return an iterator over the keys of map."""
        yield from self._keys

    __iter__ = keys

    def values(self) -> Iterator[Any]:
        """Return an iterator over the values of map."""
        yield from self._values

    def items(self) -> Iterator[Tuple[Any, Any]]:
        """Return an iterator that yields key-value tuples."""
        yield from zip(self._keys, self._values)

    __items = items

    def update(
        self, other: Optional[Mapping[Any, Any]] = None, /, **kwargs
    ) -> None:
        """Update map with items from other."""
        if other is not None:
            for key, value in other.items():
                self[key] = value
        if kwargs:
            for key, value in kwargs.items():
                self[key] = value

    __update = update

    def set_default(
        self, key: Any, default: Optional[Any] = None, /
        ) -> Any:
        """Insert a key-default pair into map if key doesn't exist.

        Return the value for key if key is in the map, else default.
        """
        try:
            return self[key]
        except KeyError:
            self[key] = default
            return default

    def pop(self, key: Any) -> Any:
        """Remove a key-value pair and return the value."""
        try:
            index = self._keys.index(key)
        except ValueError:
            raise KeyError(f"{key}") from None
        self._keys.remove(key)
        return self._values.pop(index)

    def popitem(self) -> Tuple[Any, Any]:
        """Remove and return a key-value pair as a tuple."""
        try:
            return self._keys.pop(), self._values.pop()
        except IndexError:
            raise KeyError("popitem from empty Map") from None

    def clear(self) -> None:
        """Remove all the items from map."""
        self._keys.clear()
        self._values.clear()

    @classmethod
    def fromkeys(
        cls, iterable: Sequence, value: Optional[Any] = None, /
    ) -> "Map":
        """Return a new Map with keys from iterable and values from value."""
        mapping = cls()
        for key in iterable:
            mapping[key] = value
        return mapping

    def get(self, key: Any, default: Optional[Any] = None) -> Any:
        """Return the value for key if key is in the map, else default."""
        try:
            return self[key]
        except KeyError:
            return default

    def __getitem__(self, key: Any) -> Any:
        try:
            index = self._keys.index(key)
        except ValueError:
            raise KeyError(f"{key}") from None
        return self._values[index]

    def __setitem__(self, key: Any, value: Any) -> None:
        hash(key)
        if key in self._keys:
            index = self._keys.index(key)
            self._values[index] = value
        else:
            self._keys.append(key)
            self._values.append(value)

    def __eq__(self, other: "Map") -> bool:
        if other.__class__ is not self.__class__:
            return False
        if len(self) != len(other):
            return False
        other_items = list(other.__items())
        for item in self.__items():
            if item not in other_items:
                return False
        return True

    def __contains__(self, key: Any) -> bool:
        return key in self._keys

    def __len__(self) -> int:
        return len(self._keys)

    def __repr__(self) -> str:
        return (
            f"{self.__class__.__name__}"
            f"({dict(zip(self._keys, self._values))})"
        )

    def __str__(self) -> str:
        return f"{dict(zip(self._keys, self._values))}"

    def __delitem__(self, key: Any) -> None:
        try:
            index = self._keys.index(key)
        except ValueError:
            raise KeyError(f"{key}") from None
        del self._keys[index]
        del self._values[index]

    def __reversed__(self) -> Iterator:
        yield from reversed(self._keys)

Esta implementación usa dos listas paralelas: ._keys almacena las claves y ._values almacena los valores correspondientes. Cada clave en la posición i de ._keys se asocia al valor en la misma posición i de ._values.

Los métodos principales te permiten ofrecer las siguientes funcionalidades:

  • .keys(): devuelve un iterador sobre las claves del mapa.
  • .values(): devuelve un iterador sobre los valores del mapa.
  • .items(): devuelve un iterador que produce tuplas clave-valor.
  • .update(): actualiza el mapa con pares clave-valor de otro mapeo o de argumentos por nombre.
  • .set_default(): inserta un par clave-valor solo si la clave no existe. Devuelve el valor asociado.
  • .pop(): elimina un par clave-valor y devuelve el valor. Lanza KeyError si la clave no existe.
  • .popitem(): elimina y devuelve el último par clave-valor como una tupla.
  • .clear(): elimina todos los pares clave-valor.
  • .fromkeys(): método de clase que construye un nuevo mapa con claves hashables de un iterable y un valor por defecto.
  • .get(): devuelve el valor asociado a una clave, o un valor por defecto si la clave no existe.

Los métodos especiales te permiten ofrecer las siguientes funcionalidades:

  • .__getitem__() y .__setitem__(): permiten acceder y asignar valores con la sintaxis m[key] y m[key] = value.
  • .__delitem__(): permite eliminar pares clave-valor con del m[key].
  • .__eq__(): compara dos mapas por igualdad y devuelve False si comparas con objetos de otro tipo.
  • .__contains__(): comprueba si una clave existe en el mapa.
  • .__len__(): devuelve el número de pares clave-valor.
  • .__repr__() y .__str__(): devuelven representaciones de cadena legibles.
  • .__reversed__(): permite iterar sobre las claves en orden inverso.

Ejemplo de uso del mapa

En esta sección verás ejemplos prácticos de cómo crear y manipular instancias de tu clase Map.

Inicialización

Para crear un Map, puedes hacerlo de varias formas:

Python REPL
>>> from map_adt import Map

>>> my_map = Map()
>>> my_map
Map({})

>>> my_map = Map({"one": 1, "two": 2})
>>> my_map
Map({'one': 1, 'two': 2})

>>> my_map = Map(one=1, two=2)
>>> my_map
Map({'one': 1, 'two': 2})

Acceso y modificación de elementos

Puedes acceder y modificar elementos usando la sintaxis de corchetes:

Python REPL
>>> from map_adt import Map

>>> my_map = Map({"one": 1, "two": 2})

>>> my_map["one"]
1
>>> my_map["two"]
2

>>> my_map["three"] = 3
>>> my_map
Map({'one': 1, 'two': 2, 'three': 3})

Si intentas acceder a una clave que no existe, obtendrás un error:

Python REPL
>>> from map_adt import Map

>>> my_map = Map({"one": 1})
>>> my_map["missing"]
Traceback (most recent call last):
    ...
KeyError: 'missing'

Puedes usar .get() para obtener un valor por defecto en lugar de un error:

Python REPL
>>> from map_adt import Map

>>> my_map = Map({"one": 1})
>>> my_map.get("one")
1
>>> my_map.get("missing", 0)
0

Eliminar elementos

Puedes eliminar pares clave-valor con del o con .pop():

Python REPL
>>> from map_adt import Map

>>> my_map = Map(one=1, two=2, three=3)

>>> del my_map["three"]
>>> my_map
Map({'one': 1, 'two': 2})

>>> my_map.pop("two")
2
>>> my_map
Map({'one': 1})

Iterar sobre claves, valores y pares

Puedes iterar sobre las claves, los valores o ambos:

Python REPL
>>> from map_adt import Map

>>> my_map = Map(one=1, two=2, three=3)

>>> for key in my_map:
...     print(key)
...
one
two
three

>>> for value in my_map.values():
...     print(value)
...
1
2
3

>>> for key, value in my_map.items():
...     print(f"{key} -> {value}")
...
one -> 1
two -> 2
three -> 3

Longitud y pertenencia

Puedes consultar la longitud del mapa y verificar si una clave está contenida en él:

Python REPL
>>> from map_adt import Map

>>> my_map = Map(one=1, two=2, three=3)

>>> len(my_map)
3

>>> "one" in my_map
True
>>> "four" in my_map
False

Construir desde claves

El método de clase .fromkeys() permite construir un mapa a partir de una secuencia de claves:

Python REPL
>>> from map_adt import Map

>>> Map.fromkeys(["one", "two", "three"])
Map({'one': None, 'two': None, 'three': None})

>>> Map.fromkeys(["cats", "dogs"], 0)
Map({'cats': 0, 'dogs': 0})

Conclusión

Has aprendido cómo implementar un mapa que almacena pares clave-valor y proporciona operaciones esenciales como acceso por clave, inserción, eliminación e iteración.

Este conocimiento te permite comprender cómo funcionan internamente los mapas y cuándo usarlos para resolver problemas que requieren asociar claves con valores.

Puedes encontrar el código Python de este artículo en el repositorio de ejemplos de Python Scouts. ¡Te agradeceríamos mucho si nos dejas una estrella (⭐) en el repositorio!