Programming | Programming theory » Dr. Iványi Péter - Adatszerkezetek, hasító táblák

Adatszerkezetek Hasító táblák Dr. Iványi Péter 1 Hash tábla • A bináris fáknál O(log n) a legjobb eset a keresésre. • Ha valamilyen „közvetlen címzést” használunk, akkor akár O(1) is elérhető. • A hash tábla a tömb általánosításaként is felfogható, ahol az index bármilyen érték lehet. • „Ugyanakkor több lehetséges kulcs van mint hely a táblában” 2 Hash tábla Nagy adathalmaz, de sok kihagyás van az adatok között Hash függvény Kis adathalmaz 3 Hash tábla • Tömbnél az index: egész szám • Hash tábla: valós szám, szöveg, egy másik tömb vagy bármi egyéb. • Az index: a kulcs • A hash táblába tárolt adat: az érték 4 Primitív hash tábla, tömb • n elemű tömbben akarjuk tárolni a megadott adatokat • Feltételezzük, hogy a kulcs csak egész szám • Maradék osztást használunk insert(index, ertek) { tomb[index mod n] = ertek; } 5 Hash tábla • Trükk: a kulcsból tömb indexet

hozunk létre • Például, ha adva van egy név, akkor szeretnénk megtudni a hozzátartozó telefonszámot 6 Hash függvény • A hash táblák alapja a „megfelelően” megválasztott hash függvény. – Irodalom tartalmaz jót és rosszat is – Nincs univerzális megegyezés arról mi tekinthető jónak • Rosszul választott függvény kulcs ütközéshez (collision) vezet • Kulcsok csoportosulása (clustering): Ebben az esetben annak a valószínűsége hogy több kulcs ugyanazt az indexet adja meg jóval nagyobb mintha egy véletlen szám generátor függvényt használtunk volna. 7 Hash függvény • Függvény minősége: – Egyszerűség (forrás kódban a sorok száma) – Sebesség (időmérés, benchmark) – „Erő” mérése: • Statisztikai tesztek melyek megállapítják, hogy a hash függvény mennyiben különbözik a véletlen szám generáló függvénytől • Talán a legfontosabb mérési módszer a hash függvény jóságának a

mérésére, hogy a függvényre jellemző-e az „Avalanche” effektus 8 Avalanche effektus • Ha a bemenetet kicsit megváltoztatjuk (például csak egy bitet átállítunk) akkor a kimenet jelentősen megváltozik (például az eredménynek több mint a fele megváltozik) 9 Hash függvény • A hash függvény akkor „jó”, ha: – amikor a bemenet egy bitje megváltozik, akkor a kimenet minden bitje legalább 50 %-os valószínűséggel változik meg 10 Ütközések feloldása • Ha két kulcs ugyanazt az indexet adja, akkor nem lehet két rekordot ugyanaz a helyen tárolni. • Ebben az esetben egy másik helyet (indexet) kell találni. – Feloldás túlcsordulás kezeléssel – Láncolás (chaining) – Alternatív címzés (open addressing) 11 Túlcsordulás kezelés tabla[n]; overflow[MAX OVERFLOW]; end index = 0; Insert(kulcs, ertek) { h = hash(kulcs) mod n; if(tabla[h] != ures) { if(end index == MAX OVERFLOW) tabla betelt; overflow[end] = kulcs

és ertek; end = end + 1; } else tabla[h] = kulcs és ertek; } 12 Túlcsordulás kezelés • Többféle probléma – A túlcsordulás tömböt is végig kell keresni, – Ha nagy a túlcsordulás tömb lassítja a keresést, törlést, beillesztést, O(n) lesz ismét 13 Láncolás • A hash táblában minden rekord valójában egy láncolt lista • Keresés, törlés kiegészül azzal, hogy a listán végig kell menni 14 Láncolás • Elvileg szükség lehet rendezett listára, hogy gyorsabban kereshessünk, DE • Ha jó a hash függvény akkor a listák rövidek és nincs szükség a rendezésre, mert a keresés a rendezetlen listában így is nagyon rövid lesz! 15 Alternatív címzés • Alternatív címet keresünk ütközés esetén – Lineáris próba – Quadratikus próba – Dupla hashing 16 Lineáris próba • Példa: – A hash tábla legyen egy 11 elemű tömb 0 1 2 3 4 5 6 7 8 9 10 insert(kulcs, ertek) { h = hash(kulcs) mod n;

while(tabla[h] != ures) { h = (h + 1) mod n; } tabla[h] = kulcs és ertek; } 17 Lineáris próba Beillesztés: 426 426 mod 11 = 8 0 Beillesztés: 921 921 mod 11 = 8 0 Beillesztés: 715 715 mod 11 = 0 0 1 2 3 4 5 6 7 8 9 10 426 1 2 3 4 5 6 7 8 9 10 426 921 715 1 2 3 4 5 6 7 8 9 10 426 921 18 Lineáris próba Beillesztés: 129 129 mod 11 = 8 Beillesztés: 514 514 mod 11 = 8 Beillesztés: 287 287 mod 11 = 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 8 9 10 426 921 129 715 514 0 9 10 426 921 129 715 0 8 2 715 514 287 3 4 5 6 7 8 9 10 426 921 129 19 Lineáris próba • Jellemző rá a „csoportosulás” (clustering) – Előző példában a 8-az index esetén egyre nehezebb adatot beilleszteni. – Csökkenti az algoritmus sebességét • Lehetőleg csak félig legyen tele a hash tábla 20 Lineáris próba • A lépésköz általában 1, bár lehet mást is használni • Működés feltételei: – A

