Implementációk

Mélymerülés az ArrayList, LinkedList, HashMap, TreeMap, HashSet és LinkedHashMap implementációkba — mikor melyiket használd, teljesítményjellemzők és kritikus trade-offok.

---

1. Definíció

Mi ez?

A JCF konkrét implementációkat biztosít az interfészeihez. Mindegyik meghatározott kompromisszumokat köt memória, hozzáférési sebesség, rendezés és szálbiztonság között. A megfelelő implementáció kiválasztása az egyik legjelentősebb teljesítménybeli döntés Java-ban.

Miért fontos?

Ha LinkedList-et használsz ott, ahol ArrayList elegendő lenne, 10×+ lassulást okozhatsz véletlenszerű hozzáférésnél. Ha HashMap helyett TreeMap-et választasz, minden műveletnél O(log n) pluszköltséget viselsz, de elveszted a rendezettséget. Ezek a döntések nagy léptékben összeadódnak.

Hol helyezkednek el?

List → ArrayList, LinkedList
Set  → HashSet, LinkedHashSet, TreeSet
Map  → HashMap, LinkedHashMap, TreeMap

---

2. Alapfogalmak

2.1 `ArrayList`

Átméretezhető tömb (Object[]) által tárolva. Alapértelmezett kezdeti kapacitás: 10.

2.2 `LinkedList`

Kétszeresen láncolt lista — minden csomópont prev/next referenciákat tartalmaz. Megvalósítja a List és a Deque interfészt is.

2.3 `HashMap`

Hash tábla vödörként funkcionáló tömbbel. Alapértelmezett kapacitás: 16, load factor: 0.75.

Java 8+: ≥8 bejegyzést tartalmazó vödrök linked list-ről Red-Black Tree-re váltanak (O(log n) legrosszabb eset).

2.4 `LinkedHashMap`

A HashMap-et bővíti egy kétszeresen láncolt listával az összes bejegyzésen keresztül:

• Beszúrási sorrend (alapértelmezett)
• Hozzáférési sorrend (new LinkedHashMap<>(cap, 0.75f, true)) → LRU cache

Ugyanolyan O(1) mint a HashMap, kis konstans overhead-del.

2.5 `TreeMap`

Red-Black Tree — önkiegyensúlyozó BST. Minden művelet O(log n). Kulcsok természetes sorrendben vagy megadott Comparator szerint rendezve. null kulcsok nem engedélyezettek.

2.6 `HashSet`

HashMap<E, PRESENT> által tárolva (PRESENT = statikus dummy Object). Minden művelet a belső map-re delegál — azonos teljesítmény.

2.7 `ArrayDeque`

Az ArrayDeque általában a legjobb általános célú választás queue és stack jellegű használatra.

Sokszor veri a LinkedList-et, mert tömörebben tárol és jobban kihasználja a cache lokalitást.

2.8 Terhelés alapján válassz, ne megszokásból

Az implementációválasztást az uralkodó műveletekhez kell igazítani:

• sok random olvasás → ArrayList
• sor / verem jellegű kétvéges műveletek → ArrayDeque
• egyszerű kulcs alapú lookup → HashMap
• stabil iterálási sorrend → LinkedHashMap
• rendezett navigáció → TreeMap

2.9 A specializált implementáció sokszor még jobb választás

Az igazán jó választás néha nem a “szokásos” implementációk egyike. Az EnumMap és az EnumSet nagyon kompakt és gyors, ha a kulcsok vagy értékek enumok. Az IdentityHashMap referenciaazonosság alapján hasonlít, nem equals() szerint, ezért csak speciális identitás-alapú esetekben helyes. A ConcurrentHashMap pedig megosztott, módosítható map-eknél jobb alapértelmezés konkurens kódban, mert sokkal jobban skálázódik, mint egy durva zárolással körbetekert HashMap.

Ez interjún is jó jelzés: először a megfelelő absztrakciót válaszd ki, utána a helyes standard implementációt, végül nézd meg, hogy egy specializált implementáció még jobban illeszkedik-e a domainhez.

---

3. Gyakorlati használat

ArrayList vs LinkedList

Ellenintuitív: Az ArrayList tipikus méreteknél még közepén való beillesztésnél is veri a LinkedList-et a CPU cache lokalitás miatt.

HashMap vs LinkedHashMap vs TreeMap

Gyakorlati választási ellenőrzőlista

Mielőtt konkrét implementációt választasz, kérdezd meg:

