Programming | Delphi » Fábián Zoltán - Hasító táblázatok és függvények

2. Hasító táblázatok A hasító táblázat a tömb fogalom egyszerű általánosítása. A tömbelemek közvetlen címzése lehetővé teszi, hogy egy tetszőleges pozíción levő elemet hatékonyan, O(1) idő alatt vizsgálhassunk meg. Amikor az aktuálisan tárolt kulcsok száma a lehetséges kulcsok számához képest viszonylag kicsi, akkor a hasító táblázatok igen hatékonyak, mivel a legtöbb esetben a tárolt kulcsok számával arányos méretű tömböt használnak. A tömb elemeinek közvetlen címzésére a kulcs helyett egy, a kulcsból kiszámított érték szolgál. A legfontosabb szótárműveletek végrehajtása átlagosan O(1) időt igényel A legrosszabb esetben @(n), mint a láncolt lista esetében. Ismétlésképpen az átlagos keresési idők: szekvenciális keresés (n/2), logaritmikus keresés (log2n), bináris fa (log2n). Megjegyzések Ha például az egyes kulcsokat úgy képezzük, hogy a karakterek ASCII kódjait összeadjuk, akkor nem kapunk

egyértelmű megoldást, mivel több kulcs ugyanoda mutathat, ha ugyanolyan (de más sorrendben levő) karakterekből áll. Az ütközés feloldása: az egy kulcshoz tartozó elemeket láncolt listába fűzzük fel. Egy hasító függvény akkor jó, ha egyenletesen képez le, és nem hoz létre sűrűsödéseket, csomókat a táblázatban. (a címtér mérete korlátozott) Közvetlen címzésű táblázatok A közvetlen címzés akkor alkalmazható, amikor lefoglalhatunk egy akkora tömböt, amelyben minden lehetséges kulcsnak megfelel egy tömbelem. Ez a technika viszonylag kis méretű kulcsuniverzumokra jól működik. Tegyük fel, hogy egy alkalmazáshoz olyan dinamikus halmazra van szükségünk, melyben az elemek kulcsai az U={0,1,,m-1} univerzumból valók, ahol m nem túl nagy. Tegyük fel még, hogy nincs két egyforma kulcsú elem. A dinamikus halmaz megvalósítására egy T[0m-1] tömböt használunk, amely maga a közvetlen címzésű táblázat. A táblázat minden

helye (rés) megfelel az U univerzum egy kulcsának. Pl a k rés a halmaz k kulcsú elemére mutat Ha a halmaz nem tartalmaz k kulcsú elemet, akkor T[k]=nil. Műveletek KÖZVETLEN CÍMZÉSŰ KERESÉS (T,k) Return T[k] KÖZVETLEN CÍMZÉSŰ BESZÚRÁS (T,x) T[kulcs(x)]=x KÖZVETLEN CÍMZÉSŰ TÖRLÉS (T,k) T[kulcs(x)]=NIL Mindegyik művelet gyors, végrehajtási idejük O(1). Bizonyos alkalmazásokban a dinamikus halmaz elemei tárolhatók magában közvetlen címzésű táblázatban. Ilyenkor egy elem kulcsát és kísérő adatait nem egy, a táblázat megfelelő réséhez mutatóval kapcsolt külső objektumban tároljuk, hanem magában a résben, miáltal tárterületet takarítunk meg. Gyakran még az sem szükséges, hogy az objektum kulcsmezőjét tároljuk, hiszen ha megvan egy elem táblázatbeli indexe, akkor megvan a kulcsa is. Ha az elemeket magukban a résekben tároljuk, akkor valamilyen módon el kell tudnunk dönteni, hogy egy rés üres-e. Hasító táblázatok

Ha az U univerzum nagy, akkor egy |U| méretű T táblázat tárolása a gépek memóriájában nem célszerű vagy lehetetlen. Fennáll továbbá, hogy az aktuálisan tárolt elemek K halmaza az U-hoz képest olyan kicsi lehet, hogy a T által elfoglalt hely nagy része kihasználatlan. Amikor a szótárban tárolt kulcsok K halmaza sokkal kisebb a lehetséges kulcsok U univerzumánál, akkor a hasító táblázatnak jóval kisebb memóriára van szüksége, mint a közvetlen címzésű táblázatnak. A közvetlen címzés használata esetén egy k kulcsú elem a k. résben tárolódik A hasítási technika alkalmazása esetén ez az elem a h(k) helyre kerül, vagyis egy H hasító függvényt használunk arra, hogy a rést a k kulcsból meghatározzuk. Itt H a kulcsok U univerzumát képezi le a T[0m-1] hasító táblázat réseire: H: U -> {0,1,,m-1}. A hasító függvény célja, hogy csökkentsük a szükséges tömbindexek tartományát. |U| számú index helyett most csak

