hashovací struktura se nevejde do hlavní paměti (RAM), efektivnost se počítá podle počtu přístupů k blokům v externí paměti (HDD)
=== Statické hashovací metody ===
* hashovací fce mapuje klíče do fixního počtu adres/stránek
* umožňují přidávat klíče ale neumožňují rozšiřovat adresní prostor bez přehashování celého indexu
* vhodné pro statické databáze
==== Cormack (perfektní hashování) ====
[[Soubor:Cornack.PNG|thumb|Pre pristup najprv vypocitame riadok s adresata funkciou ''h''(''k'') = ''j'' . Adresa v hlavnom subore bude potom ''j.p'' + ''h''ⱼᵢ (''k'', ''j.r'')|344x344px]]
V vyzdvyhnutiu lubovolneho zaznamu su potrebne najviac dva pristupy na disk. Ak je adresar ulozeny v pamati tak potom jeden.
'''Potrebujeme''':
* '''Hlavnu hashovaciu funkciu ''h''(''k'')''' ktora vracia [0...''n''] Pre pristup k riadku adresara
* '''Pomocnu hashovaciu funkcia ''h''ᵢ(''k'', ''r'')''' vracia hodnotu s ⟨0, ''r'' - 1⟩ napr ''h''ᵢ(''k'', ''r'') = (''k'' mod (2''i'' + 100''r'' + 1)) mod ''r''
* '''Adresar '''( Velkost '''O(''n'')''' kde ''n'' je velkost suboru ) ktory obsahuje parametre druhej hashovacej funkcie ( ''p'' : index do primarneho adresara, ''i'' index hashovacej funcie , ''r'' pocet miest na kolko hashovacia funcia ''h''ᵢ prvky hashuje)
* '''Primarny subor''' obsahuje data a je ulozeny na disku.
'''FIND''': Pre pristup najprv vypocitame riadok s adresata funkciou ''h''(''k'') = ''j'' . Adresa v hlavnom subore bude potom j.p + ''h''ⱼᵢ ( ''k'', ''j.r'' )
'''INSERT''': Vsetky hodnoty adresara su na zaciatku 0.
* Zistime riadok adresara
** Ak je prvy najdeme pre neho volne miesto , ulozime ho a zauktualizujeme adresar
** Ak nieje prvy zobereme kolidujuce zaznamy a pozrieme ci nemame koliziu. Ak nie najdeme novu funciu ktora bude mat obor hodnot tak aby sme zaheshovali ''n'' + 1 prvkov , najdeme volne miesto a zaktualizujeme adresar.
{{collapse|Příklad|
<pre>
Vysvetlivky:
p ... pointer do primarniho souboru
i ... index pouzite hashovaci funkce
r ... pocet kolidujicich prvku/rozsah pro hi (velikost bloku v prim.
souboru, jehoz zacatek dostanu pomoci has. fce h)
Hashovaci funkce:
h(k) = k mod 7
hi(k,r) = (k >> i) % r
Vkladane prvky:
8, 9, 23, 5, 12, 22, 2
i(8):
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ 8 │
1 │ 0 │ 0 │ 1 │ └────┘
2 │ │ │ │ \
3 │ │ │ │ primarni soubor
4 │ │ │ │
5 │ │ │ │
6 │ │ │ │ - adresar
└────┴───┴───┘
--------------------------------------------------------------------------
i(9):
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ 8 │
1 │ 0 │ 0 │ 1 │ 1 │ 9 │
2 │ 1 │ 0 │ 1 │ └────┘
3 │ │ │ │
4 │ │ │ │
5 │ │ │ │
6 │ │ │ │
└────┴───┴───┘
--------------------------------------------------------------------------
i(23):
23 % 7 = 2, dochazi ke kolizi. Najdeme nove misto v prim. souboru,
kam se vejdou oba kolidujici prvky (souvisly blok velikosti 2).
Prvni takovy existuje na pozici 2.
Zkusime pouzit fci h0:
23 % 2 = 1, ale take 9 % 2 = 1.
Musime tedy zvolit jinou hasovaci funkci.
Pouzijeme h1, vypocitame nove pozice prvku 9 a 23 v ramci bloku
velikosti 2.
(23 >> 1) % 2 = 11 % 2 = 1
(9 >> 1) % 2 = 4 % 2 = 0
Vysly ruzne hodnoty, tedy lze h1 pouzit.
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ 8 │
1 │ 0 │ 0 │ 1 │ 1 │ │
2 │ 2 │ 1 │ 2 │ 2 │ 9 │
3 │ │ │ │ 3 │ 23 │
4 │ │ │ │ └────┘
5 │ │ │ │
6 │ │ │ │
└────┴───┴───┘
--------------------------------------------------------------------------
i(5):
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ 8 │
1 │ 0 │ 0 │ 1 │ 1 │ 5 │
2 │ 2 │ 1 │ 2 │ 2 │ 9 │
3 │ │ │ │ 3 │ 23 │
4 │ │ │ │ └────┘
5 │ 1 │ 0 │ 1 │
6 │ │ │ │
└────┴───┴───┘
--------------------------------------------------------------------------
i(12):
Kolize s cislem 5. Zkusime pouzit hasovaci fci h0.
5 % 2 = 1
12 % 2 = 0
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ 8 │
1 │ 0 │ 0 │ 1 │ 1 │ │
2 │ 2 │ 1 │ 2 │ 2 │ 9 │
3 │ │ │ │ 3 │ 23 │
4 │ │ │ │ 4 │ 12 │
5 │ 4 │ 0 │ 2 │ 5 │ 5 │
6 │ │ │ │ └────┘
└────┴───┴───┘
--------------------------------------------------------------------------
i(22):
Kolize s 8. Fci h0 nelze pouzit k rozliseni, zkusime h1.
(8 >> 1) % 2 = 0
(22 >> 1) % 2 = 1
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ │
1 │ 6 │ 1 │ 2 │ 1 │ │
2 │ 2 │ 1 │ 2 │ 2 │ 9 │
3 │ │ │ │ 3 │ 23 │
4 │ │ │ │ 4 │ 12 │
5 │ 4 │ 0 │ 2 │ 5 │ 5 │
6 │ │ │ │ 6 │ 8 │
└────┴───┴───┘ 7 │ 22 │
└────┘
--------------------------------------------------------------------------
i(2):
Kolize s 9 a 23.
Fce h0 selze, protoze 23 % 3 = 2 % 3 = 2.
9 dec = 1001 bin
23 dec = 10111 bin
12 dec = 1100 bin
Zkusime h1:
(9 >> 1) % 3 = 4 % 3 =1
(23 >> 1) % 3 = 11 % 3 = 2
(2 >> 1) % 3 = 1
Zkusime h2:
(9 >> 2) % 3 = 2
(23 >> 2) % 3 = 2
(2 >> 2) % 3 = 0
Zkusime h3:
(9 >> 3) % 3 = 1
(23 >> 3) % 3 = 2
(2 >> 3) % 3 = 0
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ │ 8 │ 2 │
1 │ 6 │ 1 │ 2 │ 1 │ │ 9 │ 9 │
2 │ 8 │ 3 │ 3 │ 2 │ │ 10 │ 23 │
3 │ │ │ │ 3 │ │ └────┘
4 │ │ │ │ 4 │ 12 │
5 │ 4 │ 0 │ 2 │ 5 │ 5 │
6 │ │ │ │ 6 │ 8 │
└────┴───┴───┘ 7 │ 22 │
--------------------------------------------------------------------------
d(23):
Postupujeme podobne jako u vkladani. Potrebujeme najit souvisly blok
velikosti 2. Takovy je na zacatku, nemusime zvetsovat velikost
prim. souboru. Zmenime tedy p na 0. Snizime r a prozkousime has. fce.
Zkusime h0:
23 % 2 = 1
2 % 2 = 0
p i r
┌────┬───┬───┐ ┌────┐
0 │ │ │ │ 0 │ 2 │
1 │ 6 │ 1 │ 2 │ 1 │ 9 │
2 │ 0 │ 0 │ 2 │ 2 │ │
3 │ │ │ │ 3 │ │
4 │ │ │ │ 4 │ 12 │
5 │ 4 │ 0 │ 2 │ 5 │ 5 │
6 │ │ │ │ 6 │ 8 │
└────┴───┴───┘ 7 │ 22 │
└────┘
</pre>
}}
[[Soubor:Fagin.PNG|thumb|Faginovo hashovanie pre hlbku adresara 2|224x224px]]
=== Dynamické hashovací metody ===
* umožňuje dynamický nárůst adresního prostoru pomocí dynamické hashovací fce
* vhodné pro db s měnící se velikostí
==== Fagin (rozšiřitelné adresářové hashování, Koubkovo "externí hashování") ====
'''Potrebujeme'''
* '''Adresar '''( Obsahuje ukazovatele / nie nutne unikatne / na stranky dat v na disku ; hlavicku v ktorej je ulozena hlbka adresara 0 < ''d ''< ''r'') / aky pocet bitov sa bere s pseudokluca)
* '''Hashovaciu funkciu pre pseodukluc ''h''(''k'')'''. Pseodukluce maju vsetky rovnaku dlzku r
* '''Stranky na disku''' , stranka obsahuje lokalnu hlbku ''d`''. Ak ''d` ''< ''d'' tak na jednu stranku vedie viac ukazovatelov
'''FIND:'''
* Spocitame pseodukluc ''k` ''= ''h''(''k'')
* Vezmeme hlbku adresata (''d'') a precitame prvych ''d'' bitov s pseodokluca ( nazveme to ''p'')
* Zobereme ukazovatel, ktory je umieneny v ''p.v'' ( ''v'' je velkost kazdeho pointra v bytoch ) ⇒ vedie na hladanu stranku
'''INSERT: '''Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-funkce. Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář.
Predpokladejme, ze do stranky se vejdou 2 zaznamy<br>
h(k) = k mod 32 - hasovaci fce<br>
-Vzdy na klic pouzijeme h(k) a potom vezmeme horni bity z takto<br>
ziskaneho cisla.<br>
-Pocet bitu, ktere budeme brat mame v "ousku" adresare. Pritom vzdy uvazujeme<br>
vsech pet bitu z cisla, tj napr. 2 dec = 10 bin budeme uvazovat jako 00010<br>
Vkladane hodnoty:<br>
5, 20, 33, 28, 30, 8, 25<br>
i(5): // 5 dec = 00101<br>
"ousko" adresare - rika, kolik bitu ma adresar<br>
┌─┐/ "ousko" u stranky - rika, kolik (hornich) bitu rozlisuje<br>
│1└─┐ ┌─┐/ hodnoty<br>
0 │ │─────│1└─┐<br>
1 │ │─┐ │ 5 │<br>
└───┘ │ │ │<br>
│ └───┘<br>
└┌─┐<br>
│1└─┐<br>
│ │<br>
│ │<br>
└───┘<br>
i(20): // 20 dec = 10100<br>
┌─┐<br>
│1└─┐ ┌─┐<br>
0 │ │─────│1└─┐<br>
1 │ │─┐ │ 5│<br>
└───┘ │ │ │<br>
│ └───┘<br>
└┌─┐<br>
│1└─┐<br>
│ 20│<br>
│ │<br>
└───┘<br>
i(33): // 33 mod 32 = 1 = 00001<br>
┌─┐<br>
│1└─┐ ┌─┐<br>
0 │ │─────│1└─┐<br>
1 │ │─┐ │ 5│<br>
└───┘ │ │ 33│<br>
│ └───┘<br>
└┌─┐<br>
│1└─┐<br>
│ 20│<br>
│ │<br>
└───┘<br>
i(28): // 28 = 11100<br>
┌─┐<br>
│1└─┐ ┌─┐<br>
0 │ │─────│1└─┐<br>
1 │ │─┐ │ 5│<br>
└───┘ │ │ 33│<br>
│ └───┘<br>
└┌─┐<br>
│1└─┐<br>
│ 20││ 28│<br>
└───┘<br>
i(30): // 30 = 11110<br>
Chceme umistit hodnotu do stranky, ktera je plna. Zvetsime adresar, po zmene<br>
bude dvoubitovy. Strankam, ktere nepotrebujeme stepit jen zvetsime "rozsah",<br>
prvky ze stepenych stranek rozhazime podle hornich bitu do spravnych stranek.<br>
Take si do "ouska" stranek poznamename, ze rozlisujeme hodnoty podle dvou<br>
bitu.<br>
┌─┐ ┌─┐<br>
│2└─┐ │1└─┐<br>
00 │ │─┬───│ 5│<br>
01 │ │─┘ │ 33│<br>
10 │ │───┐ └───┘<br>
11 │ │─┐ └─────┌─┐<br>
└───┘ └┌─┐ │2└─┐<br>
│2└─┐ │ 20│<br>
│ 28│ │ │<br>
│ 30│ └───┘<br>
└───┘<br>
i(8): // 8 = 01000<br>
Vkladame do plne stranky, ta se ale da rozstepit, protoze rozlisuje<br>
hodnoty jen podle jednoho bitu.<br>
┌──────────┌─┐<br>
┌─┐ │ ┌─┐ │2└─┐<br>
│2└─┐│ │2└─┐ │ 5│<br>
00 │ │┘┌───│ 8│ │ 33│<br>
01 │ │─┘ │ │ └───┘<br>
10 │ │───┐ └───┘<br>
11 │ │─┐ └─────┌─┐<br>
└───┘ └┌─┐ │2└─┐<br>
│2└─┐ │ 20│<br>
│ 28│ │ │<br>
│ 30│ └───┘<br>
└───┘<br>
i(25): // 25 = 11001<br>
Vkladame do plne stranky, jeji "rozsah" nelze rozdelit (rozlisuje hodnoty<br>
podle dvou bitu) - musime zvetsit adresar a rozdelit prislusnou stranku a<br>
zmenit "rozsahy" jednotlivych stranek.<br>
┌─────────┌─┐<br>
┌─┐ │ ┌─┐ │2└─┐<br>
│3└─┐ │ │2└─┐ │ 8│<br>
000 │ │─┤┌──│ 5│ │ │<br>
001 │ │─┘│ │ 33│ └───┘<br>
010 │ │─┬┘ └───┘<br>
011 │ │─┘ ┌─┐<br>
100 │ │─┬────────────│2└─┐<br>
101 │ │─┘ ┌─┐ │ 20│<br>
110 │ │─────────│3└─┐│ │<br>
111 │ │──┌─┐ │ 25│└───┘<br>
└───┘ │3└─┐ │ │<br>
│ 28│ └───┘<br>
│ 30│<br>
└───┘
[[Soubor:Litwin.PNG|thumb|Schéma štěpení při lineárním hašování]]
==== Litwin (lineární bezadresářové hashování) ====
Nevyužívá adresář, ale '''potřebuje oblast přetečení''' a tedy není zaručeno, že se ke všem datům dostaneme v 1 přístupu na disk. Data uložena ve stránkách.
Stránky jsou štěpeny nezávisle na tom, kde došlo ke kolizi, kruhovým schématem (viz obrázek). Po každých L (L je parametr metody) vloženích je rozštěpena 1 stránka. Když dochází ke štěpení stránky, přidáme 1 stránku na konec '''úložiště stránek''' . Záznamy ze štěpené stránky (a případné z oblasti přetečení, které by patřily do štěpené stránky) jsou potom rozděleny mezi novou a štěpenou stránku.
'''FIND:''' ''h''(''k'') = ''k`'' (pseudoklíč má na rozdíl Fagina podle posledních bitů a jeho délku spočítá podle počtu všech stránek, pokud tam není hledáme v obl.přetečení)
'''INSERT:''' najdi místo pomocí FIND a pak vložíme, pokud se nevejde tak nacpeme do oblasti přetečení, po L INSERTech štěpíme a podle posledních bitů rozdělíme záznamy
Růst primárního souboru je lineární ⇒ lineární hashování
{{collapse|Příklad|
<pre>
Hasovaci fce - v nasem pripade pouze prevod z desitkove do dvojkove soustavy
Vysvetlivky:
b = 3 ...velikost bloku
l = 2 ...po kolika insertech se ma stepit stranka
Vkladane hodnoty:
12, 5, 4, 1, 3, 2, 7, 14
i(12):
┌────┐ Kdyz mame jedinou stranku (do 1. stepeni), vkladame do ni
│ 12 │ vsechny hodnoty (nezalezi na poslednim bitu).
│ │
│ │
└────┘
i(5):
┌────┐
│ 12 │
│ 5 │
│ │
└────┘ "oznaceni stranky" - posledni bit(y) cisel ve strance maji
├──────┐ / tuto hodnotu
│ 0 │ 1
┌────┐ ┌────┐ Protoze l=2 a vlozili jsme druhy prvek, dojde ke stepeni.
│ 12 │ │ 5 │ Podle posledniho bitu cisel se rozhodne, do
│ │ │ │ ktere pujdou stranky.
│ │ │ │
└────┘ └────┘
i(4):
0 1
┌────┐ ┌────┐
│ 12 │ │ 5 │
│ 4 │ │ │
│ │ │ │
└────┘ └────┘
i(1):
0 1
┌────┐ ┌────┐
│ 12 │ │ 5 │
│ 4 │ │ 1 │
│ │ │ │
└────┘ └────┘
├──────────────┐
│ 00 1 │10
┌────┐ ┌────┐ ┌────┐ Vlozili jsme 4. prvek - dochazi ke stepeni.
│ 12 │ │ 5 │ │ │ Hodnoty rozdelujeme podle poslednich dvou
│ 4 │ │ 1 │ │ │ bitu.
│ │ │ │ │ │
└────┘ └────┘ └────┘
i(3):
00 1 10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ │
│ 4 │ │ 1 │ │ │
│ │ │ 3 │ │ │
└────┘ └────┘ └────┘
i(2):
00 1 10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │
│ 4 │ │ 1 │ │ │
│ │ │ 3 │ │ │
└────┘ └────┘ └────┘
├──────────────┐
00 │ 01 10 │11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │ │ 3 │
│ 4 │ │ 1 │ │ │ │ │
│ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘
i(7):
00 01 10 11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │ │ 3 │
│ 4 │ │ 1 │ │ │ │ 7 │
│ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘
i(14):
00 01 10 11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │ 5 │ │ 2 │ │ 3 │
│ 4 │ │ 1 │ │ 14 │ │ 7 │
│ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘
├───────────────────────────┐
│000 01 10 11 │100
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ │ │ 5 │ │ 2 │ │ 3 │ │ 12 │
│ │ │ 1 │ │ 14 │ │ 7 │ │ 4 │
│ │ │ │ │ │ │ │ │ │
└────┘ └────┘ └────┘ └────┘ └────┘
</pre>
}}
{{zdroje|
https://is.cuni.cz/webapps/zzp/detail/46740/
}}
