Belső működés

A Collections Framework valódi teljesítményét az equals() / hashCode() szerződés, a hashing stratégia, az ütközéskezelés, az újraméretezés, a memóriaelrendezés és a cache-viselkedés határozza meg.

---

1. Definíció

A collections belső működése azt írja le, hogyan tárolja, keresi vissza és mozgatja az adatokat például egy HashMap, HashSet, TreeMap vagy ArrayList. Ez azért fontos, mert nem elég azt mondani, hogy egy művelet „gyors”; azt is tudni kell, miért gyors, milyen feltételek mellett marad az, és mikor romlik le.

API-szinten a használat egyszerűnek tűnik:

• map.get(kulcs)
• set.contains(ertek)
• list.add(elem)
• list.get(index)

A háttérben azonban nagyon különböző tárolási modellek dolgoznak:

• tömbök
• láncolt struktúrák
• hash bucketek
• kiegyensúlyozott fák
• comparator alapú rendezés

Az erős interjúválasz mindig összeköti a publikus API-t a rejtett reprezentációval. Például:

• a HashMap#get() azért gyors átlagban, mert a hash egy bucketre szűkíti a keresést
• az ArrayList#get(index) azért gyors, mert közvetlen indexelt tömbhozzáférés
• a TreeMap#get() lassabb lehet, mint a HashMap#get(), viszont rendezett navigációt és tartomány-lekérdezéseket ad

Ennek a témának a lényege tehát nem a trivia, hanem a háttérmechanika megértése.

---

2. Alapfogalmak

2.1 Az `equals()` és `hashCode()` szerződése

A hash alapú kollekciók két metódus együttműködésére épülnek:

• az equals() a logikai egyenlőséget dönti el
• a hashCode() az elsődleges bucketbe tereléshez kell

A fő szabály:

Ha két objektum equals() szerint egyenlő, akkor kötelező, hogy ugyanazt a hashCode()-ot adják vissza.

Ha ez sérül:

• a HashSet logikai duplikátumokat fogadhat be
• a HashMap#get(kulcs) nem találhat meg korábban beszúrt elemet
• a contains() eredményei meglepőek és inkonzisztensek lehetnek

Ezért jó kulcsok gyakran a recordok: automatikusan értékalapú equals() és hashCode() implementációt kapnak.

2.2 Hashing és bucket-választás

Hash táblában a keresés nem úgy működik, hogy az elejétől végignézi az összes elemet. Ehelyett:

1. kiszámítja a kulcs hash értékét
2. szétteríti vagy keveri a biteket
3. ebből bucket indexet képez
4. csak azon a bucketen belül keres tovább

Ez adja az átlagos $O(1)$ viselkedés alapját.

De a „konstans idő” nem azt jelenti, hogy ingyenes:

• a hash-t így is ki kell számolni
• collision esetén összehasonlítások futnak
• az átméretezés alkalmanként drága tüskéket okoz
• a memória lokalitás a valós CPU-költséget is befolyásolja

2.3 Ütközéskezelés

Collision akkor történik, amikor két különböző kulcs ugyanabba a bucketbe kerül.

Ez önmagában még nem hiba. Azt jelenti, hogy a mapnek többletmunkát kell végeznie a bucketen belül.

Régebben a bucket belső szerkezete tipikusan láncolt lista volt. Java 8 óta az erősen ütköző bucketek fásíthatók Red-Black Tree-vé.

Ez azt eredményezi, hogy:

• az átlagos viselkedés megmarad hash táblának
• a legrosszabb eset lineárisból logaritmikussá javulhat
• a hash flooding típusú támadások kevésbé fájdalmasak

2.4 Load factor és újraméretezés

A hash alapú struktúrák nem várják meg, hogy teljesen megteljen a belső tömb.

A HashMap alapértékei:

• kezdeti kapacitás: 16
• load factor: 0.75

A növekedési küszöb képlete:

$$ threshold = capacity \times loadFactor $$

Tehát 16 kapacitásnál az első növekedés 12 bejegyzés után jön.

Az újraméretezés azt jelenti, hogy:

