Effektiva datastrukturer: Sets & Maps

Optimera kod i Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Tillämpa utrymmes-/tidskomplexitet

Nu känner vi till både utrymmes- och tidskomplexitet!

Hur använder vi den kunskapen för att skriva effektivare kod?

Genom att välja rätt datastruktur!

Ett användarhanteringssystem

Vi bygger ett användarhanteringssystem
Vi behöver kontrollera om en användare finns, givet ett användarnamn
Med en lista: komplexitet $O(n)$

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

Sets

En samling unika element med snabb sökning
$O(1)$ i genomsnittlig tidskomplexitet för att lägga till, ta bort och kontrollera om ett element finns

Förbättrad lösning för användarhanteringssystemet:

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

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

Maps

Som ett lexikon: ord (nyckel) -> definition (värde)
HashMap: $O(1)$ i genomsnittlig tidskomplexitet för operationer

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

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

Hashcode-metoden

Vad som gör dem snabba -> hashCode()
I vårt ArrayList-exempel visste vi inte indexet för användarnamnet vi letade efter
Med metoden hashcode() kan vi omvandla ett objekt till ett index att söka efter
Till exempel pavlos.2020 -> 35189

pavlos.2020 bearbetas genom hashcode och ger resultatet 35189

Indexering av element

HashMap och HashSet har en underliggande array
När vi lägger till ett element:
- Java anropar hashCode() på elementet för att få ett heltal
- Sedan används modulo på det för att få bucket-numret

Exempel:

[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!

Kollisioner

När fler än ett element hamnar i samma bucket
- Kallas en kollision
LinkedList används för bucketen
Därför säger vi $O(1)$ i genomsnitt

Kom ihåg detta

Att välja datastruktur är som att välja rätt verktyg för jobbet - en hammare (ArrayList) är perfekt för spikar men usel för skruvar (där en Set kan fungera bättre).

En öppen verktygslåda med hammare, skruvmejsel, skiftnyckel och tång sida vid sida

Nu kör vi en övning!

Optimera kod i Java