Ir al contenido
wannacode

HashMap y HashSet

En resumen: Un mapa (diccionario) guarda pares de clave y valor con claves únicas y encuentra rápido un valor por su clave, y un conjunto guarda valores únicos.

Problema

¿Quién es este usuario?

Los usuarios del sitio están en una lista. En cada inicio de sesión buscas el correo por el nombre de usuario:

static String findEmail(List<User> users, String username) {
    for (User u : users) {
        if (u.username.equals(username)) {
            return u.email;
        }
    }
    return null;
}

Con tres usuarios es instantáneo. Con 2 000 000, cada inicio de sesión compara hasta 2 000 000 nombres, y hay miles de inicios de sesión por minuto. Una guía telefónica no se lee desde la primera página. Vas directo a la letra.

La idea

Diccionario: clave → valor

Quieres preguntar «¿cuál es el correo de garcia?» y obtener la respuesta al instante. La colección para esto se llama diccionario (mapa). Guarda pares: una clave y un valor. En Java el diccionario habitual es HashMap:

Map<String, String> emails = new HashMap<>();
emails.put("garcia", "garcia@example.com");
emails.put("mlopez", "mlopez@example.com");
emails.put("fernandez", "fernandez@example.com");


System.out.println(emails.get("fernandez"));
System.out.println(emails.get("nadie"));
System.out.println("Usuarios: " + emails.size());
Salida
fernandez@example.com
null
Usuarios: 3
  • Hay dos parámetros de tipo: uno para la clave y otro para el valor. Map<String, String> es «de texto a texto».
  • put(clave, valor) guarda un par, y get(clave) devuelve el valor.
  • Una clave que no está da null.
  • Map y HashMap están en java.util. Otra vez, la interfaz va a la izquierda, y la clase, después de new.

get no recorre todos los pares. Encuentra el lugar de la clave casi al instante, sin importar cuántos haya. Cómo lo hace es la siguiente lección.

La idea

El almacén: cambios y comprobaciones

Las existencias de un almacén: artículo → cantidad.

Map<String, Integer> stock = new HashMap<>();
stock.put("portátil", 4);
stock.put("ratón", 25);
stock.put("portátil", 3);


System.out.println(stock.get("portátil"));
System.out.println(stock.containsKey("monitor"));
System.out.println(stock.getOrDefault("monitor", 0));
stock.remove("ratón");
System.out.println(stock.size());
Salida
3
false
0
1
  • Las claves son únicas. El segundo put("portátil", 3) no agrega una fila nueva. Reemplaza 4 por 3.
  • containsKey pregunta si la clave está en el mapa.
  • getOrDefault(clave, 0) devuelve el valor, o 0 si la clave no está. Esto te protege de null.
  • remove(clave) quita el par.
Más precisamente, para curiosos
  • Los valores se pueden repetir: el portátil y el ratón pueden ser 3 los dos. Las claves no.
  • También existe containsValue. Pero recorre todos los valores, porque un diccionario es rápido solo por clave.

Pruébalo

¿Cuántos hay en el menú?

¿Qué imprimirá el programa?

Map<String, Integer> menu = new HashMap<>();
menu.put("café", 2);
menu.put("té", 2);
menu.put("café", 3);
System.out.println(menu.size() + " " + menu.get("café"));
Respuesta

La idea

Recorrido y orden

El precio de envío por ciudad. Un diccionario se recorre por pares con entrySet():

Map<String, Double> delivery = new HashMap<>();
delivery.put("Sofia", 4.5);
delivery.put("Plovdiv", 5.2);
delivery.put("Varna", 6.0);
delivery.put("Burgas", 6.0);
delivery.put("Ruse", 5.8);


for (Map.Entry<String, Double> e : delivery.entrySet()) {
    System.out.println(e.getKey() + ": " + e.getValue() + " €");
}
Salida
Ruse: 5.8 €
Varna: 6.0 €
Sofia: 4.5 €
Plovdiv: 5.2 €
Burgas: 6.0 €

Ruse salió primero, pero Sofia se agregó primero. HashMap no promete ningún orden. El orden depende de los códigos hash de las claves, que son el tema de la siguiente lección. No escribas código que dependa de él.

Cuando el orden importa, cambia solo la clase después de new:

  • LinkedHashMap mantiene el orden en que se agregan. Con las mismas llamadas a put y System.out.println(delivery):