• új, nagyobb tábla jön létre
• a bejegyzések újraosztódnak
• a bucket-útvonalak megváltozhatnak

Ezért fontos az előre méretezés nagy tömeges beszúrásnál.

2.5 Tömb-alapú vs csomópont-alapú tárolás

Az ArrayList összefüggő tömbben tárol referenciákat. A LinkedList minden elemhez külön csomópont-objektumot hoz létre, amely referenciákkal kapcsolódik a többihez.

Ennek jelentős következményei vannak:

Ezért félrevezető lehet csak az elméleti komplexitás:

• a LinkedList papíron jól nézhet ki bizonyos műveleteknél
• a ArrayList mégis sokszor gyorsabb a gyakorlatban a CPU-k memóriamodelle miatt

2.6 Fa alapú rendezés

A TreeMap és TreeSet nem hashinggel, hanem kiegyensúlyozott fa struktúrával dolgozik.

Ez azt jelenti, hogy:

• nincs bucket-logika
• nincs hash alapú elérés
• természetes vagy comparator szerinti sorrend van
• a műveletek tipikusan $O(\log n)$ költségűek

Cserébe olyan képességeket kapsz, mint:

• firstKey()
• lastKey()
• floorKey()
• ceilingKey()
• subMap()

2.7 Big-O vs valódi futásidő

A fejlesztők sokszor megállnak a komplexitási címkénél. Ez hasznos, de nem elég.

A valódi futásidőt befolyásolja még:

• a memória allokációs minta
• az elágazásbecslés
• a cache miss-ek száma
• az objektumheader overhead
• a comparator költsége
• a kulcsok hash eloszlásának minősége

Ezért a jó válasz nem csak annyi, hogy „a HashMap $O(1)$”, hanem inkább:

„A HashMap átlagban $O(1)$ jól eloszló hash-ek mellett, de a valós teljesítmény függ a kulcsok minőségétől, a resize gyakoriságától és a collision viselkedéstől is.”

---

3. Gyakorlati használat

Az internals mögötti gyakorlati kérdés valójában ez:

Melyik implementáció illik a tényleges terheléshez és hibamódhoz?

3.1 Szabályok, amelyek valódi hibákat előznek meg

• használj immutábilis kulcsokat HashMap-ben
• az equals() és hashCode() mindig együtt készüljön el
• ne építs a HashMap iterálási sorrendjére
• nagy tömeges betöltésnél előre méretezz mapet és listát
• rendezett struktúrát csak akkor válassz, ha a sorrend valódi üzleti igény

3.2 A kulcstervezés gyakorlati következményei

A jó kulcs tipikusan:

• immutábilis mezőkre épül
• stabil egyenlőségi szemantikával bír
• az objektum élete során stabil hash-t ad
• ésszerűen jól szóródó értékeket eredményez

A rossz kulcstervezés következménye lehet:

• eltűnő lookup
• duplikátumnak tűnő bejegyzések
• throughput-romlás
• nehezen reprodukálható production bugok

3.3 Mikor kevés az átlagos eset?

Interjún és teljesítménybeszélgetésben mondd ki külön:

• average case
• amortized case
• worst case

Például:

• az ArrayList#add(e) végére amortizált $O(1)$
• a HashMap#get(k) átlagos $O(1)$
• a TreeMap#get(k) pedig tipikusan $O(\log n)$

Ez a különbségtétel sokkal erősebb tudást jelez, mint egyetlen szám bedobása.

3.4 Mikor lesz a sorrend a helyesség része?

A sorrend nem mindig csak kozmetika.

Számíthat például:

• determinisztikus teszteknél
• stabil API válaszoknál
• felhasználói listáknál
• reprodukálható logoknál
• cache kiléptetési logikánál

Ha a sorrend számít, olyan struktúrát válassz, amely garantálja is.

3.5 Előre méretezés mint workload-döntés

Érdemes előre méretezni például akkor, ha:

• nagy fájlt parse-olsz
• CSV vagy JSON tömeges import történik
• induláskor cache-t építesz fel
• nagy adathalmazokat csoportosítasz
• tight loopban ideiglenes mapeket hozol létre

