Efektivní datové struktury: Sets a Maps

Optimalizace kódu v Javě

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Využití prostorové a časové složitosti

Teď už známe prostorovou a časovou složitost!

Jak tyto znalosti využít k psaní efektivnějšího kódu?

Výběrem správné datové struktury!

Systém pro správu uživatelů

Vytváříme systém pro správu uživatelů
Potřebujeme pro dané uživatelské jméno zjistit, jestli uživatel existuje
Při použití seznamu: složitost $O(n)$

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

Sets

Kolekce unikátních prvků s rychlým vyhledáváním
Průměrná časová složitost $O(1)$ pro přidání, odebrání a ověření existence prvku

Vylepšené řešení systému pro správu uživatelů:

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

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

Maps

Podobně jako slovník: slovo (klíč) -> definice (hodnota)
HashMap: průměrná časová složitost operací $O(1)$

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

Co je dělá tak rychlými -> hashCode()
V našem příkladu s ArrayList jsme neznali index hledaného uživatelského jména
Pomocí metody hashcode() můžeme převést objekt na index, podle kterého vyhledáváme
Například pavlos.2020 -> 35189

Zpracování pavlos.2020 metodou hashcode, výsledek 35189

Indexování prvků

HashMap a HashSet mají uvnitř pole
Když přidáváme prvek:
- Java zavolá hashCode() na daný prvek, aby získala celé číslo
- Poté na výsledek použije modulo, aby zjistila číslo přihrádky (bucketu)

Příklad:

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

Kolize

Když skončí více prvků ve stejné přihrádce
- Tomu se říká kolize
Pro danou přihrádku se použije LinkedList
Proto říkáme, že $O(1)$ platí v průměru

Co si zapamatovat

Výběr datové struktury je jako výběr správného nástroje na danou práci – kladivo (ArrayList) je skvělé na hřebíky, ale na šrouby se moc nehodí (tam by mohla lépe posloužit Set).

Otevřená sada nářadí s kladivem, šroubovákem, klíčem a kleštěmi vedle sebe

Pojďme cvičit!

Optimalizace kódu v Javě