m-re van szükség. A memóriaigény is ennek megfelelően csökken Megtörténhet, hogy két elem ugyanoda képződik le, vagyis ütközés van. Az ütközések kiküszöböléséhez a H hasító függvényt kell megfelelően megválasztani. Egy lehetséges megoldás az, hogy véletlenszerűen generáljuk a H függvényt. Így minimalizálható az ütközések száma. Természetesen egy hasító függvénynek determinisztikusnak kell lennie: egy adott k elemre ugyanazt a h(k) kulcsot kell előállítania. De mivel |U|>m, ezért kell lennie legalább két kulcsnak, ami ugyanarra a hasított értékre képződik le, tehát az ütközések elkerülése lehetetlen. Ütközésfeloldás láncolással A láncolásnál az ugyanarra a résre leképeződő elemeket összefogjuk egy láncolt listába. A j rés egy mutatót tartalmaz, amely a j címre leképződő elemek listájának fejére mutat. Amennyiben ilyen elemek nincsenek, akkor a j. rés a NIL-t tartalmazza Műveletek

LÁNCOLT-HASÍTÓ-BESZÚRÁS (T,x) Beszúrás a T[h(kulcs(x))] lista elejére LÁNCOLT-HASÍTÓ-KERESÉS (T,k) A k kulcsú elem keresése a T[h(k)] listában LÁNCOLT-HASÍTÓ-TÖRLÉS (T,x) X törlése a T[h(kulcs(x))] listából 2. Hasító függvények Jó egy hasító függvény akkor, ha minden kulcs egyforma valószínűséggel képződik le az m rés valamelyikére. A gyakorlatban heurisztikus technikákat használhatunk a jól működő hasító függvények készítésére. A hasító függvény értékét úgy állítjuk elő, hogy várhatóan független legyen az adatokban esetleg meglévő szabályszerűségektől. A kulcsok természetes számokkal való megjelenítése A legtöbb hasító függvény azt tételezi fel, hogy a kulcsok univerzuma a természetes számok halmaza. Ekkor keresnünk kell egy módszert arra, hogy a kulcsokat természetes számokként jelenítsük meg. Például a karaktersorozat kulcsokat tekinthetjük megfelelő számrendszerben felírt

egészeknek. A pt azonosítót (112,116) ASCII kódokkal felírva, és a 128-as számrendszerben felírt egészként tekintve pt a (112x128)+116=14452 számmal azonosítható. Mivel a legtöbb esetben található hasonlóan egyszerű módszer, a továbbiakban felételezzük, hogy a kulcsok természetes számok. Az osztásos módszer Egy k kulcsot úgy képezünk le az m rés valamelyikére, hogy vesszük k m-mel való osztásának maradékát. Azaz a hasító függvény a következő: h(k)=k mod m Ha például a hasító táblázat mérete m=12 és a kulcs k=100, akkor h(k)=4. Mivel ez a módszer egyetlen osztást igényel, ezért igen gyors. Ne legyen például m 2 hatvány, mert ilyenkor h(k) éppen k legalacsonyabb helyértékű bitje. A 10 hatványok elkerülendők akkor, ha decimális számokat használunk kulcsként, mivel ilyenkor a hasító függvény nem függne a k összes decimális jegyétől. Jó értékek m számára a 2 hatványokhoz nem túl közeli prímek. Pl a 701 A

szorzásos módszer Két lépésben működik. Az elsőben beszorozzuk a k kulcsot valamely A (0<A<1) állandóval, és vesszük a kA törtrészét. Ezután ezt az értéket beszorozzuk m-mel és vesszük az eredmény alsó egészrészét. Röviden a hasító függvény értéke a következő: h(k)=[m(kA mod 1)], ahol kA mod 1 a kA törtrészét, vagyis (kA-[kA])-t jelenti. A szorzásos módszer előnye, hogy itt az m értéke nem kritikus. Általában valamely 2 hatványnak választjuk. Így a legtöbb gépen könnyen megvalósíthatjuk a függvényt Bár ez a módszer az A állandó minden értékére működik, bizonyos értékekre jobban. Az optimális választás a tárolt adatok jellegétől függ. Knuth azt írja, hogy az A≈ 5 −1 ≈ 0,6180339887. 2 érték valószínűleg jól fog működni. Például legyen k=123456, m=10000, és A a Knuth-féle érték. Ekkor: h(k) = [10000 x (123456 x 0,61803 mod 1)] = [10000 x (76300.0041151 mod 1)] = ε[10000 x (0,0041151)] =

