Strutture dati efficienti: Set e Map

Ottimizzazione del codice in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Applicare la complessità spazio/tempo

Ora conosciamo la complessità in spazio e tempo!

Come applicarla per scrivere codice più efficiente?

Scegliendo la struttura dati giusta!

Un sistema di gestione utenti

Stiamo creando un sistema di gestione utenti
Per un dato username, dobbiamo verificare se l'utente esiste
Usando una lista: complessità $O(n)$

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

Set

Collezione di elementi unici con ricerche rapide
$O(1)$ in media per aggiungere, rimuovere e verificare l'esistenza di un elemento

Soluzione migliorata per la gestione utenti:

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

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

Map

Come un dizionario: parola (chiave) -> definizione (valore)
HashMap: $O(1)$ in media per le operazioni

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

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

Metodo hashCode

Cosa le rende veloci -> hashCode()
Nell'esempio con ArrayList, non conoscevamo l'indice dell'username da trovare
Con il metodo hashcode() convertiamo un oggetto in un indice cercabile
Ad esempio pavlos.2020 -> 35189

"pavlos.2020" elaborato con hashcode, risultato 35189

Indicizzare gli elementi

HashMap e HashSet hanno un array sottostante
Quando aggiungiamo un elemento:
- Java chiama hashCode() sull'elemento per ottenere un intero
- Applica il modulo su quel valore per ottenere il numero di bucket

Esempio:

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

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- questo è il nostro bucket!

Collisioni

Quando più elementi finiscono nello stesso bucket
- Si chiama collisione
LinkedList per il bucket
Per questo diciamo $O(1)$ in media

Da ricordare

Scegliere la struttura dati giusta è come scegliere l'attrezzo giusto: un martello (ArrayList) va bene per i chiodi, ma è pessimo per le viti (meglio un Set).

Una cassetta degli attrezzi aperta con martello, cacciavite, chiave inglese e pinze affiancati

Esercitiamoci!

Ottimizzazione del codice in Java