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
+Adresář pozice p i r 1 12 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 . 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 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ář.r na 2, a najdeme čím je Primární soubor na pozici Adresář.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í 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 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í 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í 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ář
Kategorie:Hašování