Collections Framework — 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.

Művelet	Komplexitás	Megjegyzés
`get(index)`	O(1)	Közvetlen tömbhozzáférés
`add(element)` végre	O(1) amortizált	Átméretezés = új tömb ×1.5
`add(index, element)`	O(n)	Elemek jobbra tolása
`remove(index)`	O(n)	Elemek balra tolása
`contains(object)`	O(n)	Lineáris keresés

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.

Művelet	Komplexitás	Megjegyzés
`get(index)`	O(n)	Bejárás fejtől/faroktól
`addFirst()` / `addLast()`	O(1)	Mutatófrissítés
`removeFirst()` / `removeLast()`	O(1)	Mutatófrissítés
Memória elemenként	~48 bájt	Node header + adat + 2 referencia

2.3 `HashMap`

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

Művelet	Komplexitás	Megjegyzés
`get(key)`	O(1) átl.	O(log n) legrosszabb (Java 8+ fává alakított vödör)
`put(key, value)`	O(1) átl.	Kiválthat átméretezést
`containsKey(key)`	O(1) átl.

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.

Művelet	Komplexitás
`get` / `put` / `remove`	O(log n)
`firstKey()` / `lastKey()`	O(log n)
`headMap()` / `subMap()`	O(log n)

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.

3. Gyakorlati használat

ArrayList vs LinkedList

Forgatókönyv	Választás	Miért
Olvasás-intenzív, véletlenszerű hozzáférés	`ArrayList`	O(1) `get`
Közepéről gyakori hozzáadás/törlés	`ArrayList`	Cache-barát a O(n) tolás ellenére is
Queue/stack felhasználás	`ArrayDeque`	Jobb mint LinkedList mindkét végre
List + Deque egyszerre szükséges	`LinkedList`	Ritka; általában `ArrayDeque` jobb

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

Igény	Választás
Leggyorsabb get/put, sorrend nem kell	`HashMap`
Beszúrási sorrend megőrzése	`LinkedHashMap`
LRU cache	`LinkedHashMap(cap, 0.75f, true)` + `removeEldestEntry`
Rendezett kulcsok, tartomány lekérdezések	`TreeMap`

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

Szempont	ArrayList	LinkedList
⚡ Véletlenszerű `get(i)`	O(1)	O(n)
⚡ Hozzáadás véghez	O(1) amortizált	O(1)
⚡ Beillesztés közepére	O(n) tolás	O(n) bejárás
⚡ Törlés az elejéről	O(n) tolás	O(1)
💾 Memória/elem	~4 bájt (referencia)	~48 bájt (csomópont)
🔧 Cache lokalitás	Kiváló	Gyenge
🔄 Megvalósítja még	`RandomAccess`	`Deque`

HashMap vs LinkedHashMap vs TreeMap

Szempont	HashMap	LinkedHashMap	TreeMap
⚡ get/put	O(1) átl.	O(1) átl.	O(log n)
💾 Memória	Alap	+2 ref/bejegyzés	+2 ref + szín bit
🔧 Sorrend	❌ Nincs	✅ Beillesztési/hozzáférési	✅ Rendezett
🔧 Tartomány lekérdezés	❌	❌	✅
🔧 null kulcsok	✅ 1 engedélyezett	✅ 1 engedélyezett	❌ NPE

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. Senior-szintű meglátások

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());

8. Szószedet

Fogalom	Definíció
Load factor	Bejegyzések és vödrök aránya (alapérték 0.75); átméretezést vált ki ha túllépik
Rehashing	Új, nagyobb vödörtömb létrehozása és az összes bejegyzés újra-beillesztése — O(n)
Treeification	Java 8+ HashMap vödör átalakítása Red-Black Tree-vé ≥8 bejegyzésnél
Cache lokalitás	Mennyire fér bele az adat a CPU cache sorokba; összefüggő tömböknek kiváló a lokalitása
Amortizált O(1)	Átlagosan O(1) sok műveleten keresztül, alkalmanként O(n) tüske ellenére (pl. átméretezés)
LRU cache	Least Recently Used — a legrégebben hozzáfért bejegyzést távolítja el amikor megtelt

9. 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