Efficiënte datastructuren: Sets & Maps

Code optimaliseren in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Ruimte-/tijdcomplexiteit toepassen

We kennen nu ruimte- en tijdcomplexiteit!

Hoe passen we dit toe om efficiënter te coderen?

Door de juiste datastructuur te kiezen!

Een gebruikersbeheersysteem

We bouwen een gebruikersbeheersysteem
We moeten voor een 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 opzoeking
$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) gemiddelde tijd
    }
}

Maps

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

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

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

Hashcode-methode

Wat dit snel maakt -> hashCode()
In ons ArrayList-voorbeeld kenden we de index van de te zoeken gebruikersnaam niet
Met de methode hashCode() kunnen we een object omzetten naar een index om op te zoeken
Bijvoorbeeld pavlos.2020 -> 35189

pavlos.2020 verwerkt via hashcode, resultaat 35189

Elementen indexeren

HashMap en HashSet hebben een onderliggende array
Als we een element toevoegen:
- Java roept hashCode() aan op je element om een geheel getal te krijgen
- Daarop wordt modulo toegepast om het bucketnummer te krijgen

Voorbeeld:

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

"optimizingCodeInJava" -> 1406313774 // Geïmplementeerd door Java
1406313774 % 16 = 14 <- dat is onze bucket!

Collisions

Als meer dan één item in dezelfde bucket komt
- Heet een collision
LinkedList per bucket
Daarom zeggen we $O(1)$ gemiddeld

Onthouden

De juiste datastructuur kiezen is als het juiste gereedschap kiezen: een hamer (ArrayList) is top voor spijkers, maar slecht voor schroeven (waar een Set beter werkt).

Gereedschap

Laten we oefenen!

Code optimaliseren in Java