Efficiënte datastructuren: Sets & Maps

Code optimaliseren in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Ruimte-/tijdcomplexiteit toepassen

We kennen nu ruimte- en tijdcomplexiteit!

Hoe pas je dit toe om efficiëntere code te schrijven?

Door de juiste datastructuur te kiezen!

Een gebruikersbeheersysteem

We bouwen een gebruikersbeheersysteem
We moeten voor een gegeven gebruikersnaam checken of een gebruiker bestaat
Met een lijst: complexiteit $O(n)$

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

Sets

Een verzameling unieke elementen met snelle opzoektijden
$O(1)$ gemiddelde tijd voor toevoegen, verwijderen en bestaan controleren

Verbeterde oplossing voor gebruikersbeheer:

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

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

Maps

Zoals een woordenboek, woord (sleutel) -> definitie (waarde)
HashMap: $O(1)$ gemiddelde tijd voor bewerkingen

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

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

Hashcode-methode

Wat maakt ze snel -> hashCode()
In ons ArrayList-voorbeeld kenden we de index van de te vinden gebruikersnaam niet
Met de methode hashCode() kun je een object omzetten naar een index waar je op kunt zoeken
Bijvoorbeeld pavlos.2020 -> 35189

pavlos.2020 verwerkt via hashcode, resulteert in 35189

Elementen indexeren

HashMap en HashSet hebben een onderliggende array
Wanneer we een element toevoegen:
- Java roept hashCode() aan op je element om een geheel getal te krijgen
- Het neemt modulo daarvan om het bucket-nummer te bepalen

Voorbeeld:

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

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- dat is onze bucket!

Collisions

Wanneer meer dan één item in dezelfde bucket belandt
- Dat heet een collision
LinkedList voor de bucket
Daarom zeggen we $O(1)$ gemiddeld

Een tip om te onthouden

Een datastructuur kiezen is als het juiste gereedschap kiezen: een hamer (ArrayList) is top voor spijkers maar waardeloos voor schroeven (waar een Set beter kan werken).

Een open gereedschapskist met naast elkaar een hamer, schroevendraaier, moersleutel en tang

Laten we oefenen!

Code optimaliseren in Java