Strutture dati efficienti: Set e Map

Ottimizzazione del codice in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Applicare spazio/tempo

Ora conosciamo la complessità di spazio e tempo!

Come applichiamo tutto questo 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
Con 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 lookup veloce
$O(1)$ in media per aggiungere, rimuovere e verificare l’esistenza

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 sapevamo l’indice dell’username da cercare
Con hashcode() convertiamo un oggetto in un indice ricercabile
Per esempio pavlos.2020 -> 35189

pavlos.2020 elaborato con hashcode, risultato 35189

Indicizzare gli elementi

HashMap e HashSet usano un array sottostante
Quando aggiungi un elemento:
- Java chiama hashCode() sull'elemento per ottenere un intero
- Applica il modulo per ricavare il numero del 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

Nota 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 (dove un Set può funzionare meglio).

Strumenti

Ayo berlatih!

Ottimizzazione del codice in Java