1. A sorrend része-e a helyes működésnek?
2. Kell-e tartomány alapú navigáció?
3. Számít-e a memória overhead?
4. Az olvasás, beszúrás vagy törlés a domináns művelet?
5. Szekvenciális, kulcs-érték vagy kétvégű adatszerkezetről van szó?

---

4. Kód példák

Alap példa — ArrayList vs LinkedList

List<Integer> arrayList = new ArrayList<>(100_000);
List<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 100_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// O(1)
int a = arrayList.get(50_000);

// O(n) — ~50k csomópont bejárása
int b = linkedList.get(50_000);

// LinkedList csak a végeken ragyog
Deque<Integer> deque = (Deque<Integer>) linkedList;
deque.addFirst(999); // O(1)

Haladó példa — LRU Cache LinkedHashMap-mel

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LruCache(int maxSize) {
        super(maxSize, 0.75f, true); // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Használat
LruCache<Integer, String> cache = new LruCache<>(3);
cache.put(1, "egy"); cache.put(2, "kettő"); cache.put(3, "három");
cache.get(1);         // 1-es kulcs hozzáférés → "legújabb" végre kerül
cache.put(4, "négy"); // kizárja a 2-es kulcsot (legrégebben használt)
System.out.println(cache.keySet()); // [3, 1, 4]

Haladó példa — TreeMap tartomány lekérdezések

TreeMap<String, Integer> freq = new TreeMap<>();
List.of("banán", "alma", "cseresznye", "avokádó", "áfonya")
    .forEach(w -> freq.merge(w, 1, Integer::sum));

System.out.println(freq.firstKey());                // áfonya
System.out.println(freq.subMap("b", "c").keySet()); // [banán]
System.out.println(freq.floorKey("barack"));        // banán

Tipikus hiba — Módosítható HashMap kulcs

// ❌ Módosítható kulcs megtöri a HashMap-et
class ModosithatoKulcs {
    int ertek;
    public int hashCode() { return ertek; }
    public boolean equals(Object o) { return o instanceof ModosithatoKulcs m && m.ertek == ertek; }
}

Map<ModosithatoKulcs, String> map = new HashMap<>();
ModosithatoKulcs kulcs = new ModosithatoKulcs();
kulcs.ertek = 42;
map.put(kulcs, "hello");
kulcs.ertek = 99;                   // hashCode megváltozott!
System.out.println(map.get(kulcs)); // null — bejegyzés elveszett a rossz vödörben

// ✅ Mindig immutábilis kulcsokat használj: String, Integer, record, UUID

Tipikus hiba — HashMap méretének előre meg nem adása

// ❌ 16-tól indul, sok rehash 10k bejegyzésnél
Map<String, Integer> map = new HashMap<>();

// ✅ Előre méretezés: kapacitás = várható_bejegyzések / 0.75 + 1
Map<String, Integer> map = new HashMap<>(13_334); // ~10k / 0.75
// Java 19+:
Map<String, Integer> map = HashMap.newHashMap(10_000);

---

5. Trade-offok

ArrayList vs LinkedList

HashMap vs LinkedHashMap vs TreeMap

---

6. Gyakori hibák

1. Map iterálása keySet + get-tel

// ❌ Kétszeres lookup bejegyzésenként
for (String key : map.keySet()) {
    Integer value = map.get(key); // felesleges lookup
}

// ✅ Használj entrySet-et vagy forEach-t
for (Map.Entry<String, Integer> e : map.entrySet()) {
    feldolgoz(e.getKey(), e.getValue());
}
map.forEach((k, v) -> feldolgoz(k, v)); // Java 8+

2. TreeMap használata HashMap helyett

// ❌ O(log n) egyszerű lookupnál
Map<String, Felhasznalo> users = new TreeMap<>();

// ✅ O(1) átl. — TreeMap-et csak rendezéskor használj
Map<String, Felhasznalo> users = new HashMap<>();

3. HashSet equals + hashCode nélkül

// ❌ Hiányzó equals/hashCode — duplikátumok a HashSet-ben
class Pont { int x, y; }
Set<Pont> set = new HashSet<>();
set.add(new Pont());  // x=1, y=2
set.add(new Pont());  // x=1, y=2 — de NEM duplikátum! Különböző objektumok
System.out.println(set.size()); // 2 — hiba!

// ✅ Adj hozzá @Override equals() és hashCode() metódusokat
record Pont(int x, int y) {} // record-ok automatikusan generálják ezeket

---

7. Mélymerülés

Miért veri az ArrayList a LinkedList-et beillesztésnél

A CPU cache sorok 64 bájtosak. Az ArrayList összefüggő tömbje lehetővé teszi a CPU prefetch-et — amikor az i indexhez férsz hozzá, a CPU előre betölti az i+1, i+2 stb. elemeket. A LinkedList csomópontjai szétszórva vannak a heap-en → minden csomópont-hozzáférés potenciális cache miss. Ez az ArrayList-et 3–10× gyorsabbá teszi a gyakorlatban tipikus méreteknél.

HashMap treeification (Java 8+)

Rosszul elosztott hashCode implementációk O(n) legrosszabb esetet okozhatnak HashMap-nél. A Java 8 bevezette a treeification mechanizmust: ha egy vödörben ≥8 bejegyzés van ÉS a tábla ≥64 vödörrel rendelkezik, a vödör Red-Black Tree-vé alakul → O(log n) legrosszabb eset, megelőzve a hash flooding DoS támadásokat.

EnumMap és EnumSet — a feledett drágakövek

Enum kulcsoknál mindig ezeket a specializált változatokat használd:

// Tömb-alapú, nincs hashing, O(1) ordinális index alapján
Map<DayOfWeek, List<Feladat>> menetrend = new EnumMap<>(DayOfWeek.class);
Set<DayOfWeek> munkanapok = EnumSet.range(MONDAY, FRIDAY);

Determinisztikus teszt kimenet

A HashMap iterálási sorrendje nem determinisztikus és JVM futtatások között változhat. Map tartalmát ellenőrző tesztekhez:

// ✅ Kiszámítható sorrend tesztekben
Map<String, Integer> rendezett = new TreeMap<>(hashMap);
assertEquals("{a=1, b=2}", rendezett.toString());

Miért váltsa le az `ArrayDeque` a `Stack`-et?

A Stack a Vector-ból örököl, ami legacy szinkronizációt és kényelmetlen örökséget hoz magával. Modern LIFO használatra szinte mindig az ArrayDeque a jobb alapértelmezés.

Az előre méretezés valódi optimalizáció

Nagy mennyiségű beszúrásnál az ArrayList és HashMap ismételt növekedési lépései felesleges allokációt, másolást és rehashingot okoznak. Reális kezdőkapacitással ez jelentősen csökkenthető.

---

8. Interjúkérdések

Miért jobb alapértelmezett választásnak általában az `ArrayList`, mint a `LinkedList`?

Mert a legtöbb üzleti terhelés jobban profitál a tömör memóriaképből, a gyors indexelt olvasásból és a cache lokalitásból, mint a láncolt lista elméleti előnyeiből.

Mikor jobb a `LinkedHashMap`, mint a `HashMap`?

Amikor a determinisztikus iterálási sorrend fontos, például stabil kimenetnél, teszteknél, felhasználói listáknál vagy LRU cache építésénél.

Mi az a treeification a `HashMap`-ben?

Ez a Java 8+ védelmi és teljesítményi mechanizmusa, amikor az erősen ütköző bucketek linked list helyett kiegyensúlyozott fává alakulnak.

Mikor választanál mégis `TreeMap`-et a `HashMap` helyett?

Ha a rendezett kulcsok, a navigációs metódusok vagy a tartomány-lekérdezések valódi követelmények.

---

9. Szószedet

---

10. Gyorsreferencia

• 📋 ArrayList — alapértelmezett List. O(1) get. Előre méretezés: new ArrayList<>(n)
• 🔗 LinkedList — kerüld List-ként. Csak Deque-ként használd. ~48 bájt/csomópont overhead
• 🗺️ HashMap — alapértelmezett Map. O(1) átl. ≥8 bejegyzésnél vödörré alakul
• 🔗 LinkedHashMap — HashMap + beillesztési/hozzáférési sorrend. LRU cache removeEldestEntry-vel
• 🌲 TreeMap — O(log n), rendezett kulcsok. Tartomány lekérdezéshez, firstKey(), headMap()
• 🔑 HashSet = belül HashMap. Helyes equals/hashCode szükséges
• ⚠️ Módosítható HashMap/HashSet kulcs = elveszett bejegyzések — mindig immutábilis kulcsokat használj
• 📏 HashMap előre méretezés: new HashMap<>((int)(n / 0.75) + 1) a rehashing elkerüléséhez
• 🚀 EnumMap/EnumSet enum kulcsoknál — tömb-alapú, nincs hashing szükséges
• 🔄 Map iterálása entrySet()-tel vagy forEach()-vel, soha keySet() + get(key)-jel