hashtábla

Hashtábla, vagy hash-tábla, egy adatstruktúra, amely kulcs–érték párok gyors tárolására és lekérésére szolgál. A tábla egy tömböt tartalmaz, minden elem egy kosár (bucket), amelyhez a kulcs hash függvénnyel rendeli a pozíciót. A konkrét érték a megfelelő bucketban tárolódik. A hash függvény feladata, hogy szétoszlassa a kulcsokat a buckets között és determinisztikusan adjon indexet.

Kollíziók kezelése: ha két kulcs ugyanarra a pozícióra kerül, akkor vagy külön láncolás (minden buckethoz láncolt lista vagy más összefűzhető szerkezet), vagy nyílt címzés (a befoglaló tömbön belül keresünk üres helyet) alkalmazható. Nyílt címzésnél gyakori elrendezések a lineáris probálás, a kvadratikus probálás és a kettős hasítás.

Teljesítmény és méretezés: az átlagos műveleti idő O(1) a kulcsok egységre osztásától és a memóriában elrendezéstől függően; a legrosszabb eset O(n). A teljesítményt a tömb mérete és a küszöbértéknek megfelelő load factor határozza meg. Dinamikus méretezés során a tábla akkor növekszik, amikor a n/m arány egy előre meghatározott küszöb fölé nő, és ekkor a régi elemeket átmásolják egy nagyobb tömbbe.

Előnyök és korlátok: gyors átlagos hozzáférés, egyszerű használat kulcsokkal való összekapcsoláshoz, de memóriaigényes lehet, és a teljesítmény érzékeny a hash függvény minőségére és a kollíziókezelésre.

Alkalmazások: általános szótárak, adatstruktúra indexelés, gyorsítótárak, adatbázisokban index- és map-tárolók.

---