Cvičenie 11 – Hash

Ciele cvičení:

  • rozumieť priemernej a agregovanej zložitosti
  • rozumieť základným princípom hashovania
  • vedieť, ako možno hashovanie využiť pri ukladaní dát a následnej práci s nimi
  • vedieť, ako možno hashovanie využiť pri stringologickom Karp-Rabin-ovom algoritme

Budovanie HashSet-u

Pomocou poľa LinkedList-ov implementujte triedu, ktorá realizuje HashSet reťazcov s nemenným počtom priehradok. Poznámka: Použite hash-ovaciu funkciu z prednášky.

Pred implementáciu rozdiskutujte:

  • aké konštruktory je potrebné vytvoriť,
  • ako implementovať hash-ovaciu funkciu tak, aby sme nemali redundantný kód a vedeli ju neskôr jednoducho modifikovať.

Trieda nech obsahuje metódy:



1
2
3
4
5
6
7
public void add(String s);

public boolean contains(String s);

public int getCapacity(); // vrati velkost interneho pola

public int size(); // vrati pocet ulozenych retazcov

public double getLoadFactor();

public String toString();

public void printStructure(); // vypise strukturovany obsah
  • Zistite, či vaša implementácia naozaj reprezentuje množinu alebo vieme pridať rovnaký reťazec dvakrát.
  • Zmeňte použitú hash-ovaciu funkciu aby bola založená na lineárnej kongruencii s parametrom a. Upravte implementáciu aby sme parameter a vedeli zadať v konštruktore.
  • Rozdiskutujte vlastnosti hash-ovacej funkcie pre prípad, že veľkosť poľa je násobkom parametra a.
  • Pridajte metódu remove a upravte metódu add tak , aby Load Factor bol vždy medzi hodnotami 0,25 a 0,75. Poznámka: Táto implementácia nebude mať pevný počet priehradok.

Hľadanie výskytu intuitívne

Implementujte naivný algoritmus na nájdenie všetkých výskytov vzorky v reťazci. Využitie pritom schému:



1
2
3
4
5
6
7
8
9
10
11
public static void najdiVyskyty(String retazec, String vzorka) {

    int poz = 0;

    while (poz <= retazec.length() - vzorka.length()) {

        int i = 0;

        while (vzorka.charAt(i) == retazec.charAt(poz + i)) {

            //...

        }



        //...

    }

}
  • Je pravdou, že každý „zaujímavý“ okamih výpočtu možno charakterizovať obsahom premenných poz a i?

Algoritmus Karp-Rabin

  • Implementujte algoritmus Karp-Rabin z prednášky.
  • Rozdiskutujte zmeny v algoritme ak by sme uvažovali aj s použitím iných znakov ako malé a veľké písmena anglickej abecedy.
  • Rozdiskutujte pre aký najdlhší hľadaný reťazec s uvedeným hash-ovanim algoritmus funguje a prečo?

Pole s kapacitou a HashSet dôkazy

  • Dokážte, že amortizovaná zložitosť ľubovoľných n po sebe vykonaných operácii pridania a odobrania z koncu poľa s kapacitou bude O(n).
  • Dokážte, že amortizovaná zložitosť ľubovoľných n po sebe vykonaných operácii pridania a odobrania z vašej implementácie HashSet-u bude O(n).
  • Využite poznatky z predchádzajúcich dvoch bodov na návrh vylepšenej implementácie zásobníka a radu z tretieho cvičenia a popíšte zložitosť operácii (vkladania a vyberania) v rôznych prípadoch.
    • Toto riešenie sa vám môže zísť na štátniciach.