Salida
{Sofia=4.5, Plovdiv=5.2, Varna=6.0, Burgas=6.0, Ruse=5.8}
  • TreeMap ordena las claves:
Map<String, Double> delivery = new TreeMap<>();
delivery.put("Sofia", 4.5);
delivery.put("Plovdiv", 5.2);
delivery.put("Varna", 6.0);
delivery.put("Burgas", 6.0);
delivery.put("Ruse", 5.8);


System.out.println(delivery);
Salida
{Burgas=6.0, Plovdiv=5.2, Ruse=5.8, Sofia=4.5, Varna=6.0}

Map.Entry<String, Double> es un par: getKey() y getValue(). Hay un punto en el nombre porque el tipo está declarado dentro de Map. Verás tipos así en la lección «Clases anidadas».

Más precisamente, para curiosos
  • Si necesitas solo las claves, recorre keySet(). Si necesitas solo los valores, recorre values():
for (String city : delivery.keySet()) {
    System.out.print(city + " ");
}
System.out.println();


double sum = 0;
for (double price : delivery.values()) {
    sum += price;
}
System.out.println("Media: " + sum / delivery.size() + " €");
Salida
Ruse Varna Sofia Plovdiv Burgas
Media: 5.5 €
  • TreeMap es más lento que HashMap, porque mantiene las claves ordenadas. Úsalo cuando necesites el orden.
  • Con las mismas claves, un HashMap en una misma versión de Java suele imprimir en el mismo orden. Eso no es una promesa: el orden puede cambiar con otra versión, con más elementos o con otro número de cubetas.

La idea

Conteo

¿Cuántas veces se pidió cada artículo? La clave es el artículo, y el valor es la cantidad. En cada pedido tomas la cantidad anterior (o 0) y le sumas 1:

String orders = "café té café cacao café té";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);
Salida
{cacao=1, café=3, té=2}

Este es el uso más común de un diccionario: contar palabras, votos, errores por tipo, ventas por ciudad. Aquí es un TreeMap, así que los artículos salen ordenados.

String orders = "café té café cacao café té";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);
Paso a paso, en palabras
  1. 6 pedidos y un TreeMap vacío.
  2. «café» no está: getOrDefault da 0, y put añade la clave con 1.
  3. «té» no está: getOrDefault da 0, y put añade la clave con 1.
  4. «café» ya está: getOrDefault da 1, y put reemplaza el valor por 2.
  5. «cacao» no está: getOrDefault da 0, y put añade la clave con 1. TreeMap la pone antes de «café»: las claves están ordenadas.
  6. «café» ya está: getOrDefault da 2, y put reemplaza el valor por 3.
  7. «té» ya está: getOrDefault da 1, y put reemplaza el valor por 2.
  8. Cada producto es una clave una sola vez, y el valor es cuántas veces se pidió.
Más precisamente, para curiosos
  • split(" ") de la lección sobre texto divide la línea en palabras.
  • En el módulo «Java moderno» verás una forma más corta de escribir lo mismo, con el método merge.

Pruébalo

Encuentra el error

El programa debería contar los pedidos. En cambio, se detiene en el primero:
Error
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

¿En qué línea está el error?

Elige la línea con el error.

La idea

HashSet: cada uno una vez

¿Cuántas personas distintas iniciaron sesión hoy en el sitio? Si alguien entra cinco veces, debe contarse una sola. Una colección que guarda cada valor una sola vez se llama conjunto:

String[] visits = { "ana@example.com", "bruno@example.com", "ana@example.com", "vera@example.com", "bruno@example.com" };
Set<String> visitors = new HashSet<>();
for (String email : visits) {
    visitors.add(email);
}
System.out.println("Visitas: " + visits.length);
System.out.println("Visitantes únicos: " + visitors.size());
System.out.println(visitors.contains("vera@example.com"));
Salida
Visitas: 5
Visitantes únicos: 3
true
  • add sobre un valor que ya está no hace nada y devuelve false. Si es nuevo, devuelve true.
  • contains es tan rápido como containsKey en un diccionario. Por dentro, un HashSet es un HashMap en el que guardas solo las claves.
  • No hay índices. Un conjunto responde solo a la pregunta «¿está aquí?».
