Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 14: Rozdiel medzi revíziami
(→Oznamy) |
|||
(52 medziľahlých úprav od 3 ďalších používateľov nie je zobrazených) | |||
Riadok 1: | Riadok 1: | ||
== Oznamy == | == Oznamy == | ||
− | * | + | * Piatkové cvičenia sú povinné pre tých, ktorí nemali rozcvičku minulý týždeň, informáciu máte na testovači. |
− | * | + | * DÚ2 odovzdávajte do utorka 14.11. 22:00. |
− | * | + | * Na domácich úlohách a cvičeniach neodpisujte. |
+ | ** Ak vás prichytíme, stratíte body a hrozí vám aj disciplinárna komisia fakulty. | ||
+ | ** Hlavne sa ale nič nenaučíte a budete mať problémy na skúške a semestrálnom teste, ako aj na ďalších predmetoch. | ||
+ | * Semestrálny test bude v stredu 13.12. 18:10. Opravný termín v januári. | ||
+ | ** Ak sa vyskytne konflikt s iným predmetom, hláste to vyučujúcim čo najskôr. | ||
− | == | + | ==Dynamická množina== |
− | === | + | === Motivačný príklad === |
− | + | * Na fakulte sa dvere do niektorých miestností otvárajú priložením čipovej karty k čítačke. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | * | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Na fakulte sa dvere do niektorých miestností otvárajú priložením čipovej karty k čítačke. | ||
* Každá karta má v sebe uložené identifikačné číslo. | * Každá karta má v sebe uložené identifikačné číslo. | ||
− | * Čítačka má v pamäti zoznam identifikačných čísel oprávnených osôb (študenti, | + | * Čítačka má v pamäti zoznam identifikačných čísel oprávnených osôb (študenti, vyučujúci a pod.). |
− | * Po priložení karty z nej | + | * Po priložení karty z nej prečíta číslo a zisťuje, či ho má vo svojom zozname. |
− | + | * Administrátor tiež potrebuje vedieť pridávať a uberať oprávnené osoby. | |
− | + | * Ako asi môže byť systém pracujúci so zoznamom identifikačných čísel naprogramovaný? | |
− | |||
− | |||
− | |||
− | |||
− | * | ||
− | |||
− | * | ||
− | |||
− | |||
− | Ako môže byť | ||
− | |||
− | |||
− | + | ===Dynamická množina=== | |
− | * | + | Chceli by sme vytvoriť dátovú štruktúru s nasledujúcou špecifikáciou. |
− | * | + | * Máme množinu ''A'', ktorá sa bude postupne meniť, preto ju nazývame dynamická množina. |
− | * | + | * Funkcia <tt>contains</tt> dostane množinu ''A'' a hodnotu ''x'' a zistí, či ''x'' patrí do ''A''. |
+ | * Funkcia <tt>add</tt> dostane množinu ''A'' a hodnotu ''x'' a pridá ''x'' do ''A''. | ||
+ | * Funkcia <tt>remove</tt> dostane množinu ''A'' a prvok ''x'' a odoberie ''x'' z ''A''. | ||
+ | * Pre jednoduchosť funkciu <tt>remove</tt> nebudeme dnes uvažovať. | ||
* Niekedy sa môžu zísť aj iné operácie. | * Niekedy sa môžu zísť aj iné operácie. | ||
− | + | Problém príslušnosti k množine sa vyskytuje aj v mnohých iných situáciách. | |
− | |||
− | |||
− | |||
− | |||
− | + | * Ako dnes uvidíme, dynamickú množinu môžeme implementovať rôznymi spôsobmi. | |
+ | * Hovoríme, že dynamická množina je '''abstraktný dátový typ''', špecifikuje totiž iba rozhranie, ktoré má dátová štruktúra poskytovať používateľovi, nie jeho implementáciu. | ||
+ | * Ak by sme zmenili implementáciu z jednej na inú, nemusíme nutne meniť programy, ktoré dynamickú množinu využívajú, pokiaľ k nej pristupujú iba pomocou uvedených funkcií. | ||
== Implementácie dynamických množín == | == Implementácie dynamických množín == | ||
− | + | * Pre jednoduchosť budeme uvažovať iba dynamickú množinu celých čísel. | |
− | + | * Dynamickú množinu budeme uchovávať v štruktúre <tt>set</tt>. | |
+ | * Navyše budeme mať implementovaných niekoľko funkcií, ktoré s dynamickými množinami pracujú. | ||
+ | * Kostra programu teda bude vyzerať pre ľubovoľnú implementáciu dynamickej množiny takto: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 112: | Riadok 46: | ||
}; | }; | ||
− | /* Funkcia | + | /* Funkcia vytvori prazdnu dynamicku mnozinu. */ |
void init(set &s) { | void init(set &s) { | ||
// ... | // ... | ||
} | } | ||
− | /* Funkcia | + | /* Funkcia zisti, ci prvok x patri do mnoziny s. */ |
bool contains(set &s, int x) { | bool contains(set &s, int x) { | ||
// ... | // ... | ||
} | } | ||
− | /* Funkcia | + | /* Funkcia prida prvok x do mnoziny s. */ |
void add(set &s, int x) { | void add(set &s, int x) { | ||
// ... | // ... | ||
} | } | ||
− | /* Funkcia | + | /* Funkcia uvolni mnozinu s z pamate. */ |
void destroy(set &s) { | void destroy(set &s) { | ||
// ... | // ... | ||
Riadok 133: | Riadok 67: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Bez ohľadu na implementáciu štruktúry <tt>set</tt> a uvedených funkcií už teraz môžeme napísať program, ktorý ich využíva | + | Bez ohľadu na implementáciu štruktúry <tt>set</tt> a uvedených funkcií už teraz môžeme napísať program, ktorý ich využíva. Z konzoly číta príkazy a postupne ich vykonáva. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 166: | Riadok 100: | ||
destroy(A); | destroy(A); | ||
− | |||
− | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Ukážeme si teraz niekoľko rôznych implementácii dynamickej množiny; začneme s dvoma, ktoré sú nám už | + | Ukážeme si teraz niekoľko rôznych implementácii dynamickej množiny; začneme s dvoma, ktoré sú nám už známe. |
=== Dynamická množina ako pole === | === Dynamická množina ako pole === | ||
Riadok 188: | Riadok 120: | ||
struct set { | struct set { | ||
− | int * | + | int *items; // Smerník na nultý prvok poľa |
− | int length; // | + | int length; // Počet prvkov v poli |
}; | }; | ||
void init(set &s) { | void init(set &s) { | ||
− | s. | + | s.items = new int[maxN]; |
s.length = 0; | s.length = 0; | ||
} | } | ||
bool contains(set &s, int x) { | bool contains(set &s, int x) { | ||
− | for (int i = 0; i < | + | for (int i = 0; i < s.length; i++) { |
− | if (s. | + | if (s.items[i] == x) { |
return true; | return true; | ||
} | } | ||
Riadok 208: | Riadok 140: | ||
void add(set &s, int x) { | void add(set &s, int x) { | ||
assert(s.length < maxN); | assert(s.length < maxN); | ||
− | s. | + | s.items[s.length] = x; |
s.length++; | s.length++; | ||
} | } | ||
void destroy(set &s) { | void destroy(set &s) { | ||
− | delete[] s. | + | delete[] s.items; |
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 219: | Riadok 151: | ||
===Dynamická množina ako utriedené pole === | ===Dynamická množina ako utriedené pole === | ||
Prvky množiny môžeme v poli uchovávať aj utriedené od najmenšieho po najväčšie. | Prvky množiny môžeme v poli uchovávať aj utriedené od najmenšieho po najväčšie. | ||
− | * Funkcia <tt>contains</tt> potom môže použiť binárne vyhľadávanie. Je teda rýchlejšia, ako v predchádzajúcom prípade (v poli veľkosti ''n'' sa pozrie len na približne log ''n'' pozícií; napríklad pre miliónprvkové pole sa pozrieme asi na 20 prvkov poľa). | + | * Funkcia <tt>contains</tt> potom môže použiť binárne vyhľadávanie. Je teda rýchlejšia, ako v predchádzajúcom prípade (v poli veľkosti ''n'' sa pozrie len na približne log<sub>2</sub> ''n'' pozícií; napríklad pre miliónprvkové pole sa pozrieme asi na 20 prvkov poľa). |
* Funkcia <tt>add</tt> ale musí vložiť prvok na správne miesto v utriedenom poli; je teda o dosť pomalšia. | * Funkcia <tt>add</tt> ale musí vložiť prvok na správne miesto v utriedenom poli; je teda o dosť pomalšia. | ||
Riadok 230: | Riadok 162: | ||
struct set { | struct set { | ||
− | int * | + | int *items; // smerník na nultý prvok poľa |
− | int length; // | + | int length; // počet prvkov v poli |
}; | }; | ||
void init(set &s) { | void init(set &s) { | ||
− | s. | + | s.items = new int[maxN]; |
s.length = 0; | s.length = 0; | ||
} | } | ||
Riadok 244: | Riadok 176: | ||
while (left <= right) { | while (left <= right) { | ||
int index = (left + right) / 2; | int index = (left + right) / 2; | ||
− | if (s. | + | if (s.items[index] == x) { |
return true; | return true; | ||
− | } else if (s. | + | } else if (s.items[index] > x) { |
right = index - 1; | right = index - 1; | ||
} else { | } else { | ||
Riadok 258: | Riadok 190: | ||
assert(s.length < maxN); | assert(s.length < maxN); | ||
int kam = s.length; | int kam = s.length; | ||
− | while (kam > 0 && s. | + | while (kam > 0 && s.items[kam - 1] > x) { |
− | s. | + | s.items[kam] = s.items[kam - 1]; |
kam--; | kam--; | ||
} | } | ||
− | s. | + | s.items[kam] = x; |
s.length++; | s.length++; | ||
} | } | ||
void destroy(set &s) { | void destroy(set &s) { | ||
− | delete[] s. | + | delete[] s.items; |
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 275: | Riadok 207: | ||
Dnes uvidíme ďalšie dva spôsoby implementácie dynamickej množiny: | Dnes uvidíme ďalšie dva spôsoby implementácie dynamickej množiny: | ||
− | * Množina ako ''' | + | * Množina ako '''spájaný zoznam''': |
** Ľahko pridáme nové prvky, nepotrebujeme vopred vedieť veľkosť. | ** Ľahko pridáme nové prvky, nepotrebujeme vopred vedieť veľkosť. | ||
** Nedá sa rýchlo binárne vyhľadávať. | ** Nedá sa rýchlo binárne vyhľadávať. | ||
** Založené na smerníkoch. | ** Založené na smerníkoch. | ||
− | * Množina pomocou ''' | + | * Množina pomocou '''hašovania''': |
** Často veľmi rýchle vyhľadávanie. | ** Často veľmi rýchle vyhľadávanie. | ||
** Použijeme polia aj spájané zoznamy. | ** Použijeme polia aj spájané zoznamy. | ||
+ | |||
+ | == Odbočka: smerníky a <tt>struct</tt> == | ||
+ | |||
+ | === Opakovanie základnej práce so smerníkmi === | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | int n = 7; // premenná typu int | ||
+ | int *p = &n; // smerník na int | ||
+ | // n, *p teraz znamenajú to iste | ||
+ | |||
+ | int *p2 = new int; // p2 ukazuje na alokovanú pamäť pre jeden int | ||
+ | *p2 = 7; // pomocou *p2 pracujem s touto pamäťou | ||
+ | delete p2; // uvoľním pamäť | ||
+ | p2 = p; // tu mením samotný semerník | ||
+ | p = NULL; // NULL "nikam neukazuje" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === Smerníky a <tt>struct</tt> === | ||
+ | |||
+ | Smerník môže ukazovať aj na <tt>struct</tt>. Operátory <tt>.</tt> (prístup k prvku štruktúry) a <tt>[]</tt> (prístup k prvku poľa) majú vyššiu prioritu ako operátory <tt>*</tt> (dereferencia smerníka) a <tt>&</tt> (adresa). Preto napríklad: | ||
+ | * Zápis <tt>*s.cokolvek</tt> je to isté ako <tt>*(s.cokolvek)</tt> a vyjadruje dereferenciu smerníka <tt>s.cokolvek</tt>. | ||
+ | * Zápis <tt>(*p).cokolvek</tt> vyjadruje prvok <tt>cokolvek</tt> štruktúry získanej dereferenciou smerníka <tt>p</tt>. | ||
+ | * Zvyčajne je potrebnejší zápis <tt>(*p).cokolvek</tt>; existuje preň preto skratka <tt>p->cokolvek</tt>. | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | struct bod { | ||
+ | int x, y; | ||
+ | }; | ||
+ | |||
+ | // ... | ||
+ | |||
+ | bod b; | ||
+ | b.x = 0; | ||
+ | b.y = 0; | ||
+ | bod *p = &b; // p ukazuje na bod b | ||
+ | |||
+ | bod *p2 = new bod; // alokovanie nového bodu | ||
+ | (*p2).x = 20; // bod, na ktorý ukazuje p2, bude mať x 20 | ||
+ | p2->y = 10; // bod, na ktorý ukazuje p2, bude mať y 10 | ||
+ | delete p2; // uvoľnenie pamäte | ||
+ | </syntaxhighlight> | ||
+ | |||
==Spájané zoznamy== | ==Spájané zoznamy== | ||
− | ''Spájaný zoznam'' (angl. ''linked list'') je postupnosť uzlov rovnakého typu usporiadaných za sebou. Každý uzol pritom pozostáva z dvoch častí: | + | '''Spájaný zoznam''' (angl. ''linked list'') je postupnosť uzlov rovnakého typu usporiadaných za sebou. Každý uzol pritom pozostáva z dvoch častí: |
* Samotné dáta; v našom prípade jedno číslo typu <tt>int</tt>. | * Samotné dáta; v našom prípade jedno číslo typu <tt>int</tt>. | ||
− | * Smerník, ktorý ukazuje na nasledujúci prvok zoznamu | + | * Smerník <tt>next</tt>, ktorý ukazuje na nasledujúci prvok zoznamu. |
− | + | ** Tieto smerníky umožňujú pohybovať sa po zozname zľava doprava. | |
− | Posledný uzol zoznamu nemá následníka | + | ** Posledný uzol zoznamu nemá následníka, smerník <tt>next</tt> bude mať hodnotu <tt>NULL</tt>. |
Štruktúra spájaného zoznamu je znázornená na nasledujúcom obrázku: | Štruktúra spájaného zoznamu je znázornená na nasledujúcom obrázku: | ||
[[Image:PROG-list.png|300px]] | [[Image:PROG-list.png|300px]] | ||
− | |||
− | |||
Uzol jednosmerne spájaného zoznamu budeme reprezentovať pomocou <tt>struct</tt>-u <tt>node</tt>: | Uzol jednosmerne spájaného zoznamu budeme reprezentovať pomocou <tt>struct</tt>-u <tt>node</tt>: | ||
Riadok 307: | Riadok 279: | ||
Vo vnútri definície typu <tt>node</tt> teda používame smerník na samotný typ <tt>node</tt>. | Vo vnútri definície typu <tt>node</tt> teda používame smerník na samotný typ <tt>node</tt>. | ||
− | + | Samotná množina reprezentovaná spájaným zoznamom je potom štruktúra <tt>set</tt> obsahujúca iba smerník na prvý prvok zoznamu. Ak je zoznam prázdny, bude tento smerník <tt>NULL</tt>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | /* Struktura | + | /* Struktura implementujuca mnozinu ako spajany zoznam: */ |
struct set { | struct set { | ||
node *first; // Smernik na prvy uzol zoznamu | node *first; // Smernik na prvy uzol zoznamu | ||
Riadok 327: | Riadok 294: | ||
===Vkladanie na začiatok zoznamu=== | ===Vkladanie na začiatok zoznamu=== | ||
− | Nasledujúca funkcia na začiatok zoznamu vloží nový uzol s dátami x: | + | Nasledujúca funkcia na začiatok zoznamu vloží nový uzol s dátami ''x'': |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
void add(set &s, int x) { | void add(set &s, int x) { | ||
− | node *p = new node; // | + | node *p = new node; // Vytvoríme nový uzol ... |
− | p->data = x; // | + | p->data = x; // jeho data nastavíme na x. |
− | p->next = s.first; // | + | p->next = s.first; // jeho následníkom bude prvok, ktorý bol prvý |
− | s.first = p; // | + | s.first = p; // uzol p bude novým prvým prvkom |
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 353: | Riadok 320: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | Funkcia by sa dala napísať aj pomocou for cyklu | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | bool contains(set &s, int x) { | ||
+ | for(node *p = s.first; p != NULL; p = p->next) { | ||
+ | if (p->data == x) { | ||
+ | return true; | ||
+ | } | ||
+ | } | ||
+ | return false; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | V tejto forme sa viac podobá na funkciu pre polia: | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | bool contains(set &s, int x) { | ||
+ | for (int i = 0; i < s.length; i++) { | ||
+ | if (s.items[i] == x) { | ||
+ | return true; | ||
+ | } | ||
+ | } | ||
+ | return false; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Smerník <tt>p</tt> je teda v zoznamoch ekvivalentom indexu <tt>i</tt> | ||
+ | * Inicializácia je <tt>p = s.first</tt> namiesto <tt>i = 0</tt> | ||
+ | * Posun na ďalší prvok je <tt>p = p->next</tt> namiesto <tt>i++</tt> | ||
+ | * Podmienka na pokračovanie je <tt>p != NULL</tt> namiesto <tt>i < s.length</tt> | ||
=== Uvoľnenie zoznamu === | === Uvoľnenie zoznamu === | ||
− | Funkcia | + | Funkcia, ktorá uvoľní zoznam z pamäti, pracuje podobne: prechádza postupne zoznam od začiatku až po jeho koniec a uvoľňuje z pamäte jednotlivé uzly. Treba si však dať pozor na to, aby sme smerník na nasledujúci uzol získali ešte predtým, než z pamäti uvoľníme ten predošlý. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 362: | Riadok 358: | ||
node *p = s.first; | node *p = s.first; | ||
while (p != NULL) { | while (p != NULL) { | ||
− | node * | + | node *p2 = p->next; |
delete p; | delete p; | ||
− | p = | + | p = p2; |
} | } | ||
} | } | ||
Riadok 383: | Riadok 379: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | == | + | === Varianty spájaných zoznamov === |
+ | * V našom zozname si v každom uzle pamätáme iba smerník na následníka, hovoríme o ''jednosmerne spájanom zozname''. | ||
+ | * Často sú užitočné aj ''obojsmerne spájané zoznamy'', kde sa v každom uzle uchováva aj smerník na predchodcu; takéto zoznamy sú ale o niečo náročnejšie na údržbu. | ||
+ | * Používajú sa dokonca aj cyklické zoznamy, kde posledný prvok ukazuje späť na prvý prvok zoznamu. | ||
+ | |||
+ | == Hašovanie == | ||
=== Implementácia množiny priamym adresovaním === | === Implementácia množiny priamym adresovaním === | ||
− | Úplne odlišným spôsobom | + | Úplne odlišným spôsobom implementácie dynamickej množiny je tzv. ''priame adresovanie'' (angl. ''direct addressing''). |
− | * Funkcie <tt>contains</tt> aj <tt>add</tt> sú veľmi rýchle. | + | * Množinu všetkých možných hodnôt, ktoré v danej implementácii môžeme chcieť do množiny pridať, nazveme univerzum ''U''. |
− | * Problémom tohto prístupu je ale vysoká pamäťová zložitosť | + | * Predchádzajúce implementácie sa ľahko dali upraviť na rôzne univerzá (celé čísla, desatinné čísla, smerníky na zložitejšie štruktúry, napr. struct, pole, reťazec). |
− | * Veľmi efektívne pre malé univerzá (napr. cifry | + | * Na rozdiel od toho sa priame adresovanie dá použiť iba ak univerzum je ''U'' = {0,1,...,''m''-1} pre nejaké rozumne malé prirodzené číslo ''m''. |
+ | * Podmnožinu ''A'' univerza ''U'' potom môžeme reprezentovať ako pole booleovských hodnôt dĺžky ''m'', kde ''i''-ty prvok poľa bude <tt>true</tt> práve vtedy, keď ''i'' patrí do ''A''. | ||
+ | * Túto reprezentáciu sme používali napríklad v poli <tt>bolo</tt> pri prehľadávaní s návratom. | ||
+ | |||
+ | * Funkcie <tt>contains</tt> aj <tt>add</tt> sú potom veľmi jednoduché a rýchle. | ||
+ | * Problémom tohto prístupu je ale vysoká pamäťová zložitosť, ak je číslo ''m'' veľké. | ||
+ | * Veľmi efektívne pre malé univerzá (napr. cifry 0,...,9, všetky znaky anglickej abecedy, všetky znaky s ASCII hodnotami od 0 po 255, a pod.). | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cassert> | #include <cassert> | ||
− | // | + | /* Maximalne povolene cislo v mnozine */ |
− | + | const int m = 1000; | |
− | const int | ||
− | /* Struktura | + | /* Struktura implementujuca mnozinu priamym adresovanim: */ |
struct set { | struct set { | ||
− | bool * | + | bool *isin; |
}; | }; | ||
void init(set &s) { | void init(set &s) { | ||
− | s. | + | s.isin = new bool[m]; |
− | for (int i = 0; i < | + | for (int i = 0; i < m; i++) { |
− | s. | + | s.isin[i] = false; |
} | } | ||
} | } | ||
bool contains(set &s, int x) { | bool contains(set &s, int x) { | ||
− | assert(x >= 0 && x <= | + | assert(x >= 0 && x <= m - 1); |
− | return s. | + | return s.isin[x]; |
} | } | ||
void add(set &s, int x) { | void add(set &s, int x) { | ||
− | assert(x >= 0 && x <= | + | assert(x >= 0 && x <= m - 1); |
− | s. | + | s.isin[x] = true; |
} | } | ||
void destroy(set &s) { | void destroy(set &s) { | ||
− | delete[] s. | + | delete[] s.isin; |
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | === Jednoduché | + | === Jednoduché hašovanie === |
− | Priame adresovanie sa | + | Priame adresovanie sa nehodí pre veľké univerzá, lebo by vyžadovalo veľa pamäte. |
− | '' | + | '''Hašovanie''' (angl. hashing) je jednoduchá finta, ktorá funguje nasledovne: |
− | * Nech ''U'' je univerzum všetkých možných prvkov množiny | + | * Nech ''U'' je univerzum všetkých možných prvkov množiny. |
− | * Vytvoríme | + | * Vytvoríme '''hašovaciu tabuľku''' (angl. hash table), čo je pole nejakej rozumnej veľkosti ''m''. |
− | * Naprogramujeme '' | + | * Naprogramujeme ''hašovaciu funkciu'', ktorá transformuje prvky univerza ''U'' na indexy hašovacej tabuľky; pôjde teda o funkciu ''h'': ''U'' -> {0, 1, ... , ''m''−1}. |
− | + | * Najjednoduchšia hašovacia funkcia pre celočíselné prvky je ''h''(''x'') = |''x''| mod ''m''. | |
− | * Najjednoduchšia | + | ** |''x''| spočítame funkciou <tt>abs</tt> z knižnice <tt>cstdlib</tt> |
− | ** '' | + | ** Absolútnu hodnotu používame, lebo napríklad <tt>-10 % 3</tt> je -1, čo mimo rozsahu indexov tabuľky |
+ | ** V praxi sa používajú zložitejšie hašovacie funkcie. Ideálne je hašovacia funkcia jednoduchá a rýchla, ale pritom hodnoty do tabuľky distribuuje rovnomerne, aby sa príliš často nestávalo, že dva prvky sa namapujú na to isté políčko | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 442: | Riadok 449: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | Pre ''m = 5'' je táto funkcia znázornená na nasledujúcom obrázku. | ||
[[Súbor:hash1.png]] | [[Súbor:hash1.png]] | ||
− | + | Prvý pokus o prácu hašovacou tabuľkou by teda mohol vyzerať takto: | |
'''Vkladanie''' prvku ''x'': | '''Vkladanie''' prvku ''x'': | ||
− | * Spočítame <tt>index = hash(x, m)</tt> a prvok vložíme na pozíciu <tt> | + | * Spočítame <tt>index = hash(x, m)</tt> a prvok vložíme na pozíciu <tt>table[index]</tt>. |
'''Vyhľadávanie''' prvku ''x'': | '''Vyhľadávanie''' prvku ''x'': | ||
Riadok 455: | Riadok 464: | ||
'''Problémy''': | '''Problémy''': | ||
− | * Na akú hodnotu inicializovať prvky poľa <tt> | + | * Na akú hodnotu inicializovať prvky poľa <tt>table</tt>? |
* Čo ak budeme potrebovať vložiť prvok na miesto, kde je už niečo uložené? | * Čo ak budeme potrebovať vložiť prvok na miesto, kde je už niečo uložené? | ||
=== Kolízie === | === Kolízie === | ||
− | Pri vkladaní prvku sme narazili na problém, ak na už | + | * Pri vkladaní prvku sme narazili na problém, ak na už obsadené miesto chceme vložiť iný prvok. |
− | * | + | * Ak sa dva prvky ''x'' a ''y'' sa zahašujú na rovnakú pozíciu ''h''(''x'') = ''h''(''y''), hovoríme, že nastala '''kolízia'''. |
− | + | * Existujú rôzne prístupy na riešenie kolízií, môžeme napríklad hľadať iné voľné miesto v tabuľke. | |
− | + | * V našom programe kolízie vyriešime tak, že v každom políčku tabuľky uložíme spájaný zoznam všetkých prvkov, ktoré sa tam zahašovali. | |
− | + | ** Táto situácia je znázornená na nasledujúcom obrázku, v ktorom šípky zodpovedajú vkladaniam prvkov (celých čísel) do množiny reprezentovanej hašovacou tabuľkou. | |
− | |||
− | |||
− | + | [[Súbor:Hash2.png]] | |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdlib> | #include <cstdlib> | ||
− | + | /* hašovacia funkcia: */ | |
− | + | int h(int x, int m) { | |
− | /* | ||
− | int | ||
return abs(x) % m; | return abs(x) % m; | ||
} | } | ||
− | /* | + | /* štruktúra reprezentujúca jeden prvok spájaného zoznamu: */ |
struct node { | struct node { | ||
int data; | int data; | ||
Riadok 486: | Riadok 491: | ||
}; | }; | ||
− | /* | + | /* štruktúra implementujúca dynamickú množinu hašovaním: */ |
struct set { | struct set { | ||
− | node ** | + | node **table; // pole smerníkov na začiatky zoznamov |
− | int m; | + | int m; // veľkost hašovacej tabuľky |
}; | }; | ||
− | void init(set &s, int m) { // | + | void init(set &s, int m) { |
+ | // veľkosť tabuľky je parametrom funkcie init | ||
s.m = m; | s.m = m; | ||
− | s. | + | s.table = new node *[m]; |
− | for (int i = 0; i < | + | for (int i = 0; i < m; i++) { |
− | s. | + | s.table[i] = NULL; |
} | } | ||
} | } | ||
bool contains(set &s, int x) { | bool contains(set &s, int x) { | ||
− | int index = | + | int index = h(x, s.m); // spočítame políčko tabuľky |
− | node *p = s. | + | node *p = s.table[index]; // p ukazuje na začiatok zoznamu |
− | + | while (p != NULL) { // prechádzame zoznam, hľadáme x | |
− | while (p != NULL) { | ||
if (p->data == x) { | if (p->data == x) { | ||
return true; | return true; | ||
Riadok 514: | Riadok 519: | ||
void add(set &s, int x) { | void add(set &s, int x) { | ||
− | int index = | + | int index = h(x, s.m); // spočítame políčko tabuľky |
− | node * | + | node *p = new node; // vytvoríme nový uzol |
− | + | p->data = x; | |
− | + | p->next = s.table[index]; // uzol vložíme na začiatok zoznamu | |
− | s. | + | s.table[index] = p; |
} | } | ||
void destroy(set &s) { | void destroy(set &s) { | ||
− | for (int i = 0; i < | + | for (int i = 0; i < s.m; i++) { |
− | node *p = s. | + | node *p = s.table[i]; // uvoľníme zoznam s.table[i] |
while (p != NULL) { | while (p != NULL) { | ||
− | node * | + | node *p2 = p->next; |
delete p; | delete p; | ||
− | p = | + | p = p2; |
} | } | ||
} | } | ||
− | delete[] s. | + | delete[] s.table; |
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | '''Cvičenie:''' Ako bude vyzerať | + | '''Cvičenie:''' Ako bude vyzerať hašovacia tabuľka pri riešení kolízií pomocou spájaných zoznamov, ak hašovacia funkcia je |x| mod 5 a vkladáme prvky 13, -2, 0, 8, 10, 17? |
===Zložitosť=== | ===Zložitosť=== | ||
− | * Rýchlosť závisí od | + | * Rýchlosť závisí od veľkosti tabuľky ''m'', hašovacej funkcie a počtu kolízií. |
− | * V najhoršom prípade sa všetky prvky | + | * V najhoršom prípade sa všetky prvky zahašujú do toho istého políčka, a teda musíme pri hľadaní prejsť všetky prvky množiny. |
* Ak máme šťastie a v každom políčku máme len málo prvkov, bude aj vyhľadávanie rýchle. | * Ak máme šťastie a v každom políčku máme len málo prvkov, bude aj vyhľadávanie rýchle. | ||
− | ** Ak je tabuľka dosť veľká a | + | ** Ak je tabuľka dosť veľká a hašovacia funkcia vhodne zvolená, tento prípad je pomerne obvyklý. |
− | ** | + | ** Hašovacie tabuľky sa často používajú v praxi. |
− | * Viac budúci rok na predmete | + | * Viac budúci rok na predmete Algoritmy a dátové štruktúry. |
Aktuálna revízia z 10:23, 8. november 2023
Obsah
Oznamy
- Piatkové cvičenia sú povinné pre tých, ktorí nemali rozcvičku minulý týždeň, informáciu máte na testovači.
- DÚ2 odovzdávajte do utorka 14.11. 22:00.
- Na domácich úlohách a cvičeniach neodpisujte.
- Ak vás prichytíme, stratíte body a hrozí vám aj disciplinárna komisia fakulty.
- Hlavne sa ale nič nenaučíte a budete mať problémy na skúške a semestrálnom teste, ako aj na ďalších predmetoch.
- Semestrálny test bude v stredu 13.12. 18:10. Opravný termín v januári.
- Ak sa vyskytne konflikt s iným predmetom, hláste to vyučujúcim čo najskôr.
Dynamická množina
Motivačný príklad
- Na fakulte sa dvere do niektorých miestností otvárajú priložením čipovej karty k čítačke.
- Každá karta má v sebe uložené identifikačné číslo.
- Čítačka má v pamäti zoznam identifikačných čísel oprávnených osôb (študenti, vyučujúci a pod.).
- Po priložení karty z nej prečíta číslo a zisťuje, či ho má vo svojom zozname.
- Administrátor tiež potrebuje vedieť pridávať a uberať oprávnené osoby.
- Ako asi môže byť systém pracujúci so zoznamom identifikačných čísel naprogramovaný?
Dynamická množina
Chceli by sme vytvoriť dátovú štruktúru s nasledujúcou špecifikáciou.
- Máme množinu A, ktorá sa bude postupne meniť, preto ju nazývame dynamická množina.
- Funkcia contains dostane množinu A a hodnotu x a zistí, či x patrí do A.
- Funkcia add dostane množinu A a hodnotu x a pridá x do A.
- Funkcia remove dostane množinu A a prvok x a odoberie x z A.
- Pre jednoduchosť funkciu remove nebudeme dnes uvažovať.
- Niekedy sa môžu zísť aj iné operácie.
Problém príslušnosti k množine sa vyskytuje aj v mnohých iných situáciách.
- Ako dnes uvidíme, dynamickú množinu môžeme implementovať rôznymi spôsobmi.
- Hovoríme, že dynamická množina je abstraktný dátový typ, špecifikuje totiž iba rozhranie, ktoré má dátová štruktúra poskytovať používateľovi, nie jeho implementáciu.
- Ak by sme zmenili implementáciu z jednej na inú, nemusíme nutne meniť programy, ktoré dynamickú množinu využívajú, pokiaľ k nej pristupujú iba pomocou uvedených funkcií.
Implementácie dynamických množín
- Pre jednoduchosť budeme uvažovať iba dynamickú množinu celých čísel.
- Dynamickú množinu budeme uchovávať v štruktúre set.
- Navyše budeme mať implementovaných niekoľko funkcií, ktoré s dynamickými množinami pracujú.
- Kostra programu teda bude vyzerať pre ľubovoľnú implementáciu dynamickej množiny takto:
/* Struktura reprezentujuca dynamicku mnozinu. */
struct set {
// ...
};
/* Funkcia vytvori prazdnu dynamicku mnozinu. */
void init(set &s) {
// ...
}
/* Funkcia zisti, ci prvok x patri do mnoziny s. */
bool contains(set &s, int x) {
// ...
}
/* Funkcia prida prvok x do mnoziny s. */
void add(set &s, int x) {
// ...
}
/* Funkcia uvolni mnozinu s z pamate. */
void destroy(set &s) {
// ...
}
Bez ohľadu na implementáciu štruktúry set a uvedených funkcií už teraz môžeme napísať program, ktorý ich využíva. Z konzoly číta príkazy a postupne ich vykonáva.
#include <iostream>
#include <cstring>
using namespace std;
// ...
const int maxlength = 100;
int main(void) {
set A;
init(A);
while (true) {
char prikaz[maxlength];
cin.width(maxlength);
cin >> prikaz;
if (strcmp(prikaz, "contains") == 0) {
int x;
cin >> x;
cout << contains(A, x) << endl;
} else if (strcmp(prikaz, "add") == 0) {
int x;
cin >> x;
add(A, x);
} else if (strcmp(prikaz, "end") == 0) {
break;
}
}
destroy(A);
}
Ukážeme si teraz niekoľko rôznych implementácii dynamickej množiny; začneme s dvoma, ktoré sú nám už známe.
Dynamická množina ako pole
Dynamickú množinu môžeme implementovať tak, že jej prvky budeme ukladať do poľa v ľubovoľnom poradí.
- Funkcia contains musí zakaždým prejsť celé pole lineárnym prehľadávaním (nie je teda zrovna rýchla).
- Funkcia add je naopak veľmi rýchla: stačí pridať prvok na koniec poľa.
- Je ale potrebné dávať pozor na prekročenie kapacity poľa (mohli by sme použiť dynamické pole).
#include <cassert>
// ...
const int maxN = 1000;
struct set {
int *items; // Smerník na nultý prvok poľa
int length; // Počet prvkov v poli
};
void init(set &s) {
s.items = new int[maxN];
s.length = 0;
}
bool contains(set &s, int x) {
for (int i = 0; i < s.length; i++) {
if (s.items[i] == x) {
return true;
}
}
return false;
}
void add(set &s, int x) {
assert(s.length < maxN);
s.items[s.length] = x;
s.length++;
}
void destroy(set &s) {
delete[] s.items;
}
Dynamická množina ako utriedené pole
Prvky množiny môžeme v poli uchovávať aj utriedené od najmenšieho po najväčšie.
- Funkcia contains potom môže použiť binárne vyhľadávanie. Je teda rýchlejšia, ako v predchádzajúcom prípade (v poli veľkosti n sa pozrie len na približne log2 n pozícií; napríklad pre miliónprvkové pole sa pozrieme asi na 20 prvkov poľa).
- Funkcia add ale musí vložiť prvok na správne miesto v utriedenom poli; je teda o dosť pomalšia.
#include <cassert>
// ...
const int maxN = 1000;
struct set {
int *items; // smerník na nultý prvok poľa
int length; // počet prvkov v poli
};
void init(set &s) {
s.items = new int[maxN];
s.length = 0;
}
bool contains(set &s, int x) {
int left = 0;
int right = s.length - 1;
while (left <= right) {
int index = (left + right) / 2;
if (s.items[index] == x) {
return true;
} else if (s.items[index] > x) {
right = index - 1;
} else {
left = index + 1;
}
}
return false;
}
void add(set &s, int x) {
assert(s.length < maxN);
int kam = s.length;
while (kam > 0 && s.items[kam - 1] > x) {
s.items[kam] = s.items[kam - 1];
kam--;
}
s.items[kam] = x;
s.length++;
}
void destroy(set &s) {
delete[] s.items;
}
Ďalšie možnosti implementácie dynamickej množiny (plán na dnes)
Dnes uvidíme ďalšie dva spôsoby implementácie dynamickej množiny:
- Množina ako spájaný zoznam:
- Ľahko pridáme nové prvky, nepotrebujeme vopred vedieť veľkosť.
- Nedá sa rýchlo binárne vyhľadávať.
- Založené na smerníkoch.
- Množina pomocou hašovania:
- Často veľmi rýchle vyhľadávanie.
- Použijeme polia aj spájané zoznamy.
Odbočka: smerníky a struct
Opakovanie základnej práce so smerníkmi
int n = 7; // premenná typu int
int *p = &n; // smerník na int
// n, *p teraz znamenajú to iste
int *p2 = new int; // p2 ukazuje na alokovanú pamäť pre jeden int
*p2 = 7; // pomocou *p2 pracujem s touto pamäťou
delete p2; // uvoľním pamäť
p2 = p; // tu mením samotný semerník
p = NULL; // NULL "nikam neukazuje"
Smerníky a struct
Smerník môže ukazovať aj na struct. Operátory . (prístup k prvku štruktúry) a [] (prístup k prvku poľa) majú vyššiu prioritu ako operátory * (dereferencia smerníka) a & (adresa). Preto napríklad:
- Zápis *s.cokolvek je to isté ako *(s.cokolvek) a vyjadruje dereferenciu smerníka s.cokolvek.
- Zápis (*p).cokolvek vyjadruje prvok cokolvek štruktúry získanej dereferenciou smerníka p.
- Zvyčajne je potrebnejší zápis (*p).cokolvek; existuje preň preto skratka p->cokolvek.
struct bod {
int x, y;
};
// ...
bod b;
b.x = 0;
b.y = 0;
bod *p = &b; // p ukazuje na bod b
bod *p2 = new bod; // alokovanie nového bodu
(*p2).x = 20; // bod, na ktorý ukazuje p2, bude mať x 20
p2->y = 10; // bod, na ktorý ukazuje p2, bude mať y 10
delete p2; // uvoľnenie pamäte
Spájané zoznamy
Spájaný zoznam (angl. linked list) je postupnosť uzlov rovnakého typu usporiadaných za sebou. Každý uzol pritom pozostáva z dvoch častí:
- Samotné dáta; v našom prípade jedno číslo typu int.
- Smerník next, ktorý ukazuje na nasledujúci prvok zoznamu.
- Tieto smerníky umožňujú pohybovať sa po zozname zľava doprava.
- Posledný uzol zoznamu nemá následníka, smerník next bude mať hodnotu NULL.
Štruktúra spájaného zoznamu je znázornená na nasledujúcom obrázku:
Uzol jednosmerne spájaného zoznamu budeme reprezentovať pomocou struct-u node:
/* Struktura reprezentujuca uzol jednosmerne spajaneho zoznamu: */
struct node {
int data; // Hodnota ulozena v danom uzle
node *next; // Smernik na nasledujuci uzol
};
Vo vnútri definície typu node teda používame smerník na samotný typ node.
Samotná množina reprezentovaná spájaným zoznamom je potom štruktúra set obsahujúca iba smerník na prvý prvok zoznamu. Ak je zoznam prázdny, bude tento smerník NULL.
/* Struktura implementujuca mnozinu ako spajany zoznam: */
struct set {
node *first; // Smernik na prvy uzol zoznamu
};
void init(set &s) {
s.first = NULL;
}
Vkladanie na začiatok zoznamu
Nasledujúca funkcia na začiatok zoznamu vloží nový uzol s dátami x:
void add(set &s, int x) {
node *p = new node; // Vytvoríme nový uzol ...
p->data = x; // jeho data nastavíme na x.
p->next = s.first; // jeho následníkom bude prvok, ktorý bol prvý
s.first = p; // uzol p bude novým prvým prvkom
}
Vyhľadávanie v zozname
Funkcia vyhľadávajúca číslo x v zozname bude pracovať tak, že postupne prehľadáva zoznam od jeho začiatku, s využitím smerníkov na nasledujúce prvky:
bool contains(set &s, int x) {
node *p = s.first;
while (p != NULL) {
if (p->data == x) {
return true;
}
p = p->next;
}
return false;
}
Funkcia by sa dala napísať aj pomocou for cyklu
bool contains(set &s, int x) {
for(node *p = s.first; p != NULL; p = p->next) {
if (p->data == x) {
return true;
}
}
return false;
}
V tejto forme sa viac podobá na funkciu pre polia:
bool contains(set &s, int x) {
for (int i = 0; i < s.length; i++) {
if (s.items[i] == x) {
return true;
}
}
return false;
}
- Smerník p je teda v zoznamoch ekvivalentom indexu i
- Inicializácia je p = s.first namiesto i = 0
- Posun na ďalší prvok je p = p->next namiesto i++
- Podmienka na pokračovanie je p != NULL namiesto i < s.length
Uvoľnenie zoznamu
Funkcia, ktorá uvoľní zoznam z pamäti, pracuje podobne: prechádza postupne zoznam od začiatku až po jeho koniec a uvoľňuje z pamäte jednotlivé uzly. Treba si však dať pozor na to, aby sme smerník na nasledujúci uzol získali ešte predtým, než z pamäti uvoľníme ten predošlý.
void destroy(set &s) {
node *p = s.first;
while (p != NULL) {
node *p2 = p->next;
delete p;
p = p2;
}
}
Výpis zoznamu
Môžeme napísať aj nasledujúcu funkciu, ktorá po zavolaní vypíše obsah celého zoznamu:
void print(set &s) {
node *p = s.first;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
Varianty spájaných zoznamov
- V našom zozname si v každom uzle pamätáme iba smerník na následníka, hovoríme o jednosmerne spájanom zozname.
- Často sú užitočné aj obojsmerne spájané zoznamy, kde sa v každom uzle uchováva aj smerník na predchodcu; takéto zoznamy sú ale o niečo náročnejšie na údržbu.
- Používajú sa dokonca aj cyklické zoznamy, kde posledný prvok ukazuje späť na prvý prvok zoznamu.
Hašovanie
Implementácia množiny priamym adresovaním
Úplne odlišným spôsobom implementácie dynamickej množiny je tzv. priame adresovanie (angl. direct addressing).
- Množinu všetkých možných hodnôt, ktoré v danej implementácii môžeme chcieť do množiny pridať, nazveme univerzum U.
- Predchádzajúce implementácie sa ľahko dali upraviť na rôzne univerzá (celé čísla, desatinné čísla, smerníky na zložitejšie štruktúry, napr. struct, pole, reťazec).
- Na rozdiel od toho sa priame adresovanie dá použiť iba ak univerzum je U = {0,1,...,m-1} pre nejaké rozumne malé prirodzené číslo m.
- Podmnožinu A univerza U potom môžeme reprezentovať ako pole booleovských hodnôt dĺžky m, kde i-ty prvok poľa bude true práve vtedy, keď i patrí do A.
- Túto reprezentáciu sme používali napríklad v poli bolo pri prehľadávaní s návratom.
- Funkcie contains aj add sú potom veľmi jednoduché a rýchle.
- Problémom tohto prístupu je ale vysoká pamäťová zložitosť, ak je číslo m veľké.
- Veľmi efektívne pre malé univerzá (napr. cifry 0,...,9, všetky znaky anglickej abecedy, všetky znaky s ASCII hodnotami od 0 po 255, a pod.).
#include <cassert>
/* Maximalne povolene cislo v mnozine */
const int m = 1000;
/* Struktura implementujuca mnozinu priamym adresovanim: */
struct set {
bool *isin;
};
void init(set &s) {
s.isin = new bool[m];
for (int i = 0; i < m; i++) {
s.isin[i] = false;
}
}
bool contains(set &s, int x) {
assert(x >= 0 && x <= m - 1);
return s.isin[x];
}
void add(set &s, int x) {
assert(x >= 0 && x <= m - 1);
s.isin[x] = true;
}
void destroy(set &s) {
delete[] s.isin;
}
Jednoduché hašovanie
Priame adresovanie sa nehodí pre veľké univerzá, lebo by vyžadovalo veľa pamäte.
Hašovanie (angl. hashing) je jednoduchá finta, ktorá funguje nasledovne:
- Nech U je univerzum všetkých možných prvkov množiny.
- Vytvoríme hašovaciu tabuľku (angl. hash table), čo je pole nejakej rozumnej veľkosti m.
- Naprogramujeme hašovaciu funkciu, ktorá transformuje prvky univerza U na indexy hašovacej tabuľky; pôjde teda o funkciu h: U -> {0, 1, ... , m−1}.
- Najjednoduchšia hašovacia funkcia pre celočíselné prvky je h(x) = |x| mod m.
- |x| spočítame funkciou abs z knižnice cstdlib
- Absolútnu hodnotu používame, lebo napríklad -10 % 3 je -1, čo mimo rozsahu indexov tabuľky
- V praxi sa používajú zložitejšie hašovacie funkcie. Ideálne je hašovacia funkcia jednoduchá a rýchla, ale pritom hodnoty do tabuľky distribuuje rovnomerne, aby sa príliš často nestávalo, že dva prvky sa namapujú na to isté políčko
int hash(int x, int m) {
return abs(x) % m;
}
Pre m = 5 je táto funkcia znázornená na nasledujúcom obrázku.
Prvý pokus o prácu hašovacou tabuľkou by teda mohol vyzerať takto:
Vkladanie prvku x:
- Spočítame index = hash(x, m) a prvok vložíme na pozíciu table[index].
Vyhľadávanie prvku x:
- Ak je prvok s kľúčom x v tabuľke, musí byť na indexe hash(x, m).
- Skontrolujeme túto pozíciu a ak tam je niečo iné ako x, prvok x sa v tabuľke nenachádza.
Problémy:
- Na akú hodnotu inicializovať prvky poľa table?
- Čo ak budeme potrebovať vložiť prvok na miesto, kde je už niečo uložené?
Kolízie
- Pri vkladaní prvku sme narazili na problém, ak na už obsadené miesto chceme vložiť iný prvok.
- Ak sa dva prvky x a y sa zahašujú na rovnakú pozíciu h(x) = h(y), hovoríme, že nastala kolízia.
- Existujú rôzne prístupy na riešenie kolízií, môžeme napríklad hľadať iné voľné miesto v tabuľke.
- V našom programe kolízie vyriešime tak, že v každom políčku tabuľky uložíme spájaný zoznam všetkých prvkov, ktoré sa tam zahašovali.
- Táto situácia je znázornená na nasledujúcom obrázku, v ktorom šípky zodpovedajú vkladaniam prvkov (celých čísel) do množiny reprezentovanej hašovacou tabuľkou.
#include <cstdlib>
/* hašovacia funkcia: */
int h(int x, int m) {
return abs(x) % m;
}
/* štruktúra reprezentujúca jeden prvok spájaného zoznamu: */
struct node {
int data;
node *next;
};
/* štruktúra implementujúca dynamickú množinu hašovaním: */
struct set {
node **table; // pole smerníkov na začiatky zoznamov
int m; // veľkost hašovacej tabuľky
};
void init(set &s, int m) {
// veľkosť tabuľky je parametrom funkcie init
s.m = m;
s.table = new node *[m];
for (int i = 0; i < m; i++) {
s.table[i] = NULL;
}
}
bool contains(set &s, int x) {
int index = h(x, s.m); // spočítame políčko tabuľky
node *p = s.table[index]; // p ukazuje na začiatok zoznamu
while (p != NULL) { // prechádzame zoznam, hľadáme x
if (p->data == x) {
return true;
}
p = p->next;
}
return false;
}
void add(set &s, int x) {
int index = h(x, s.m); // spočítame políčko tabuľky
node *p = new node; // vytvoríme nový uzol
p->data = x;
p->next = s.table[index]; // uzol vložíme na začiatok zoznamu
s.table[index] = p;
}
void destroy(set &s) {
for (int i = 0; i < s.m; i++) {
node *p = s.table[i]; // uvoľníme zoznam s.table[i]
while (p != NULL) {
node *p2 = p->next;
delete p;
p = p2;
}
}
delete[] s.table;
}
Cvičenie: Ako bude vyzerať hašovacia tabuľka pri riešení kolízií pomocou spájaných zoznamov, ak hašovacia funkcia je |x| mod 5 a vkladáme prvky 13, -2, 0, 8, 10, 17?
Zložitosť
- Rýchlosť závisí od veľkosti tabuľky m, hašovacej funkcie a počtu kolízií.
- V najhoršom prípade sa všetky prvky zahašujú do toho istého políčka, a teda musíme pri hľadaní prejsť všetky prvky množiny.
- Ak máme šťastie a v každom políčku máme len málo prvkov, bude aj vyhľadávanie rýchle.
- Ak je tabuľka dosť veľká a hašovacia funkcia vhodne zvolená, tento prípad je pomerne obvyklý.
- Hašovacie tabuľky sa často používajú v praxi.
- Viac budúci rok na predmete Algoritmy a dátové štruktúry.