Estructuras de datos eficientes: Sets y Maps

Optimizing Code in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Aplicar complejidad de espacio/tiempo

¡Ya conocemos la complejidad en espacio y tiempo!

¿Cómo aplicamos esto para escribir código más eficiente?

¡Eligiendo la estructura de datos adecuada!

Un sistema de gestión de usuarios

Estamos creando un sistema de gestión de usuarios
Necesitamos comprobar, para un nombre de usuario dado, si el usuario existe
Usando una lista: complejidad $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Sets

Colección de elementos únicos con búsquedas rápidas
Complejidad media $O(1)$ para añadir, eliminar y comprobar si existe

Solución mejorada del sistema de usuarios:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) tiempo medio
    }
}

Maps

Como un diccionario: palabra (clave) -> definición (valor)
HashMap: complejidad media $O(1)$ para operaciones

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) tiempo medio
    }
}

Método hashCode

¿Por qué son rápidas? -> hashCode()
En nuestro ejemplo con ArrayList, no sabíamos el índice del nombre de usuario a buscar
Con el método hashcode(), podemos convertir un objeto en un índice que buscar
Por ejemplo pavlos.2020 -> 35189

pavlos.2020 procesado con hashcode, que da como resultado 35189

Indexación de elementos

HashMap y HashSet tienen un array subyacente
Al añadir un elemento:
- Java llama a hashCode() sobre tu elemento para obtener un entero
- Aplica módulo a ese entero para obtener el número de bucket

Ejemplo:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implementado por Java
1406313774 % 16 = 14 <- ¡ese es nuestro bucket!

Colisiones

Cuando más de un elemento termina en el mismo bucket
- Se llama colisión
LinkedList para el bucket
Por eso decimos $O(1)$ de media

Una idea para recordar

Elegir una estructura de datos es como escoger la herramienta adecuada: un martillo (ArrayList) va genial para clavos, pero fatal para tornillos (ahí un Set puede ir mejor).

Una caja de herramientas abierta con un martillo, destornillador, llave inglesa y alicates uno al lado del otro

¡Vamos a practicar!

Optimizing Code in Java