Cormackovo perfektní hašování

Tato hašovací metodu je vhodné použít, pokud dopředu dokážeme rámcově odhadnout, kolik dat potřebujeme uchovávat. Podle toho totiž bude třeba nadimenzovat datové struktury. Narozdíl třeba od Fagina, je tato metoda statická - s přibývajícím početm hodnot se zhoršují její vlastnosti, protože dochází k většímu počtu kolizí při hašování.

Obecný popis

Krom primárního souboru (rozděleného do stránek) máme k dispozici datovou strukturu s názvem adresář, která obsahuje dodatečné ifnromace, jenž nám pomohou rychle lokalizovat záznamy se zadaným klíčem. Celé schéma používá primární hašovací funkci HASH a sadu sekundárních haš. funkcí H_i, které mohou být na sobě závislé (tím myslím, že máme zadánu H_0, ze které jsme schopni odvodit H_1 atd. - tedy z H_i odvodíme předpis pro H_i+1).

Adresář se skládá z trojic (p, i, r). Každá taková trojice nám říká, že se na adrese p v primárním souboru za sebou nachází r záznamů, které jsou do prostoru velikosti r bezkolizně rozmístěny hašovací funkcí H_i. Trojice, které nejsou použity k indexování do primárního souboru poznáme podle nulové hodnoty r.

Primární hašovací funkce akceptuje pouze jediný parametr - klíč. Sekundární hašovací funkce akceptují dva parametry - jejich hodnoty můžeme zapisovat jako H_i(k, r, i). Jejich úkolem je bezkolizně rozhodit r záznamů se stejným HASH(k) do oblasti velikosti r. Parametr i označuje pořadové číslo hašovací funkce a může nabývat celočíselných hodnot v intervalu <0,n).

Vyhledávání

Pokud vyhledáváme záznam s určitím klíčem k, musíme nejprve zjistit, která položka adresáře na něj odkazuje. Index příslušné trojice získáme aplikací primární hašovací funkce HASH na klíč.

Přečtením příslušné trojice zjistíme, že hledaný záznam se může nacházet pouze v oblasti primárního souboru mezi adresami p a p + r - 1. Hodnota i nám řekne, jakou sekundární hašovací funkcí jsou záznamy v tomto bloku "rozhozeny" - tzn. jakou H_i použijeme na klíč, abychom získali adresu v primárním souboru, kde se hledaný záznam musí nacházet. Pokud se tam nenachází, není nikde jinde v primárním souboru.

Přidávání

Při přidávání nového záznamu musíme postupovat opatrně, abychom zachovali konzistenci mezi primárním souborem a adresářem. Algoritmus by se dal popsat následujícími kroky.

• Zjistíme skupinu r záznamů, do které bude nový prvek patřit. To se provede stejným způsobem, jakým dostaneme při vyhledávání idnex trojice v adresáři, tedy použijeme na klíč zázamu primární hašovací funkci.
• Najdeme v primárním souboru souvislý blok volného místa, který postačí pro uchování r + 1 záznamů. Ve standardní variantě Cormacka totiž r určuje počet záznamů, se stejnou hašovanou hodnotou klíče. Teoreticky by toto číslo bylo možné zvyšovat ne při každém vložení záznamu, ale "nárazově". Například při přidání prvního záznamu bychom nastavili r na hodnotu 10, čímž by v oblasti zůstalo dost volného místa, do kterého by bylo možné přidávat nové záznamy, aniž bychom museli měnit sekundární hašovací funkci, nebo hodnotu r (což znamená přemístění celé oblasti na jiné místo). Adresu námi nalezené volné oblasti si označíme q
• Použijeme i-tou sekundární hašovací funkci, která nám určí rozložení záznamů v nově alokované oblasti. Pokud pozice nějakých dvou záznamů kolidují, zkusíme použít hašovací funkci H_i+1. Takovýmto iterativním postupem nakonec najdeme j takové, že H_j bezkolizně rozhodí r+1 záznamů do stejně velkého volného prostoru.
• Překopírujeme r záznamů z původního místa do místa nového a přidáme k nim nový záznam. Rozložení nám zajistí sekundární hašovací funkce H_i. Všimněte si, že jsme dosud během přidávání neaktualizovali adresář. Činíme tak z důvodu zachování konzistence v případě, že by se celou operaci nepodařilo dokončit (například z důvodu výpadku proudu). Pokud by v tomto či libovolném předchozím kroku došlo k nějakému selhání, adresář zůstane konzistentní s primárním souborem a vše bude vypadat tak, jako by se nikdy žádné přidávání nekonalo.
• Modifikujeme trojici v adresáři na hodnoty (q, j, r+1).
• Označíme původní oblast s r záznamy jako volné místo.

Můžete namítnout, že konzistence není tak úplně zachována. A máte pravdu. Pokud během operace např. vypadne proud, může se stát, že primární soubor bude obsahovat oblast, na kterou z adresáře nevede žádný odkaz. Tento fakt není příliš velkým problémem, protože nám nebrání ve vyhledávání ani přidávání nových záznamů (nedojde-li nám volné místo na disku) a příslušnou oblast detekujeme velmi snadno, stačí porovnat obsah adresáře s seznamem volných oblastí v primárním souboru, který si udržujeme v další pomocné struktuře (např. ve spojovém seznamu). Mnohem větším problémem by byl adresář, jehož položky odkazují "do ničeho" - tedy do volného místa v primárním souboru.

Optimalizace

Zde popsaný postup je jenom základ, který je možné všelijak optimalizovat. Jak již bylo zmíněno při popisu operace přidávání, lepším volením velikosti r můžeme dosáhnout toho, že nebude nutné vyhledávat novou oblast a modifikovat adresář při každém přidávání nového záznamu. Podobně lze k tomuto schématu vymyslet i způsob, jak záznamy odebírat, u které bude hlavní dilema spočívat v tom, jak často se pokusíme zmenšovat hodnotu r.