hash tábla mérete vagy prím szám legyen vagy kettő hatványa – Ha a tábla mérete kettő hatványa akkor a lépésköz csak páratlan lehet 21 Lineáris próba, törlés • A törlés problematikusabb – Ha valóban törlünk hibás működést kapnánk – Ha csak törlünk egy elemet, akkor a következő beillesztésnél a lináris próba idő előtt leállhat 22 Lineáris próba, törlés • A törlés problematikusabb – Ha valóban törlünk hibás működést kapnánk – Példa megoldás, de a beillesztést is módosítani kell remove(kulcs) insert(kulcs, ertek) { { h = hash(kulcs) mod n; h = hash(kulcs) mod n; while(tabla[h] != ures) while( { tabla[h] != ures && tabla[h] != DELETED) h = (h + 1) mod n; { } h = (h + 1) mod n; tabla[h] = DELETED; } } tabla[h] = kulcs és ertek; } 23 Quadratikus próba • Nem konstans lépést használunk. insert(kulcs, ertek) { h = hash(kulcs) mod n; for(step = 1; tabla[h] != ures; step++) { h =

(h + step * step) mod n; } tabla[h] = kulcs és ertek; } 24 Quadratikus próba • Nem jön létre csoportosulás • Csak akkor garantált a működés ha: – A tábla maximum félig telik meg (félig üres) – A tábla mérete prím szám 25 Dupla hashing • Két hash függvényt használunk • A lépésközt is hash függvény határozza meg insert(kulcs, ertek) { h = hash(kulcs) mod n; h2 = (hash(kulcs) mod (n – 1)) + 1 while(tabla[h] != ures) { h = (h + h2) mod n; } tabla[h] = kulcs és ertek; } 26 Dupla hashing • Működés feltételei: – h2 soha nem lehet nulla, mert végtelen ciklust kapnánk – A hash tábla mérete vagy prím szám legyen vagy kettő hatványa – Ha a tábla mérete kettő hatványa akkor a lépésköz csak páratlan lehet 27 Rehashing • Néha a tábla megtelik, vagy a műveletek nagyon lelassulnak, ilyenkor új táblát kell felépíteni • A régi tábla minden „élő” kulcsát kivesszük és az új nagyobb táblába

áttesszük – Lassú és számítástechnikailag drága, ritkán alkalmazzuk • Másik módszer • hozzunk létre egy új táblát és ellenőrizzük mindkét táblában ha keresünk • amikor az új táblába illesztünk, akkor a régiből vigyünk át k db elemet • Ha minden elemet átvittünk, töröljük a régi táblát 28 Teljesítmény • Legjobb eset: O(1) • Legrosszabb eset: O(n) • Legnagyobb hatással a teher faktor (load factor) van: használt helyek / tábla mérete – Mindegyik ütközés feloldás működik 0.5 alatt – 0.5 felett folyamatosan romlik a teljesítmény 29 Asszociatív tömbök • Absztrakt adattípus – Egyedi, tetszőleges kulcsokhoz „tetszőleges” érték rendelhető – Kulcs és érték közötti kapcsolat: mapping • Legfontosabb művelet: – Keresés (lookup) vagy indexelés • Kulcshoz tartozó érték megtalálása • Leggyakoribb alkalmazás például – memoization 30 Memoization, kitérő •

Optimalizáló (Javító, gyorsító) technika • Olyan programoknál használható ahol egy függvény ismételt meghívását akarjuk gyorsítani, mivel a korábbi eredményeit eltároljuk és azt használjuk ismételt hívásnál • Donald Michie, 1968-ban adta ezt a nevet a technikának – Memorandum (latin), emlékezés 31 Memoization • Lényegében az időt helyre cseréljük – Futási idő helyett tárolni kell az adatokat Példa memoization nélkül: Függvény faktoriális(n) if n == 0 visszatérési érték: 1 else visszatérési érték: n * faktoriális(n-1) if vége Függvény vége 32 Memoization • Az eredeti függvény hol tölti az időt? – – – – – Függvény hívás során a verem előkészítése Nullával való összehasonlítás n-1 kiszámítása a visszatérési érték tárolása a szorzás végrehajtása 33 Memoization Függvény faktoriális(n) if n in asszoc-tömb visszatérési érték: lookup(n, asszoc-tömb) if n == 0

visszatérési érték: 1 else x = n * faktoriális(n-1) if vége tárol(x, asszoc-tömb) visszatérési érték: x Függvény vége 34 Memoization • Az új függvény hol foglal helyet? – A lookup függvény egy adatszerkezetet használ ami függvény hívások között is megmarad! • Perzisztens adatszerkezet • Példa: faktoriális(5) faktoriális(4) már tárolja az értéket 35 Asszociatív tömbök • Implementálás – Hasító táblával – Egyensúlyozott bináris fával telephone[‘peter]=01-1234-56‘ telephone[‘miklos]=02-4321-56 Név peter miklos Telephone 01-1234-56 02-4321-56 36 Asszociatív tömbök • • • • Hasító tábla jobb mivel O(1), fa pedig O(log N) Fa szerkezet kisebb lehet a memóriában Jó hash függvény kell, ami nehéz lehet Fa szerkezet valamilyen „sorrendet” őriz, hasító tábla esetén nehéz végig menni az összes elemen • Hasító tábla fix méretű, esetleg rehashing kell ami rontja a hatékonyságot

• Fa szerkezet mindig O(log N) bonyolultságú, de a memóriában fragmentációt okozhat 37 Asszociatív tömbök • Script nyelvekben: – awk, perl, tcl, Javascript, Python, Ruby • Programozási nyelvek – Smalltalk, Objective-C, .NET, Common Lisp – PHP, korlátozott (csak egész szám és szöveg) 38