[41,15] = 41 Az univerzális hasítási technika Ha a kulcsokat szándékosan úgy választjuk, hogy mindig ugyanarra a résre képződjenek le, akkor a keresés átlagos ideje a legrosszabb: @n. A hasonló esetek elkerülésére az egyedüli hatásos megoldás, ha a hasító függvény véletlenül, azaz a kulcsoktól független módon működik. Ez az univerzális hasítási technika, amely jó átlagos teljesítményhez vezet Alapgondolata az, hogy a hasító függvényt egy megtervezett függvényosztályból a futás során, véletlenül választjuk ki. A véletlenség garantálja, hogy ne legyen egy olyan előre megadható bemenet, amely mindig a legrosszabb viselkedést váltja ki. A rossz eset most csak akkor áll elő, ha a számítógép választ olyan véletlen hasító függvényt, amely az azonosítókat nem egyenletesen osztja szét, de ennek valószínűsége kicsi, és minden hasonló méretű halmaz esetén ugyanaz. Legyen H hasító függvények egy véges

rendszere, melyek ez adott U kulcsuniverzumot a {0,1,,m-1} tartományba képeznek le. Egy ilyen kollekciót univerzálisnak hívunk, ha tetszőleges x, y ε U ülönböző k elemekből álló kulcspár esetében azoknak a εh H hasító függvényeknek a száma, melyekre h(x)=h(y) pontosan |H|/m. Tehát a kulcsok közötti ütözés valószínűsége ugyanaz, mint a {0,1,,m-1} halmazból véletlenül kiválasztott h(x) és h(y) egyenlőségének valószínűsége. Egy megfelelő univerzális hasító függvény: r ha ( x) = ∑ i = 0 aixi mod m A nyílt címzés A nyílt címzés esetében az elemeket magában a hasító táblázatban tároljuk. A táblázat elemeinek tartalma vagy a dinamikus halmaz egy eleme vagy pedig a NIL. Egy elem keresésénél rendre végignézzük a táblázat réseit mindaddig, amíg vagy megtaláljuk a kívánt elemeit, vagy rájövünk, hogy az elem nincs a táblázatban. A nyílt címzésnél nincsenek táblázaton kívül tárolt elemek, mint a

láncolásnál, ezért ez egy idő után betelhet. Bár az ugyanoda képződő elemeket összefűzhetnénk egy-egy, a hasító táblázaton belüli listába, azonban ezt nem teszzük, mivel a nyílt címzés lényege pont a mutatók elkerülése. A mutatók láncának követése helyett itt egymás után kiszámítjuk a megvizsgálandó rések címeit. A beszúrást úgy hajtjuk végre, hogy a hasító táblázat réseit egymás után megvizsgáljuk, amíg ürest nem találunk, amibe a kulcsot betehetjük. A kipróbálandó pozíciók sorrendje a beszúrandó kulcs függvénye. Annak meghatározására, hogy melyik rést kell kipróbálni, kiterjesztjük a hasító függvény értelmezési tartományát egy új komponenssel, a kipróbálási számmal. Így a hasító függvény a következő alakú lesz: H: U x {0,1,,m-1} –> {0,1,,m-1} Megköveteljük még, hogy minden k kulcsra az úgynevezett { H (k,0), H (k,1),, H (k,m-1) } kipróbálási sorozat a {0,1,,m-1} egy permutációja

legyen. Ebből következik, hogy a táblázat kitöltése során minden pozíció számításba jön, mint egy új kulcs helye. A következő eljárásban feltételezzük, hogy a T hasító táblázatban csak kulcsok vannak, kísérő adatok nélkül; a k kulcsot tartalmazó elemet azonosítjuk magával a kulccsal. A rések vagy egy kulcsot tartalmaznak, vagy pedig NIL-t. HASÍTÓ-BESZÚR(T,k) I=0 Ciklus j=H(k,i) Ha (T[j]=nil )vagy (törölt) akkor T[j]=k Kilépés Különben i=i+1 Amíg i=m Ha (i=m) akkor túlcsordulás, nem lehet berakni az új elemet A keresési algoritmus valamely k kulcsra ugyanazokat a rés-sorozatokat próbálja ki, amelyeket a beszúrás algoritmus is megvizsgált, amikor a k-t beszúrta. Éppen ezért a keresési algoritmus megállhat (sikertelenül), amikor egy üres elemet talál, hiszen a k kulcsnak a beszúrás során ebbe a résbe kellett volna bekerülnie, tehát kipróbálási sorozatának későbbi tagjaiban már biztosan nem lehet benne.

