Qué son y cómo usar HashSet

Los HASH SET, también llamados HashTables o simplemente Sets, son colecciones no ordenadas de elementos únicos. Esto significa que no puede haber duplicados en un conjunto y el orden de los elementos no importa.

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

Utiliza una técnica llamada hashing para organizar los elementos internamente, lo que permite una recuperación rápida y búsqueda muy rápida de los elementos.

Propiedades

Cuando usar una HashSet

El uso principal de un HASH SET es la búsqueda eficiente de elementos. Imagina que tienes una serie de cromos, y quieres saber si ese cromo ya lo tienes en tu colección. El famoso “tengo, no tengo” de los niños.

Con un HASH SET, vas metiendo cada cromo en la colección. Esta te dice muy rápido (mucho más que un Array) si ya tienes ese cromo añadido previamente.

El HASH SET te permite almacenar elementos en una colección saber si ya tienes ese elemento y recuperarlo si es necesario. Por tanto, el uso principal es la búsqueda de elementos, de duplicados, etc.

Finalmente, el HASH SET tiene un “hermano”, el DICCIONARIO. Este opera de forma bastante similar a un HashSet, pero con pares clave-valor.

Ejemplos de HashSet en distintos lenguajes

La sintaxis para utilizar un HashSet puede variar el lenguaje de programación que se esté utilizando.

A continuación, vamos a ver ejemplos en algunos lenguajes populares:

HashSet<string> nombres = new HashSet<string>();
nombres.Add("Juan");
nombres.Add("María");
nombres.Add("Pedro");

foreach (string nombre in nombres)
{
    Console.WriteLine(nombre);
}

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
    unordered_set<string> nombres;
    nombres.insert("Juan");
    nombres.insert("María");
    nombres.insert("Pedro");

    for (const string& nombre : nombres)
    {
        cout << nombre << endl;
    }

    return 0;
}

const nombres = new Set();
nombres.add("Juan");
nombres.add("María");
nombres.add("Pedro");

for (const nombre of nombres)
{
    console.log(nombre);
}

nombres = set()
nombres.add("Juan")
nombres.add("María")
nombres.add("Pedro")

for nombre in nombres:
    print(nombre)

En los ejemplos anteriores, creamos un HashSet (utilizando la clase HashSet en C# y C++, y el objeto Set en JavaScript y Python) y agregamos varios elementos a él. Luego, iteramos sobre los elementos del HashSet y los mostramos por pantalla.

Funcionamiento interno Advanced

Internamente, un HASH SET funciona de manera similar a un array dinámico, pero que utiliza una función utiliza una función hash para generar los índices numéricos de los elementos.

Una función hash es una función que toma un elemento como entrada y devuelve un valor único asociado a ese elemento. Este valor único se utiliza como índice para almacenar y recuperar el objeto en el HashSet.

La “gracia” de una función de Hash es que está diseñada de manera que proporcione resultados únicos y distribuidos uniformemente para cada elemento. Parece muy complicado, pero un ejemplo sencillo de función Hash podría ser simplemente calcular el módulo del valor del elemento (en binario) con respecto al tamaño del HASH SET.

Cuando se agrega un elemento al HASH SET, se aplica la función hash al objeto para determinar su índice de almacenamiento. En esa posición, se guarda el elemento en la posición que da su función hash.

Ahora, si tenemos que consultar si nuestro HASH SET contiene un elemento, simplemente calcula la función hash del elemento y mira si en la posición está ocupada o no. Si está ocupada es que ya lo contiene, y si está vacía es que no..

Si al añadir elementos se nos llena el HASH SET, como es un Array dinámico, este se expande dinámicamente de forma transparente para el usuario. Además se cambia la función Hash para el nuevo tamaño, y se deben recalcular todos los Hash de los elementos almacenados.

Esto tiene también es el motivo por el que un HashSet no tiene orden. Los elementos se van guardando internamente “donde les toca”, que no tiene nada que ver con el orden en el que los hemos introducido.

La función hash garantiza que los elementos se almacenen y se busquen de manera eficiente, ya que la búsqueda se realiza directamente en la posición calculada mediante la función hash, sin necesidad de recorrer todos los elementos.

Eficiencia

Para un HASH SET, que es una colección en la que los elementos no están ordenados y no permite duplicados, la tabla quedaría así:

En el caso del HASH SET, 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 HashSet en cuayo caso es O(n).

La operación más relevante para un HASH SET 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 ⯈