TIN066 Základní metody hashování

Wiki-skripta pro Datové struktury I
Obsah
Základní metody hashování Univerzální a perfektní hashování (a,b) stromy Binární vyhledávací stromy AVL stromy Červeno-černé stromy Splay stromy Vyhledávání v setříděné posloupnosti Vyhledávání k-tého nejmenšího Základní haldy Binomické a Fibonacciho haldy Základní metody třídění Přihrádkové třídění

Tato část je neúplná a potřebuje rozšířit. Lepe zpracovano na: Státnice - Hašování

Slovníkový problém

Mějme universum prvků U a jeho podmnožinu S. Tu chceme reprezentovat a umět na ní provádět operace MEMBER, INSERT a DELETE. Nechci mít v paměti prostor pro celé U, proto si zavedu hashovací funkci $ h\colon U \to \{0..m-1\} $, pak prvky ukládám do pole délky m na index podle $ h(x) $.

• Problémem jsou kolize: $ x, y \in S: x \ne y,\ h(x) = h(y) $.
• Ještě nás bude zajímat load factor $ \alpha = |S|/m $.

Hashování se separovanými řetězci

Tato část je neúplná a potřebuje rozšířit. Důkazy složitostí (ale bez zamlžení toho, co už tu je; možná lemmata a detaily na zvláštní stránce?)

Každá položka hashe vede na spoják s kolidujícími prvky (řetězce jsou prosté, nic v nich není dvakrát). V nejhorším případě budu mít jediný spoják se vším.

Paměti žere každá položka $ O(1+l(i)) $ (l(i) je délka spojáku), očekávané délky spojáků se za předpokladu $ {|U|\over m}\gg n^2 $ (předpoklad tohoto typu je nezbytný, fanoušsci pravděpodobnostní metody si za ním mohou představit narozeninový paradox) řídí binomickým pravděpodobnostním rozdělením (s parametrem 1/m). Z toho vypadne, že:

• $ \mathbb{E}\ l = \alpha $
• $ \hbox{var}\ l = n{1 \over m}\left(1 - {1 \over m}\right) $

Zběsilými a děsivými sumacemi na tři stránky se dobereme k očekávané délce nejdelší položky $ O({\log n \over \log \log n}) $ za předpokladu, že $ \alpha \le 1 $.

Tato část je neúplná a potřebuje rozšířit. Vysvětlit tu souvislost s narozeninovým paradoxem pořádně, nejlépe obecně jako samplování s opakováním vs. bez opakování; jednou větou jde v podstatě jen o to, že náhodné zobrazení z $ n \to m $ je pro $ n \ll \sqrt m $ skoro jistě prosté, a proto vybíráme-li bez opakování (neboli prostě), dopadne to skoro jistě stejně, jako když za předpokladu $ n \ll \sqrt m $ vybíráme s opakovaním (což se mnohem lépe analyzuje, neboť se tím odstraní závislosti).

Neuspořádané řetězce

Dobře, jak dlouho bude trvat něco najít? Očekávaný počet testů při neúspěšném hledání bude: $ (1 - 1/m)^n + n/m $ tzn. cca $ e^{-\alpha} + \alpha $ (pravděpodobnost prázdného řetězce plus pro každou délku ta délka krát pravděpodobnost, že to bude ona).

Očekávaný počet testů při úspěšném vyhledání $ 1 + \alpha/2 $. To je vidět celkem intuitivně, dokázat to formálně je trošku pracnější, ale už jsme tu přeskočili i horší věci. ;-)

Uspořádané řetězce

Očekávaný počet testů při úspěšném vyhledávání je stejný jako neuspořádaných řetězců. Při neúspěšném vyhledávání to můžeme utnout dříve, konkr. se lze dopracovat k počtu testů $ e^{-\alpha} + 1 + \alpha/2 - (1 - e^{-\alpha})/\alpha $.

S přemísťováním

Jde o hešování se separovanými řetězci, kde pro řetězce nevytváříme spojové seznamy s uzly někde na haldě, ale přidáváme tyto uzly do volných řádků naší tabulky (hrozí zde proto přeplnění). Uzly řetězců jsou v jednom úseku paměti - může být vstřícnější ke cache oproti separovaným řetězcům.

Stále zde existují řetězce. Řetězec s X vždy začíná na místě, kam se nahešovalo X. V případě, že do položky budu chtít uložit něco, co tam vážně patří, přendám prvek jinam. Očekávané hodnoty všeho budou stejné jako u separovaných řetězců, ale INSERT/DELETE budou samozřejmě náročnější.

Sloupce: (key, next, previous)

MEMBER x : i = h(x)

• if(i.previous != null || i.key == null) return false; - je zde cizí řetězec nebo prázdný řádek
• while (i.next!=null && i.key != x) i = i.next; - doskáčeme v řetězci na x nebo na konec
• return i.key==x;

INSERT x : i = h(x)

• pokud (i.key prázdný) vložím zde, konec;
• pokud (i.previous prázdný) je zde začátek správného řetězce. Doskáču na konec řetězce, vložím na nový řádek a napojím k řetězci
• pokud (i.previous neprázdný) je zde meziuzel cizího řetězce. Překopíruju položku i na jiný prázdný řádek (a přepojím pointery předchůdce/následníka), na i začnu nový řetězec.

DELETE x : i = h(x)

