Cormackovo hašování: Porovnání verzí
Smazaný obsah Přidaný obsah
Bez shrnutí editace |
Bez shrnutí editace |
||
Řádek 31:
'''r''' označje počet položek v primárním souboru, na které se odkazuje '''p''' <br>
'''pozice''' je index položky v adresáři.
===Příklad 1.===
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 1
| 1||2 ||3
|-
! 2
| || ||
|-
! ...
| || ||
|-
! j
| || ||
|-
! ...
| || ||
|}
</td><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Primární soubor
! pozice !! hodnota
|-
! 0
| 4
|-
! 1
| 5
|-
! 2
| 6
|-
! 3
|
|-
! 4
|
|-
! 5
|
|}
</tr>
</table>
Tato situace nám popisuje, že v primárním souboru jsou uloženy 3 položky, všechny v jednom bloku(vede na n2 jen jeden pointer '''p'''), které jdou od sebe rozlišit hašovací funkcí číslo 2 ('''r''' == 2) a první z těchto položek je v primárním souboru na pozici 1 ('''p''' == 1).
=== Jak funguje vkládání ===
Pokud přidáváme položku s klíčem '''k''', nejprve spočteme <math>h(k)</math>. Pokud je Adresář[<math>h(k)</math>].r == 0, provedeme následující akce
* Adresář[<math>h(k)</math>].r = 1
* Adresář[<math>h(k)</math>].i = <math>\heartsuit</math> (Pozor, ne 0)!
* V primárním souboru na první volnou pozici s adresou p<sub>new</sub> umístíme ukládanou položku
* Adresář[<math>h(k)</math>].p = p<sub>new</sub>
Pokud je Adresář[<math>h(k)</math>].r != 0, provedeme následující akce
* Adresář[<math>h(k)</math>].r = Adresář[<math>h(k)</math>].r +1
* Najdeme nejmenší i takové, že <math>h_{i}(k,r)</math> je růzdné pro nově vkládanou položku a pro všechny položky v datovém bloku příslušném pointeru Adresář[<math>h(k)</math>].p
* Adresář[<math>h(k)</math>].i = i
* V primárním souboru na první volnou a dostatečně velkou pozici s adresou p<sub>new</sub> umístíme ukládanou položku a všechny položky z bloku Adresář[<math>h(k)</math>].p v pořadí, které určí klíč sekundární hašovací funce
<math>h_{i}(k, r)</math>
* Adresář[<math>h(k)</math>].p = p<sub>new</sub>
===Příklad 2.===
Zvolne velikost adresáře M=7.
Potom <math>h(k)</math> navrhneme ve tvaru <br>
<math>h(k)</math> <math>h(k)= k \quad mod \quad M</math>;<br>
<math>h_{i}(k, r) = (k << i) \quad mod \quad r </math>, pro r případ '''r''' jemocninou 2; <br>
<math>h_{i}(k, r) = (k \quad xor i) \quad mod \quad r </math>, jinak.<br>
(<math> << i</math> značí [[bitový posun]] vlevo o i bitů)
Postupně budeme přidávat do prázného souboru položky 6, 3, 13.
<math>h(6) = 6, h(3) = 3</math>, přidání je tedy triviální a struktury mají po přidání prvních dvou tento tvar.
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 0
| || ||
|-
! 1
| || ||
|-
! 2
| || ||
|-
! 3
| 1 ||<math>\heartsuit</math> || 1
|-
! 4
| || ||
|-
! 5
| || ||
|-
! 6
| 0 ||<math>\heartsuit</math> || 1
|}
</td><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Primární soubor
! pozice !! hodnota
|-
! 0
| 6
|-
! 1
| 3
|-
! 2
|
|-
! 3
|
|-
! 4
|
|-
! 5
|
|}
</tr>
</table>
Potom se pokusíme přidat 13. <math>h(13) = 6</math>, což už je obsazeno.
Updatneme Adresář[6].r na 2, a najdeme čím je to obsazeno (položkou s klíčem 6), a hledáme první sekundární funkci, která tyto klíče rozliší. To je <math>h_{0}</math>, protože <math>h_{0}(6,2) = 0</math>, a <math>h_{0}(13,2) = 1</math>.
Takže po vložení 13 budou struktuy vypadat následujícím způsobem
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresár
! pozice !! p !! i !! r
|-
! 0
| || ||
|-
! 1
| || ||
|-
! 2
| || ||
|-
! 3
| 1 ||<math>\heartsuit</math> || 1
|-
! 4
| || ||
|-
! 5
| || ||
|-
! 6
| 2 ||0 || 2
|}
</td><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Primární soubor
! pozice !! hodnota
|-
! 0
|
|-
! 1
| 3
|-
! 2
| 6
|-
! 3
| 13
|-
! 4
|
|-
! 5
|
|}
</tr>
</table>
=== Jak funguje vyhledávání ===
* spočteme <math>h(k)</math>.
* podle Adresář[<math>h(k)</math>].r se buď podíváme na přímo příslušné místo do primárního souboru, nebo spočteme příslušnou (Adresář[<math>h(k)</math>].i) sekundární hašovací funkci, najdeme příslušný blok a v něm příslušnou položku.
Další často používanou sekundární funkcí je funkce
<math>h_{i}(k,r)=(k \quad mod \quad (2i + 100r +1))\quad mod \quad r</math>
Predpokladá se, že <math> k << 2i + 100r +1</math>.
=== Pseudokód ===
Zadefinujeme si ješte nějaké datové položky:
<code>
typedef head_1 {int p; int i; int r;}
typedef body_1 {int k; int v;}
head_1 *head=new head_1[s];
body_1 *body=new body_1[];
</code>
==== Vyhledávání ====
<code>
int h(int k, int s) {}
int hi(int i, int k, int r) {}
bool find(int k, int *v) {
j=h(k, s);
if (head[j].r==0) return false;
else {
body *p=body[head[j].p+hi(head[j].i, k, head[j].r)];
if (p->k!=k) return false;
else {*v=p->v; return true;}
}
}
</code>
==== Vkládání ====
...je trošku zložitejšie, c-like algoritmus není kompletní, ale je názorný...
<code>
int free(int size) {/*nájde voľné miesto v primárnom súbore s veľkosťou size*/}
bool insert(body_1 d) {
j=h(d.k, s);
if (head[j].r==0) { //pre daný kľúč ešte nemáme alokovaný blok
int p=free(1);
body[p].k=d;
head[j].p=&body[p]; head[j].i=0; head[j].r=1;
} else {
Ak už je hodnota d.k v množine head[j].p - head[j].p+head[j].r, vráť false
Nájdi voľné miesto pre (head[j].r+1) prvkov
Nájdi i také, aby hashovacia funkcia hi vrátila pre každý z prvkov (pôvodný blok+d) rôznu adresu
Premiestni prvky zo starého umiestnenia na nové, zapíš nový prvok
Oprav adresár
}
}
</code>
| |||