Structuri de date eficiente: Set-uri și Map-uri

Optimizarea codului în Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Aplicarea complexității spațiu/timp

Acum știm despre complexitatea spațiu-timp!

Cum aplicăm această înțelegere pentru a scrie cod mai eficient?

Alegând structura de date potrivită!

Un sistem de gestionare a utilizatorilor

Construim un sistem de gestionare a utilizatorilor
Trebuie să verificăm dacă un utilizator cu un nume dat există
Folosind o listă: complexitate $O(n)$

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

Set-uri

O colecție de elemente unice cu căutare rapidă
Complexitate medie $O(1)$ pentru adăugare, ștergere și verificarea existenței unui element

Soluție îmbunătățită pentru sistemul de gestionare a utilizatorilor:

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

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

Map-uri

Ca un dicționar: cuvânt (cheie) -> definiție (valoare)
HashMap: complexitate medie $O(1)$ pentru operații

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

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

Metoda hashcode

Ce le face rapide -> hashCode()
În exemplul cu ArrayList, nu știam indexul numelui de utilizator căutat
Folosind metoda hashcode(), putem converti un obiect într-un index de căutare
De exemplu, pavlos.2020 -> 35189

pavlos.2020 procesat prin hashcode, rezultând 35189

Indexarea elementelor

HashMap și HashSet au un array subiacent
Când adăugăm un element:
- Java apelează hashCode() pe elementul tău pentru a obține un întreg
- Aplică modulo pe acesta pentru a obține numărul bucket-ului

Exemplu:

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

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!

Coliziuni

Când mai multe elemente ajung în același bucket
- Se numește coliziune
LinkedList pentru bucket
De aceea spunem $O(1)$ în medie

O idee de reținut

Alegerea structurii de date e ca alegerea uneltei potrivite pentru o lucrare - un ciocan (ArrayList) e ideal pentru cuie, dar nepotrivit pentru șuruburi (unde un Set ar funcționa mai bine).

O cutie de scule deschisă cu ciocan, șurubelniță, cheie fixă și clește alăturate

Hai să exersăm!

Optimizarea codului în Java