Más precisamente, para curiosos
  • Aquí tampoco se promete el orden. LinkedHashSet mantiene el orden en que se agregan, y TreeSet ordena:
Set<String> tags = new TreeSet<>();
tags.add("java");
tags.add("sql");
tags.add("git");
tags.add("java");
System.out.println(tags);
Salida
[git, java, sql]
  • retainAll deja solo los elementos que dos conjuntos tienen en común, y addAll los une. Los necesitarás en el ejercicio.

Pruébalo

Una factura repetida

El contador quiere ver los números de factura que se ingresaron dos veces. ¿Qué método comprueba y agrega a la vez?
String[] invoices = { "F-101", "F-102", "F-101", "F-103" };
Set<String> seen = new HashSet<>();
for (String number : invoices) {
    if (!seen.(number)) {
        System.out.println("Factura repetida: " + number);
    }
}

Ejercicio

Diccionarios en acción

Resuelve las tareas en tu editor.

1. Una tabla de usuarios. Una clase UserTable con los métodos add(String username, String email), get(String username) y size(). Por dentro es un HashMap. Agrega garcia, mlopez y fernandez con correos de la forma garcia@example.com, y busca mlopez y nadie. En la siguiente lección también construirás tu propia tabla hash, sin HashMap.

Salida
mlopez: mlopez@example.com
nadie: no existe ese usuario
Usuarios: 3

2. Frecuencia de palabras. Lee una línea de texto, pásala a minúsculas y cuenta cada palabra. Imprime las palabras en orden alfabético.

Entrada
Café con leche y café sin azúcar y café
Salida
azúcar: 1
café: 3
con: 1
leche: 1
sin: 1
y: 2

3. Documentos por palabra clave. Una clase DocumentIndex con los métodos addDocument(int id, String... keywords) y search(String keyword), que devuelve una lista con los números de los documentos que tienen esa palabra. Por dentro es un Map<String, List<Integer>>: para cada palabra, una lista de documentos. Agrega el documento 1 con "POO" y "Java", el documento 2 con "SQL" y "bases de datos", y el documento 3 con "Java" y "colecciones". Busca "Java", "SQL" y "Python".

Salida
Java: [1, 3]
SQL: [2]
Python: []

4. Una red de contactos. Una clase Contact con nombre y correo, y una clase ContactNetwork con los métodos addContact(String name, String email), addConnection(String a, String b) (la conexión va en los dos sentidos), friendsOf(String name), common(String a, String b) (amigos en común) y emailOf(String name). Guarda los contactos en un Map<String, Contact> y las conexiones en un Map<String, Set<String>>. Usa un TreeSet para que los nombres salgan ordenados. Conecta a Juan con María y a Juan con Pedro.

Salida
Juan: [María, Pedro]
María: [Juan]
Amigos en común de María y Pedro: [Juan]
Correo de Pedro: pedro@example.com

Más tareas

  • Un ID único. Un método generateUserId(String email) da a cada correo nuevo un número, U001, U002 y así sucesivamente, y para un correo que ya vio devuelve el mismo número. Las mayúsculas y las minúsculas del correo cuentan igual. En la siguiente lección hay una versión con una función hash.
  • Un catálogo de libros. La clave es el ISBN, por ejemplo 978-84-376-0494-7, y el valor es el título. Agrega libros, busca uno e imprímelos todos, ordenados por ISBN.
  • Un planificador de viajes. Para cada destino, guarda una lista de actividades: «París» → «la torre Eiffel», «el Louvre». Imprime el plan en el orden en que se agregaron los destinos. ¿Qué diccionario vas a elegir?
  • Un diccionario en línea. Palabra → definición. Lee palabras hasta que llegue «fin». Para una palabra desconocida, imprime «No existe esa palabra.».
  • Notas por asignatura. Lee líneas como «Matemáticas 6», «Física 5», «Matemáticas 4», e imprime la nota media de cada asignatura, ordenadas por nombre.

Test

Ponte a prueba

1. ¿Cuándo es un HashMap mejor opción que una lista?
2. El mapa ya tiene la clave "café" con el valor 2. ¿Qué hace put("café", 3)?
3. ¿Qué devuelve get para una clave que no está?
4. Imprimes un HashMap. ¿En qué orden salen las claves?
5. ¿Qué devuelve add en un HashSet si el valor ya está?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·