Cormackovo hašování
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:
|
Význam položek |
Příklad 1
[editovat | editovat zdroj]
|
|
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.
|
|
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:
|
|
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ář
}
}