Statické hashování - Static hashing

Statické hashování je další forma hashování problém, který umožňuje uživatelům provádět vyhledávání na dokončené sadě slovníků (všechny objekty ve slovníku jsou konečné a nemění se).

Používání ^[1]

aplikace

Protože statické hashování vyžaduje, aby databáze, jeho objekty a reference zůstávají stejné, jeho aplikace jsou omezené. Databáze, které obsahují informace, které se zřídka mění, jsou také způsobilé, protože by to jen výjimečně vyžadovalo úplné promíchání celé databáze. Mezi příklady patří sady slov a definice konkrétních jazyků, sady významných údajů pro zaměstnance organizace atd.

Perfektní hashování

Perfect hashing is a model of hashing in which any set of n elements can be stored in a hash tabulka stejné velikosti a může provádět vyhledávání v konstantním čase. Byl konkrétně objeven a diskutován Fredmanem, Komlosem a Szemeredim (1984), a proto byl přezdíván „FKS Hashing“.^[2]

FKS hashování

FKS Hashing využívá hashovací tabulku se dvěma úrovněmi, ve kterých nejvyšší úroveň obsahuje n kbelíků, z nichž každá obsahuje vlastní hashovací tabulku. FKS hashování vyžaduje, aby v případě kolize to musely dělat pouze na nejvyšší úrovni.

Implementace

Nejvyšší úroveň obsahuje náhodně vytvořenou hashovací funkci h (x), která zapadá do omezení Carterovy a Wegmanovy hashovací funkce - vidět v Univerzální hashování. Poté bude nejvyšší úroveň obsahovat n kbelíků označených k₁, k₂, k₃, ..., k_n. Podle tohoto vzoru všechny kbelíky obsahují hashovací tabulku velikosti s_i a příslušnou hashovací funkci, h_i(X). O hashovací funkci bude rozhodnuto nastavením s_i až k_i² a náhodně procházet funkcemi, dokud nedojde ke kolizím. To lze provést v konstantním čase.

Výkon

Protože tam jsou ${ displaystyle n vyberte 2}$ páry prvků, z nichž pravděpodobnost kolize je rovna 1 / n, hashování FKS může očekávat, že bude mít striktně méně než n / 2 kolizí. Na základě této skutečnosti a toho, že každé h (x) bylo vybráno tak, aby počet kolizí byl maximálně n / 2, nebude velikost každé tabulky na nižší úrovni větší než 2n.

Viz také

Reference

^ Daniel Roche (2013). SI486D: Náhodnost ve výpočetní technice, hashovací jednotka. United States Naval Academy, Computer Science Department.
^ Michael Fredman; János Komlós; Endre Szemerédi (1984). Ukládání řídkého stolu s O (1) nejhorším případem doby přístupu. Deník ACM (svazek 31, vydání 3).

[Roche2013-1] Daniel Roche (2013). SI486D: Náhodnost ve výpočetní technice, hashovací jednotka. United States Naval Academy, Computer Science Department.

[FKS1984-2] Michael Fredman; János Komlós; Endre Szemerédi (1984). Ukládání řídkého stolu s O (1) nejhorším případem doby přístupu. Deník ACM (svazek 31, vydání 3).

[1]

[2]