Ha hozzávetőlegesen tudod az elemszámot, az előre méretezés egyszerű és gyakran látványos nyereség.

---

4. Kód példák

Alappélda — stabil hash kulcs

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

final class UserKey {
    private final String email;

    UserKey(String email) {
        this.email = email;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (!(other instanceof UserKey userKey)) {
            return false;
        }
        return Objects.equals(email, userKey.email);
    }

    @Override
    public int hashCode() {
        return Objects.hash(email);
    }
}

public class StableKeyDemo {
    public static void main(String[] args) {
        Map<UserKey, String> users = new HashMap<>();
        users.put(new UserKey("anna@example.com"), "Anna");

        System.out.println(users.get(new UserKey("anna@example.com")));
    }
}

Ez azért működik, mert a lookup ugyanazt a logikai hash-utat és egyenlőségi döntést reprodukálja, mint a beszúrás.

Haladó példa — módosítható kulcs csapdája

import java.util.HashMap;
import java.util.Map;

public class MutableKeyTrap {
    static class Key {
        String id;

        Key(String id) {
            this.id = id;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof Key key && id.equals(key.id);
        }

        @Override
        public int hashCode() {
            return id.hashCode();
        }
    }

    public static void main(String[] args) {
        Map<Key, String> map = new HashMap<>();

        Key key = new Key("A-1");
        map.put(key, "stored");

        key.id = "B-2";

        System.out.println(map.get(key));
        System.out.println(map.containsKey(key));
    }
}

A bejegyzés fizikailag még bent van a mapben, de a kulcs új hash-e már nem a megfelelő buckethez visz.

Haladó példa — comparator inkonzisztencia

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

record Person(String id, String name) {}

public class ComparatorTrap {
    public static void main(String[] args) {
        Comparator<Person> byNameOnly = Comparator.comparing(Person::name);
        Set<Person> people = new TreeSet<>(byNameOnly);

        people.add(new Person("1", "Alice"));
        people.add(new Person("2", "Alice"));

        System.out.println(people.size());
    }
}

Ha a comparator szerinti egyenlőség tágabb, mint a logikai egyenlőség, a struktúra a comparatornak engedelmeskedik.

Gyakorlati példa — map előre méretezése

import java.util.HashMap;
import java.util.Map;

public class PresizingExample {
    public static void main(String[] args) {
        int expectedEntries = 10_000;
        int capacity = (int) (expectedEntries / 0.75f) + 1;

        Map<String, Integer> counts = new HashMap<>(capacity);
    }
}

Ez csökkenti az ismételt rehashing esélyét nagy tömeges beszúráskor.

---

5. Trade-offok

Nincs univerzálisan legjobb struktúra. Mindegyik valamilyen workload felé torzít.

---

6. Gyakori hibák

1. `equals()` override `hashCode()` nélkül

❌ Hibás mentális modell: „az egyenlőség önmagában elég”

✅ Helyes modell: a hash alapú struktúrák a két metódus együttműködésére épülnek.

2. Módosítható kulcs hash struktúrában

Ha a hash-ben vagy egyenlőségben részt vevő mező megváltozik beszúrás után, a lookup megbízhatatlanná válik.

3. Mindenre automatikusan $O(1)$-et mondani

Ennek csak akkor van értelme, ha a konkrét implementációt és az ehhez tartozó feltételeket is kimondod.

4. Comparator konzisztencia figyelmen kívül hagyása

Ha a comparator szerint két érték azonos helyre esik, a rendezett struktúra annak megfelelően fog viselkedni, nem a te intuíciód szerint.

5. Iterálási sorrend összekeverése a rendezett sorrenddel

A LinkedHashMap beszúrási vagy hozzáférési sorrendet tart, a TreeMap comparator szerinti sorrendet, a HashMap pedig nem ordering API.

6. Memória overhead alábecslése

Több millió node-alapú elem teljesen másképp viselkedik, mint több millió tömb-alapú referencia.

---

7. Mélymerülés

7.1 Miért veri gyakran az `ArrayList` a `LinkedList`-et?

A tankönyv szerint a linked list sok műveletben jól hangzik. A valódi CPU-k viszont másképp működnek.