(feltételezve, hogy nincsenek a hasító táblázatból kitörölt kulcsok) A HASÍTÓ-KERES eljárás bemenete a T hasító táblázat és a k kulcs, a visszatérési érték a k kulcsot tartalmazó rés j sorszáma, vagy NIL, ha nincs ilyen rés. HASÍTÓ-KERES I=0 Ciklus J=H(k,I) Ha T[J]=k akkor result=J Kilépés Különben i=i+1 Amíg (I=m) vagy (T[J]=NIL) Ha (T[J]=k) akkor Megvan A nyílt címzéses törlés kissé nehezebb. Amikor töröljük az i résben lévő kulcsot, nem elegendő a NIL beírása, mert ha csak ezt tennénk, akkor lehetetlen lenne minden olyan kulcs visszakeresése, melynek beszúrása során az i. rést kipróbáltuk és foglaltnak találtuk Egy lehetséges megoldás az, hogy a töröltség jelölésére a NIL helyett egy másik értéket, a TÖRÖLT-et használjuk. Ennek megfelelően a HASÍTÓ-BESZÚR eljárást úgy kell módosítani, hogy a TÖRÖLT értékű réseket is kezelje; megengedve hogy kulcs kerüljön beléjük. A HASÍTÓ-KERES eljárást

nem is kell megváltoztatni, mivel az a TÖRÖLT értékek esetében jól működik, azaz továbblép. Ha lehetővé tesszük az elemek törlését, akkor a keresési idő már nem lesz a kitöltöttségi arány függvénye. Ezért amikor törölnünk is kell elemeket, akkor az ütközések feloldására legtöbbször nem is a nyílt címzést, hanem a láncolást használjuk. Elemzésünk során élünk az egyenletes hasítási feltételezéssel, tehát feltesszük, hogy minden kulcsra a {0,1,.,rn - 1} elemek m! permutációja közül mindegyik ugyanolyan valószínűséggel fordul elő, mint kipróbálási sorozat. A tiszta egyenletes hasítási technikát nehéz megvalósítani, ezért a gyakorlatban alkalmas közelítéseket használnak (mint például dupla hasítás). Három olyan technika van, amit a nyílt címzésnél széles körben használnak kipróbálási sorozatok előállítására: a lineáris kipróbálás, a négyzetes kipróbálás és a dupla hasítás.

Mindegyikük garantálja, hogy bármely k kulcs esetében az (h(k,0),h(k,1),,h(k,m-1)) sorozat a (0,1,.,m-1) sorozat permutációja legyen Ezen technikák egyike sem teljesíti az egyenletes hasítási feltételt, hiszen egyikük sem tud m2-nél több kipróbálási sorozatot létrehozni (az egyenletes esetben elvárt m! helyett). A dupla hasító adja a legtöbb kipróbálási sorozatot, és a legjobb eredményt. A lineáris kipróbálás Ha adott egy h : U {0,1, .,m - 1 } közönséges hasító függvény, akkor a lineáris kipróbálás módszere az alábbi hasító függvényt használja (i = 0,1, . m - 1): h(k,i) = (h(k) + i) mod m. Egy adott k kulcs esetén az első kipróbált rés T[h(k)]. A következő kipróbált elem a T[h(k)+1], és így tovább egészen a T[m - 1] résig. Ezután ciklikusan folytatjuk a T[0] T[1] résekkel, s legvégül T[h(k) - 1]-et próbáljuk ki. Mivel a kezdeti próbapozíció már meghatározza az egész kipróbálási sorozatot, ezért itt csak

m kipróbálási sorozat fordul elő. A lineáris kipróbálást könnyű megvalósítani, de kellemetlen hátránya is van, az elsődleges klaszterezés jelensége. Hosszú, elemek által teljesen kitöltött sorozatok jönnek létre; melyek megnövelik az átlagos keresési időt. Például vegyünk egy n = m / 2 elemet tartalmazó táblázatot. Ha itt az összes páros sorszámú rés kulccsal kitöltött, s az összes páratlan üres, akkor a sikertelen keresés átlagos igénye 1.5 kipróbálás Ha viszont a táblázat első n = m/2 eleme a foglalt, akkor az átlagos kipróbálási szám körülbelül (n/4 = m/8)-ra nő. Sajnos a klaszterek keletkezésének valószínűsége elég nagy, mivel egy i hosszúságú foglalt szakaszt követő üres elem új kulccsal való kitöltésének valószínűsége (i+1)/m; ami akkor a legkisebb, 1/m, ha a megelőző elem is üres. A tendencia az, hogy az összefüggő, foglalt elemekből álló szakaszok egyre hosszabbak lesznek, s ezért a