• nejdříve doskáču na správné i (jako v MEMBER(x))
• vymažu položku, "spoják style" (přepojení pointerů, rozlišení zda jsem první / vnitřní / koncový prvek spojáku ...)

Poznámky: na pointery next - previous stačí jen pár bitů (indexy jsou jen v rámci tabulky). V INSERT(x) je potřeba umět elegantně najít volný řádek / zahlásit přeplnění.

S dvěma ukazateli

Hashování s přemísťováním, ale řetězec (spoják) je pouze jednosměrný, ukazatel na předchozí prvek nahradíme ukazatelem begin na začátek řetězce. Řetězec obsahující X nemusí začínat na řádku h(x), ale začíná na h(x).begin (rovněž hodnota h(x).key nemusí patřit do řetězce obsahujícího X). Odpadá nutnost přemísťování (jen se mění begin), zase je maličko větší očekávaný počet testů.

Sloupce: (key, next, begin).

INSERT x : i = h(x)

• pokud (i.begin prázdné)
  • pokud (i.key prázdné) vložíme položku na i
  • jinak vezmeme prázdný řádek j, j.key = x, i.begin = j;
• pokud (i.begin neprázdné) doskáčeme na konec řetězce, vložíme x na nový řádek a napojíme za konec řetězce

Srůstající (coalesced) hashování

Sloupce: (key, next)

Máme jen jeden pomocný ukazatel next, prvek pak prostě přidáme do řetězce, který zrovna prochází jeho položkou; v řetězci se tak časem mohou ocitnout prvky s různými hashi. Neumíme efektivně mazat. Srůstající řetězce jsou jakýmsi protikladem separovaných řetězců.

Tato část je neúplná a potřebuje rozšířit. Počty testů

Bez pomocné paměti (standardní)

LISCH (late) přidá prvek na konec řetězce, EISCH (early) přidá prvek do řetězce za prvek na kolidující položce (volnou položku pro přidávaný prvek seženu jedno jak). EISCH je trochu rychlejší (neformálně - pravděpodobnost práce s nově přidaným prvek je vyšší).

S pomocnou pamětí

Přidáme oblast přetečení, což bude přímo neadresovatelný seznam, kam házíme kolidující nové prvky - až když je oblast plná, začneme je vkládat přímo na volná místa tabulky. (Tedy ukazatel next může procházet klidně skrz oblast přetečení.) EICH, LICH fungují stejně, VICH (varied) vloží nový prvek za poslední, který je ještě v pomocné části, nebo jako EICH (pokud řetězec přes pomocnou část nevede).

S lineárním přidáváním

Sloupce: (key)

Bez pomocných položek pro práci s tabulkou, prostě nový prvek přidám na nejbližší následující volné místo (předpokládám cyklickou paměť). Hodně triviální implementace, ale složité a pomalé DELETE. Nevhodné pro netriviální $ \alpha $, začnou se vytvářet shluky.

Očekávaný počet testů:

• Neúspěšný případ: $ {1 \over 2}\left(1 + \left({1 \over 1 - \alpha}\right)^2\right) $
• Úspěšný případ: $ {1 \over 2}\left(1 + {1 \over 1 - \alpha}\right) $

Dvojité hashování

Jako lineární přidávání, další volnou pozici ale hledám chytřeji než lineárně - zavedu si druhou hashovací funkci, pak postupně pro rostoucí i testuji $ (h_1(x) + ih_2(x)) \mod m $. Samozřejmě je vhodné, aby $ h_2(x) \not| m $. DELETE je zase otrava. Když druhý hash zvolíme chytře, bude fungovat o dost lépe než lineární.

Lineární přidávání je specifický případ dvojitého hešování, kde $ h_2(x) $ je konstantní jednička.

Lineární funguje dobře pro tabulku zaplněnou do 70%, dvojité až do 90%.

Tato část je neúplná a potřebuje rozšířit. Odhady testů

Externí hashování

Chceme minimalizovat počet přístupů do stránkované externí paměti. V OZD se následující učilo pod jménem "Faginovo hashování".

Data rozhazujeme do stránek, každá stránka má atribut i - prvních i bitů hashe všech položek ve stránce je stejných. Dále si držíme adresář - mapování hashů na stránky, ve kterém indexujeme pomocí prvních j bitů hashe ($ i \le j $); několik položek adresáře může ukazovat na tu samou stránku (pak $ i < j $). Pokud se stránka naplní, zvýšíme i a stránku rozštěpíme, pokud tím porušíme invariant, zvýšíme i j.

Adresář by se měl vejít do jedné stránky (nebo ho prostě držíme v paměti), potom MEMBER jsou max. 3 externí operace (nalezení 2 operace, třetí příp. update a zápis zpět na disk), INSERT/DELETE max. 6 operací (lookup 2 operace, pak buď uložení jako třetí, nebo např. pro INSERT rozštěpení: 3.,4. zápis dvou nových stránek, 5. znovunačtení adresáře (proč si jej nedržíme v paměti?), 6. uložení nového adresáře).

Nechť b je počet prvků na stránku a n počet všech prvků:

• Očekávaný počet použitých stránek bude $ n \over b\ln 2 $; tedy je zaplněno zhruba 69% možných položek v paměti.
• Očekávaná velikost adresáře bude $ {e \over b\ln 2}n^{1+1/b} $; tedy superlineární! Mez použitelnosti (nárůst adresáře kolem 5%) pro $ b=100 $ je zhruba $ n=10^{10} $, pro větší n je potřeba i větší b.