Mi az a hashtable?

A számítógépes tudományban a hashtable olyan adatszerkezet az adatok tárolására, amelyek egy olyan értékek listájából állnak, az úgynevezett Keys, amelyet párosítanak a megfelelő értéklistával, úgynevezett tömbnek.Például egy üzleti név párosulhat a címével.Általában a tömb minden egyes értékének a hash -nak nevezett pozíciószáma van.A hash funkció általában utasításkészlet vagy algoritmus, amely az egyes kulcsértékeket egy hash -hoz és mdash -hez ábrázolja;Csatlakoztatja a vállalkozás nevét a címéhez, a telefonszámához és az üzleti kategóriához.A hash függvény célja, hogy az egyes kulcsokat hozzárendelje a tömb egyedi megfelelő értékéhez;Ezt általában hashnak nevezik.A hash -funkciókat megfelelően kell formázni a hashtable megfelelő működéséhez.

A hashtable teljesítménye egy adatkészleten függ a hash -funkció hatékonyságától.A jó hash -funkció általában egységes kulcsok keresését és a leképezések egyenletes eloszlását biztosítja a megfelelő tömbben.Hash -ütközés akkor fordul elő, ha két kulcsot ugyanazon értékhez rendelnek.Ha hash -ütközés következik be, a hash funkciót általában újra végrehajtják, amíg egyedi, megfelelő értéket nem találnak;Ez általában hosszabb hasítási időket eredményez.Noha a hashtablákban lévő kulcsok száma általában rögzítve van, néha lehetnek másolatú kulcsok.Ennek ellenére egy jól megtervezett hashtable hatékony hash-funkciókkal rendelkezik, amelyek az egyes kulcsokat a tömb egyedi megfelelő értékéhez térképezik.

Időnként a hashtable -ben a nem hatékony hash -funkciók is előállíthatják a leképezések csoportját.Ha egy hash -funkció létrehoz egy klasztert a meglévő kulcsokhoz, akkor ez növelheti a megfelelő értékek kereséséhez szükséges időt.Ez lelassíthatja a jövőbeli kulcsok kivonását, mivel a legtöbb hash -funkció általában a tömb következő helyzetét keresi.Ha egy nagy értékcsoportot már hozzárendeltek, akkor általában sokkal hosszabb időt vesz igénybe egy új kulcshoz nem megfelelő érték keresése.

A terhelési tényező egy másik fogalom, amely a hash -függvény hatékonyságához kapcsolódik;A terhelési tényező a már meglévő hashák mennyisége a megfelelő tömb teljes méretéhez viszonyítva egy hashtablában.Általában úgy definiálják, hogy a már hozzárendelt kulcsok számát a megfelelő tömb méretével osztják el.Ahogy a terhelési tényező növekszik, a jó hash -funkció általában továbbra is állandó számú ütközést és klasztereket tart fenn egy bizonyos pontig.Gyakran ez a küszöb felhasználható annak meghatározására, hogy a hash -funkció mennyire hatékony a megadott kulcsszámmal, és mikor lehet szükség új hash -funkcióra.olyan, amely nem eredményez ütközéseket vagy klasztereket, növekvő terhelési tényezővel.Elméletileg a tökéletes hashtable előállításának kulcsa egy tökéletes hash függvény előállítása.Általánosságban elmondható, hogy a kutatók úgy vélik, hogy a tökéletes hash -funkciónak állandó teljesítményűnek kell lennie mdash;az ütközések és klaszterek száma és mdash;növekvő terhelési tényezővel.A legrosszabb esetben a tökéletes hash -funkció továbbra is lehetővé tenné az állandó kivonást anélkül, hogy elérné a küszöböt.