Přeskočit na obsah

Cormackovo hašování

Z Wikipedie, otevřené encyklopedie

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 , a celé třídy sekundárních hašovacích funkcí . Funkce 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

[editovat | editovat zdroj]
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í

[editovat | editovat zdroj]

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

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

Pokud je Adresář[].r != 0, provedeme následující akce

  • Adresář[].r = Adresář[].r +1
  • Najdeme nejmenší i takové, že 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ář[].p
  • Adresář[].i = i
  • V primárním souboru na první volnou a dostatečně velkou pozici s adresou pnew umístíme ukládanou položku a všechny položky z bloku Adresář[].p v pořadí, které určí klíč sekundární hašovací funkce
  • Adresář[].p = pnew

Příklad 2

[editovat | editovat zdroj]

Zvolme velikost adresáře M=7. Potom navrhneme ve tvaru
;
, pro případ r je mocninou 2;
, jinak.
( značí bitový posun vlevo o i bitů)

Postupně budeme přidávat do prázdného souboru položky 6, 3, 13. , 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 1
4
5
6 0 1
Primární soubor
pozice hodnota
0 6
1 3
2
3
4
5
...

Potom se pokusíme přidat 13. , 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 , protože , a . 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 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í

[editovat | editovat zdroj]
  • spočteme .
  • podle Adresář[].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ář[].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 Předpokládá se, že .

Pseudokód

[editovat | editovat zdroj]

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

typedef struct {int p; int i; int r;} head_1;
typedef struct {int k; int v;} body_1;

head_1 *head = new head_1[s];
body_1 *body = new body_1[];

Vyhledávání

[editovat | editovat zdroj]
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_1 *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í

[editovat | editovat zdroj]

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ář
    }
}