Adatszerkezetek 2. 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 • 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
3
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; }
4
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
5
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. 6
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
7
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)
8
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
9
Ü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)
10
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; } 11
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
12
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
13
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!
14
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
15
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; } 16
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
17
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
18
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
19
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
20
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
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 – 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; }
22
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; }
23
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
24
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; } 25
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
26
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 27
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
28
Objektumok • Az objektumok olyan zárt programozási egységek, amelyek a kezelni kívánt adatokon kívűl tartalmazzák azokat az eljárásokat és függvényeket is amelyek az objektumok megfelelő kezelésére képesek. • 3 tulajdonság – Egységbe zárás – Öröklődés – Többrétűség (polimorfizmus) 29
Egységbe zárás • Encapsulation • Az adatmezőkön kívül a kezelő eljárások és függvények is részei az adatstruktúrának • Az objektum adatait manipulálni képes függvényeket és eljárásokat metódusnak nevezzük,
30
Speciális metódusok • Konstruktor: – Akkor fut le amikor az objektum futás közben létrejön – Biztosítja, hogy az adatokhoz szükséges memória rendelkezésre álljon
• Destruktor: – Akkor fut le, amikor az objektum megszűnik – Memória területek felszabadítása
31
Öröklődés • Minsig van egy ős objektum • Objektumokból származtatunk újabb objektumokat • A leszármaztatott objektumok öröklik őseik tulajdonságait, azaz minden eljárást, metódust és adatmezőt, amivel azok rendelkeznek.
32
Többrétűség (polimorfizmus) • Ha egy leszármaztatott objektum metódusát ugyanolyan néven definiálunk, mint egy ősének a metódusát • Function overriding
33
Objektum-orientált programozás • Más gondolkozást kíván meg a programozótól mint a struktúrális programozás • Objektumok hierarchiájának megtervezése
34
