Effektiva datastrukturer: Sets & Maps

Optimera kod i Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Tillämpa tids- och rymdkomplexitet

Nu vet vi vad tids- och rymdkomplexitet är!

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 ett givet användarnamn finns
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 uppslagstid
$O(1)$ 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)$ 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

Det som gör dem snabba -> hashCode()
I exemplet med ArrayList kände vi inte till indexet för användarnamnet vi sökte
Med metoden hashcode() kan vi omvandla ett objekt till ett index att slå upp
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
- Det anropar modulo på ovanstående 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

Något att ha i minnet

Att välja datastruktur är som att välja rätt verktyg för jobbet – en hammare (ArrayList) är utmärkt för spik men sämre för skruvar (där ett Set kan passa bättre).

Tools

Nu kör vi en övning!

Optimera kod i Java