Perfektní hašovaní (Cormack)

Z Wikipedie, otevřené encyklopedie

Tento článek z oblasti informatiky potřebuje úpravy. Můžete Wikipedii pomoci tím, že ho vhodně vylepšíte. Inspiraci k vylepšení lze hledat v radách na stránce Vzhled a styl, případně na diskusní stránce článku.

Cormakovo hašování je jednou z metod perfektního hašování. Dnes se používá například pro uspořádávání a vyhledávání položek na externích médiích v některých aplikacích (například slovníky,které nemají databázi slov na disku, ale na CD nosiči). Je založeno na existenci primární hašovací funkce $h (k)$ , a celé třídy sekundárních hašovacích funkcí $h i (k, r)$ . funkce $h (k)$ musí mít obor hodnot roven velikosti adresáře. Položky jsou ukládány do primárního souboru (pevné velikosti), způsobem, který bude popsán za pomoci adresáře (také pevné velikosti). Protože je i primární soubor i adresář pevné velikosti, řadí se Cormacovo hašování do tzv. statických metod hešování.

Primární soubor si jde představit jako pole pevné velikosti. Adresář vypadá následujícím způsobem:

Adresář
pozice	p	i	r
1
2
...
j
...

Význam položek
p je odkaz do primimárního souboru
i značí kolikátá hašovací funkce byla použita a
r označje počet položek v primárním souboru, na které se odkazuje p
pozice je index položky v adresáři.

Obsah

1 Příklad 1
2 Jak funguje vkládání
3 Příklad 2
4 Jak funguje vyhledávání
5 Pseudokód
- 5.1 Vyhledávání
- 5.2 Vkládání

[editovat] Příklad 1

Adresář
pozice	p	i	r
1	1	2	3
2
...
j
...

Primární soubor
pozice	hodnota
0	4
1	5
2	6
3
4
5
...

Tato situace nám popisuje, že v primárním souboru jsou uloženy 3 (r == 3) položky, všechny v jednom bloku(vede na ně jen jeden pointer p), které jdou od sebe rozlišit hašovací funkcí číslo 2 (i == 2) a první z těchto položek je v primárním souboru na pozici 1 (p == 1).

[editovat] Jak funguje vkládání

Pokud přidáváme položku s klíčem k, nejprve spočteme $h (k)$ . Pokud je Adresář[ $h (k)$ ].r == 0, provedeme následující akce

Adresář[ $h (k)$ ].r = 1
Adresář[ $h (k)$ ].i = $\heartsuit$ (Pozor, ne 0)!
V primárním souboru na první volnou pozici s adresou p_new umístíme ukládanou položku
Adresář[ $h (k)$ ].p = p_new

Pokud je Adresář[ $h (k)$ ].r != 0, provedeme následující akce

Adresář[ $h (k)$ ].r = Adresář[ $h (k)$ ].r +1
Najdeme nejmenší i takové, že $h i (k, r)$ 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ář[ $h (k)$ ].p
Adresář[ $h (k)$ ].i = i

V primárním souboru na první volnou a dostatečně velkou pozici s adresou p_new umístíme ukládanou položku a všechny položky z bloku Adresář[ $h (k)$ ].p v pořadí, které určí klíč sekundární hašovací funce

$h i (k, r)$

Adresář[ $h (k)$ ].p = p_new

[editovat] Příklad 2

Zvolne velikost adresáře M=7. Potom $h (k)$ navrhneme ve tvaru
$h(k)= k \quad mod \quad M$ ;
$h_{i}(k, r) = (k << i) \quad mod \quad r$ , pro r případ r jemocninou 2;
$h_{i}(k, r) = (k \quad xor \quad i) \quad mod \quad r$ , jinak.
( $< < i$ značí bitový posun vlevo o i bitů)

Postupně budeme přidávat do prázného souboru položky 6, 3, 13. $h (6) = 6, h (3) = 3$ , přidání je tedy triviální a struktury mají po přidání prvních dvou tento tvar.

Adresář
pozice	p	i	r
0
1
2
3	1	$\heartsuit$	1
4
5
6	0	$\heartsuit$	1

Primární soubor
pozice	hodnota
0	6
1	3
2
3
4
5
...

Potom se pokusíme přidat 13. $h (13) = 6$ , což už je obsazeno. Updatneme Adresář[6].r na 2, a najdeme čím je Primární soubor na pozici Adresář[6].p obsazen - (položkou s klíčem 6), a hledáme první sekundární funkci, která tyto klíče rozliší. To je $h 0$ , protože $h 0 (6,2) = 0$ , a $h 0 (13,2) = 1$ . Takže po vložení 13 budou struktuy vypadat následujícím způsobem

Adresár
pozice	p	i	r
0
1
2
3	1	$\heartsuit$	1
4
5
6	2	0	2

Primární soubor
pozice	hodnota
0
1	3
2	6
3	13
4
5
...

[editovat] Jak funguje vyhledávání

spočteme $h (k)$ .
podle Adresář[ $h (k)$ ].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ář[ $h (k)$ ].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 $h_{i}(k,r)=(k \quad mod \quad (2i + 100r +1))\quad mod \quad r$ Predpokladá se, že $k < < 2 i + 100 r + 1$ .

[editovat] Pseudokód

Zadefinujeme si ješte nějaké datové položky:

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[];

[editovat] Vyhledávání

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;}
    }
}

[editovat] Vkládání

Je trošku složitější, C-like algoritmus není kompletní, ale je názorný:

int free(int size) { /* najde volné místo v primárním souboru s velikostí size */ }

bool insert(body_1 d) {
    j=h(d.k, s);
    if (head[j].r==0) { // pro daný klíč ješ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 {
        // Jestli už je hodnota d.k v množine head[j].p - head[j].p+head[j].r, vrať false
        // Najdi volné místo pro (head[j].r+1) prvků
        // Najdi i takové, aby hashovací funkce hi vrátila pro každý z prvků (původní blok+d) různou adresu
        // Přemísti prvky ze starého umístění na nové, zapiš nový prvek
        // Oprav adresář
    }
}

Citováno z „http://cs.wikipedia.org../../../p/e/r/Perfektn%C3%AD_ha%C5%A1ovan%C3%AD_%28Cormack%29_20f2.html“

Kategorie: Datové struktury