Az ArrayList gyakran azért nyer, mert:

• az adatok folytonosak
• a prefetch jól működik
• kisebb az objektum overhead
• bejáráskor nincs pointer chasing

A LinkedList gyakran azért veszít, mert:

• minden csomópont külön objektum
• a referenciák szétszóródnak a heapen
• a cache miss-ek dominálhatják a futásidőt

7.2 Hash flooding és a `HashMap` védelmi fejlődése

A rosszul eloszló hash-ek hosszú bucket-láncokat okozhatnak. Ellenséges input mellett ez akár DoS-jellegű problémává is válhat.

A Java 8 ezt részben úgy kezelte, hogy nagy collision nyomás mellett a bucketeket fává alakítja.

Ez nem helyettesíti a jó kulcstervezést, de csökkenti a patológiás esetek kárát.

7.3 A fail-fast iterator hibadetektor, nem thread-safety mechanizmus

Sok kollekció módosítás-számlálóval figyeli, hogy a bejárás közben történt-e strukturális módosítás.

Ez vezet a ConcurrentModificationException-höz sok hibás módosítási mintánál.

Fontos árnyalat:

• a fail-fast csak best-effort
• nem szinkronizációs mechanizmus
• nem teszi thread-safe-fé a kollekciót

7.4 A memória overhead is teljesítmény

A teljesítmény nem csak CPU idő.

Számít még:

• az objektumszám
• a GC nyomás
• a pointer chasing
• a retained heap méret

Ezért tudnak a „papíron szép” struktúrák gyengén teljesíteni production környezetben.

7.5 Az internals ismerete jobb API-tervezéshez vezet

Ha érted a belső működést, jobb API-kat írsz:

• nem adsz ki List-et, ha csak iteráció kell
• tudod, mikor éri meg immutable másolatot visszaadni
• nem reflexből, hanem céllal választasz map implementációt
• pontosan dokumentálod a sorrendi garanciákat

Ez a téma igazi értéke: nem a részletek bemagolása, hanem a jobb mérnöki döntések meghozatala.

---

8. Interjúkérdések

Miért csak átlagosan $O(1)$ a `HashMap#get()` és nem garantáltan?

Mert a művelet függ a hash eloszlásától, az ütközésektől és a bucket belső szerkezetétől is. Rossz esetben több munkát kell végezni egy bucketen belül.

Miért tud egy `HashMap` „elveszíteni” egy elemet, miközben fizikailag még bent van?

Mert ha egy módosítható kulcs a beszúrás után megváltozik, az új hash/equality út már nem fog megegyezni az eredeti bucketbe helyezéssel.

Miért lehet gyorsabb az `ArrayList`, mint a `LinkedList`, még drágának tűnő műveleteknél is?

Mert a folytonos memória és a cache lokalitás a gyakorlatban sokszor fontosabb, mint a linked csomópontok elméleti előnye.

Mi a leggyakoribb production hiba, ami a kollekciók belső működéséhez köthető?

A hibás equals() / hashCode() szerződés és a módosítható map kulcsok az egyik leggyakoribb oka a rejtett lookup- és deduplikációs problémáknak.

---

9. Szószedet

---

10. Gyorsreferencia

• a HashMap gyors átlagos lookupot ad, de nem minden körülmények között konstansat
• az equals() és hashCode() egy közös szerződés a hash alapú struktúrákhoz
• a módosítható kulcs veszélyes HashMap-ben és HashSet-ben
• a TreeMap a sebesség egy részét rendezettségre és navigációra cseréli
• az ArrayList cache-barát, ezért jó alapértelmezett lista
• a LinkedList ritkán a legjobb általános célú List
• az előre méretezés csökkenti a resize és rehash költségét tömeges terhelésnél
• a comparator konzisztencia számít TreeSet és TreeMap esetén
• a fail-fast iterator sok hibás módosítást jelez, de nem thread-safety mechanizmus
• a belső működés megértése jobb API- és teljesítménydöntésekhez vezet

Ha interjún elakadsz, a Belső működés témánál mindig térj vissza három pontra: pontos definíció, domináns use-case, és a legfontosabb hibamód.