Belső működés

A Collections Framework teljesítményét a hashCode/equals szerződés, a hashing stratégia, az ütközéskezelés és a Big-O viselkedés határozza meg.

1. Definíció

A collections belső működése azt írja le, hogyan tárolja és keresi vissza az adatokat például egy HashMap, HashSet vagy ArrayList. Interjún ez azért fontos, mert nem elég azt mondani, hogy egy művelet “gyors”; tudni kell, hogy milyen feltételek mellett marad gyors, és mikor romlik a teljesítmény. Ez a téma a Collections Framework mögötti adatstruktúrákhoz kapcsolódik: hash table, bucket, linked structure, fa alapú rendezés és indexelt tömb. A jó válaszok mindig összekötik az API-szintű használatot a belső reprezentációval.

2. Alapfogalmak

Fogalom	Jelentés	Miért fontos
equals()	Érték szerinti egyenlőség	Ha két objektum egyenlő, akkor a HashSet és HashMap logikája ezt fogja használni duplikátumellenőrzéshez.
hashCode()	Bucket kiválasztásához használt egész szám	Egyenlő objektumoknak kötelező ugyanazt a hashCode-ot adniuk.
Hashing	Kulcsból numerikus hash számítása	Jó eloszlás esetén kevés collision keletkezik.
Collision	Több kulcs ugyanabba a bucketbe kerül	A belső szerkezet ekkor plusz összehasonlításokat végez.
Big-O	Műveletek elméleti költsége	Átlagos és worst-case komplexitást külön kell kezelni.

• A HashMap és HashSet átlagosan O(1) keresést tudnak, de csak akkor, ha a hash eloszlás jó és az equals() korrekt.
• A TreeMap és TreeSet rendezett struktúrák, ezért tipikusan O(log n) műveleteket adnak, cserébe rendezést és range query képességet nyersz.
• Az ArrayList index szerinti elérése O(1), viszont közepére beszúrni drága, mert elemeket kell másolni.
• A hash alapú struktúrák teljesítménye nem csak az elemszámtól, hanem a kulcsok minőségétől és a load factor értékétől is függ.

3. Gyakorlati használat

A(z) Belső működés témában a legfontosabb gyakorlati kérdés mindig az, hogy milyen use-case-re választasz eszközt. A jó interjúválasz itt nem csak azt mondja meg, mit lehet csinálni, hanem azt is, mikor érdemes és mikor nem.

• Használj immutable kulcsokat HashMap-ben. Ha a kulcs mezői változnak a beszúrás után, a map “elveszítheti” az elemet, mert már más bucketbe tartozna.
• Override-old együtt az equals() és hashCode() metódusokat, tipikusan ugyanazokra a mezőkre építve.
• Interjún mondd ki az “average vs worst case” különbséget: HashMap#get() átlagban O(1), de rossz hash eloszlásnál romolhat.
• Rendezett iterációhoz ne HashMap-et erőltesd, hanem LinkedHashMap-et vagy TreeMap-et válassz az igény szerint.
• Nagy mennyiségű adatnál a pre-sizing csökkentheti a rehash költségét.

4. Kód példák

Egyszerű példa

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

class UserKey {
    private final String email;

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

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

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

public class HashMapExample {
    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")));
        // Anna
    }
}

Haladó példa

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 obj) {
            return obj instanceof Key other && id.equals(other.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"; // rossz ötlet: a hash már más lenne

        System.out.println(map.get(key));            // gyakran null
        System.out.println(map.containsKey(key));    // false lehet
    }
}

A kódpéldák interjún azért hasznosak, mert megmutatják, hogy a fogalmi szintű tudást le tudod fordítani konkrét API-használatra. Ha röviden el tudod magyarázni, miért így írod a példát, az általában többet ér, mint egy túlbonyolított demo.

5. Trade-offok

Szempont	Előny	Hátrány
Hash alapú tárolás	Átlagosan nagyon gyors lookup és insert	Rossz hash eloszlás esetén collision miatt romolhat
Rendezett struktúra	Determinista sorrend és range query	O(log n) költség, nagyobb konstans faktor
Komplex kulcs objektum	Gazdag domain modell	Hibás equals/hashCode könnyen rejtett bugokat okoz

6. Gyakori hibák

• ❌ Rossz: equals() override, de hashCode() nincs override-olva. ✅ Helyes: A két metódust mindig együtt kezeld, ugyanazokra a mezőkre építve.
• ❌ Rossz: Mutable objektumot használsz HashMap kulcsként. ✅ Helyes: Kulcsnak immutable típust válassz, vagy legalább a hash-ben részt vevő mezőket ne módosítsd.
• ❌ Rossz: Minden collectionre automatikusan O(1)-et mondasz. ✅ Helyes: Mindig nevezd meg a konkrét implementációt és az average/worst-case viselkedést.

7. Senior szintű meglátások

Senior szinten fontos megérteni, hogy a Big-O önmagában kevés. A cache-locality, a memória overhead és az objektumallokáció is erősen befolyásolja a valós teljesítményt.

Gyakori follow-up kérdés interjún: miért lehet egy ArrayList gyorsabb iterációra, mint egy LinkedList, még akkor is, ha a linked struktúra elméletben jó bizonyos beszúrásokra? A válasz általában a CPU cache és a pointer chasing körül forog.

Másik senior téma a hash flooding és a rossz kulcstervezés. Ha a kulcsok hash-e erősen ütközik, nem csak lassulás jelenik meg, hanem bizonyos támadási felületek is előkerülhetnek hálózati input esetén.

Tipikus follow-up interjúkérdések:

• Hogyan magyaráznád el röviden a(z) Belső működés témát egy junior fejlesztőnek?
• Milyen trade-offot látsz a(z) Belső működés kapcsán valós projektben?
• Milyen tipikus production hibát tudsz ehhez a témához kötni?

8. Szószedet

Kifejezés	Jelentés
bucket	A hash table belső rekesze, ahová egy kulcs hash alapján kerül.
collision	Amikor két különböző kulcs ugyanabba a bucketbe esik.
rehash	A tábla újraméretezése és az elemek újraosztása.
load factor	A töltöttségi küszöb, ami után a hash tábla növekszik.
worst case	Az a legrosszabb helyzet, amikor a művelet költsége a legnagyobb.

9. Gyorsreferencia

• HashMap: átlagosan get/put = O(1), rossz esetben romolhat.
• TreeMap: get/put = O(log n), de rendezett.
• ArrayList#get(index): O(1), középre beszúrás: O(n).
• equals() és hashCode() szerződése kritikus hash alapú struktúráknál.
• Kulcsnak preferáld az immutable objektumot.

Ha interjún elakadsz, a(z) Belső működés témánál mindig térj vissza a három alapelvhez: pontos definíció, tipikus use-case, és a legfontosabb trade-off vagy hiba.