Cormackovo hašování

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

Tento článek není dostatečně ozdrojován a může tedy obsahovat informace, které je třeba ověřit.
Jste-li s popisovaným předmětem seznámeni, pomozte doložit uvedená tvrzení doplněním referencí na věrohodné zdroje.

Cormackovo hašování (nebo Cormackovo hashování nebo Cormackovo hešování) je jednou z metod dokonalé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 haš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 primárního souboru i značí kolikátá hašovací funkce byla použita a r označuje počet položek v primárním souboru, na které se odkazuje p pozice je index položky v adresáři.

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).

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ůzné 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í funkce $h_{i}(k, r)$
• Adresář[$h(k)$].p = p_new

Příklad 2

Zvolme 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 případ r je mocninou 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ázdné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. Zaktualizujeme 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 struktury vypadat následujícím způsobem:

Adresář 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 ...

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$ Předpokládá se, že $k << 2i + 100r +1$.

Pseudokód

Zadefinujeme si ještě 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[];

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

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ště 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 hašovací 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ář
    }
}