Mi a hash-tábla működési elve?

Hash-tábla (vagy asszociatív tömb) párokat "kulcs-érték" tárol. A működési elv egy hash függvény használatán alapul, amely a kulcsot numerikus indexre (hash) alakítja, jelezve az érték tárolási helyét a tömbben (kosár).

Lépések:

Hash számítása: Egy adott kulcs esetén a hash érték számítása.

<?php
$key = "example";
$hash = crc32($key); // Egyszerű hash függvény példája

Index meghatározása: A hash értékét általában a tömb méretének modulo műveletével alakítjuk át indexre.
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Kosárhoz való hozzáférés: A számított index segítségével hozzáférünk a tömb megfelelő kosarához.
Ütközések kezelése: Mivel különböző kulcsok ugyanazt a hash értéket kaphatják (ütközés), a kosár több "kulcs-érték" párt is tartalmazhat. Az ütközések megoldására különböző módszerek léteznek:
- Láncolás (Separate Chaining): Minden kosárban egy lista (pl. összekapcsolt lista) tárolja a "kulcs-érték" párokat, amelyek hash értékei egyeznek.
- Nyitott címzés (Open Addressing): Ütközés esetén ismételt keresést végzünk egy szabad cella után a tömbben egy meghatározott szabály szerint (lineáris, kvadratikus, dupla hash).

Műveletek:

Beszúrás: A kulcs hash értékét kiszámítjuk, meghatározzuk az indexet, és a "kulcs-érték" párt a megfelelő kosárba helyezzük. Ütközés esetén hozzáadjuk a listához (láncolás) vagy keresünk szabad helyet.
Keresés: A kulcs hash értékét kiszámítjuk, meghatározzuk az indexet. A megfelelő kosárban a kulcs alapján keressük az értéket. Láncolás esetén végigiterálunk a listán; nyitott címzésnél szekvenciális keresést végzünk.
Törlés: A kulcs hash értékét kiszámítjuk, meghatározzuk az indexet. A megfelelő kosárban megtaláljuk és töröljük a párt a kulcs alapján.

Előnyök:

Gyors hozzáférés az elemekhez (átlagosan O(1)).
Hatékony memóriahasználat.

Hátrányok:

Nagy ütközésszám esetén a teljesítmény romolhat.
A táblázat mérete igényelhet beállítást (rehashing) a hatékonyság fenntartása érdekében.