lineáris kipróbálás nem a legjobb közelítése az egyenletes hasítási technikának. A négyzetes kipróbálás A négyzetes kipróbálás a következő alakú hasító függvényt használja: h(k.i) = (h(k) + c1i + c2i2) mod m, ahol (ahogy a lineáris kipróbálásnál) h egy kisegítő hasító függvény, c1 és c2 ≠ 0 segédállandók és i = 0,1, . , m - 1 Az először kipróbált pozíció itt is T[h(k)]:, a későbbi pozíciók az őket megelőzőkből a próbaszámtól négyzetesen függő mennyiséggel való eltolással kaphatók meg. Ez a módszer sokkal hatékonyabban működik, mint a lineáris kipróbálás. Ahhoz viszont, hogy ki tudjuk használni az egész táblázatot, megkötéseket kell tennünk c1-re, c2-re és m-re. Itt is igaz, hogy ha két kulcshoz ugyanaz a kezdeti próbapozíció tartozik, akkor a teljes kipróbálási sorozatuk megegyezik; hiszen h(k1,0) = h(k2, 0)-ból már következik h(k1,i) = h(k2,i). Ez a klaszterezés egy szelídebb

változatához, az úgynevezett másodlagos k laszterezéshez vezet. Úgy, mint a lineáris kipróbálásnál, a kezdeti próbahely itt is meghatározza a teljes kipróbálási sorozatot, ezért csak m különböző sorozat van használatban. A dupla hasítás A dupla hasítás az egyik legjobb nyílt címzéses módszer; mivel az általa használt kipróbálási sorozatok a véletlen permutációk sok tulajdonságával rendelkeznek. A dupla hasítás a következő alakú hasító függvényt használja: h(k,i) = (h1(k) + i∙h2(k)) mod m, ahol hl és h2 kisegítő hasító függvények. A kezdeti kipróbálási pozíció most is T[h1(k)]; az egymás után következő próbapozíciók pedig az előző pozíciók h2(k)-val való eltolásával jönnek létre (mod m). A lineáris illetve négyzetes kipróbálás módszerével ellentétben itt a próbasorozatok kétféle módon is függenek a k kulcstól, mivel a kezdőpozíció, az eltolás illetve mindkettő változhat. A h2(k)

értéknek relatív prímnek kell lennie a táblázat m méretéhez képest. Ha ugyanis valamely k kulcsra m-nek és h2 (k)-nak volna valamilyen d > 1 közös osztója, akkor k keresése során csak a táblázat 1/d részét tudnánk megvizsgálni. Egy kényelmes út ennek a feltételnek a biztosítására, ha m-et 2 hatványnak választjuk, h2-t pedig úgy, hogy mindig páratlan számot állítson elő. Egy másik lehetőség, ha m prím és h2 mindig m-nél kisebb pozitív egészet ad eredményül. Válasszuk például m-et prímnek és legyen hl (k) = k mod m, h2(k) = 1 + (k mod m), ahol m egy m-nél kicsivel kisebb egész (mondjuk m-1 vagy m-2). Ha például k = 123456 és m=701, m = 700; akkor h1(k) = 80 és h2(k) = 257, így az első kipróbálási pozíció a 80, s minden 257. (mod m) elemet megvizsgálunk, amíg a kulcsot meg nem találjuk vagy addig, amíg minden rést meg nem vizsgáltunk. A dupla hasítás a lineáris és négyzetes hasítási technika javítása, ahol a

e (m) kipróbálási sorozat helyett @(m2)-t használhatunk; mivel minden lehetséges (h1(k),h2(k)) értékpát különböző sorozathoz vezet. Az is javítás, hogy amikor változtatjuk a kulcsot, akkor a kezdeti h1(k) próbapozíció és a h2(k) eltolás egymástól függetlenül változik. Beszúrás dupla hasítási technika esetén. Hasító táblázatunk legyen 13 hosszú, hl(k) = k mod 13 és h2(k) = 1 + (k mod 11). Mivel 14 ≡ mod 13 és 14≡3 mod 11, ezért a 14 kulcsot a 9. résbe szúrjuk be, mivel az 1. és 5 rés megvizsgálásakor azokat már foglaltnak találtuk