27c - Hashovacie tabuľky (tabuľky s rozptýlenými položkami)

Tabuľky s priamym prístupom

• množina kľúčov, ktoré budeme vyhľadávať
• množina adries, na ktorých ležia jednotlivé prvky
• existuje mapovacia funkcia = mechanizmus, ktorému predáme kľúč a on vráti adresu
• časová zložitosť 1
• problém je v nájdení vhodnej mapovacej funkcie (keby sme mali zoznam všetkých mapovacích funkcií, tak tam sú napr. funkcie, ktoré mapujú všetky hodnoty na jeden kľúč, alebo všetky hodnoty na všetky kľúče, atď)
• Mapovacia funkcia:
  • je dané mapovacie pole intervalom najčastejšie [0..n] resp. [1..N]
  • mapovacia funkcia transformuje kľúč na index, ktorého hodnota musí byť v danom intervale
  • najčastejšie 2 etapy:
    • prevod kľúča na prirodzené číslo
    • prevod prirodzeného čísla na hodnotu spadajúcu do intervalu (najčastejšie pomocou „modulo“)
  • jedno-jednoznačná mapovacia funkcia = vracia rozličné hodnoty pre rôzne kľúče pre každú hodnotu a kľúč
  • kolízia = dva rôzne kľúče sa namapujú na rovnaké miesto (funkcia je jednoznačná, ale nie je jedno-jednoznačná)
  • synonymá = tie kľúče, ktoré sa namapujú na rovnaké miesto
  • 2 požiadavky na mapovaciu funkciu:
    • rýchlosť
    • čo najmenej kolízií
  • maximálna doba vyhľadávania je daná dĺžkou najdlhšieho zoznamu synoným
• Explicitné a implicitné zreťazenie:
  • index sekvenčný prístup
  • hashovacia tabuľka pozostáva z mapovacieho priestoru (pole) a zo zoznamu synoným, každý zoznam synoným začína na jednom prvku mapovacieho poľa
  • explicitné zreťazenie = prvok obsahuje adresu následníka

• implicitné zreťazenie = adresa následníka je funkciou adresy predchodcu
  • krok je konštantný:
    • krok určuje programátor
    • krok určuje program (druhá rozptyľovacia funkcia)
  • krok je premenný (kvadratická metóda) - toto by nemal skúšať (podľa vlastných slov)

• implicitné zreťazenie synoným:

• každý prvok má nejakú zložku, ktorá určuje, či je voľný alebo obsadený
• koniec zoznamu synoným je daný prvým voľným prvkom, ktorý sa nájde so zadaným krokom
• nové synonymum sa uloží na prvé voľné miesto
• tabuľka musí obsahovať aspoň jeden voľný prvok (každá sekvencia potrebuje jeden voľný stav na konci - ten môže byť spoločný pre viaceré sekvencie)
• tabuľka je implementovaná kruhovým poľom
• sekvencie sa môžu prelínať
• rušenie položiek prakticky nie je možné (jedine zaslepenie)
• krok 1 je nevhodný (kvôli prelínaniu), krok musí byť nesúdeliteľný s veľkosťou poľa ⇒ prvočíslo

• dvojitá rozptyľovacia funkcia:
  • krok je určený programom
  • prvá rozptyľovacia funkcia vytvára hodnotu z intervalu 0..Max = kľúč % (Max+1)
  • druhá rozptyľovacia funkcia vytvára krok z intervalu 1..Max = kľúč % (Max+1)
  • vyhľadávanie: 1. rozptyl. funkciou sa dostaneme na index, ak je obsadený, tak získame z 2. rozptyl funkcie krok a posúvame sa (kruhovo) až kým nenájdeme daný prvok, alebo dosiahneme koniec zoznamu synoným (prázdny prvok)

• brentova varianta:
  • rekonfigurácia prvkov pri vkladaní aby sa priemerná doba hľadania kľúča znížila
  • oplatí sa keď je počet vkladaní menší ako počet vyhľadávaní