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 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:

1
2
.
j
. +more

| valign="top" | 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

1	1	2	3
2
.
j
. +more

| [wiki_table=9f8eef82] |}.

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)]. +morei = \heartsuit (Pozor, ne 0). * V primárním souboru na první volnou pozici s adresou pnew umístíme ukládanou položku * Adresář[h(k)]. p = pnew Pokud je Adresář[h(k)]. r . = 0, provedeme následující akce.

* Adresář[h(k)]. r = Adresář[h(k)]. +morer +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 pnew 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)]. +morep = pnew.

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 , pro případ r je mocninou 2;

h_{i}(k, r) = (k \quad xor \quad i) \quad mod \quad r , jinak.

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

0
1
2
3	1	\heartsuit	1
4
5
6	0	\heartsuit	1

| [wiki_table=8a4eab3c] |}

Potom se pokusíme přidat 13. h(13) = 6, což už je obsazeno. +more 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:.

0
1
2
3	1	\heartsuit	1
4
5
6	2	0	2

| [wiki_table=4beb7b74] |}

Jak funguje vyhledávání

spočteme h(k). * podle Adresář[h(k)]. +morer 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 .

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]. +morep + 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]. +morer==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í