Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Srůstající hašování

Nyní se podíváme na několik verzí metody, která se nazývá srůstající hašování. Budeme potřebovat jedinou položku pro práci s tabulkou a to ukazatel jednosměrného spojového seznamu. Na rozdíl od předchozích metod zde nejsou řetězce separované, v jednom řetězci mohou být prvky s různou hodnotou hašovací funkce. Když máme přidat prvek , tak ho zařadíme do řetězce, který se nachází na -tém řádku tabulky. Řetězce tedy v této metodě srůstají. Různé verze této metody se liší tím, kam přidáváme nový prvek a podle práce s pamětí. Dělí se na standardní srůstající hašování bez pomocné paměti a na hašování používající pomocnou paměť, kterému se říká jen srůstající hašování.

Nejdříve se budeme věnovat metodám standardního srůstajícího hašování (bez pomocné paměti):

- LISCH - late-insertion standard coalesced hashing - vkládá se za poslední prvek řetězce,
- EISCH - early-insertion standard coalesced hashing - vkládá se za první prvek řetězce.

Přirozená efektivní operace DELETE pro standardní srůstající hašování není známa. Na druhou stranu i primitivní algoritmy mají rozumnou očekávanou časovou složitost.

Další otázka zní, proč používat metodu EISCH, když programy pro metodu LISCH jsou jednodušší. Odpověď je na první pohled dost překvapující. Při úspěšném vyhledávání je metoda EISCH rychlejší než metoda LISCH. Je to proto, že je o něco pravděpodobnější, že se bude pracovat s novým prvkem. V neúspěšném případě jsou samozřejmě obě metody stejné, neboť řetězce jsou u obou stejně dlouhé.

Metody srůstajícího hašování (s pomocnou pamětí) mají použitou paměť rozdělenou na dvě části. Na tu přímo adresovatelnou hašovací funkcí a na pomocnou část. Adresovací část má řádků, pokud hašovací funkce má hodnoty z oboru , v pomocné části jsou řádky ke kterým nemáme přístup přes hašovací funkci. Když při přidávání nového prvku vznikne kolize, tak se nejprve vybere volný řádek z pomocné části a teprve když je pomocné část zaplněna použijí se k ukládání kolidujících prvků řádky z adresovatelné části tabulky. Tato strategie oddaluje srůstání řetězců. Srůstající hašování se tedy, aspoň dokud není zaplněna pomocná část tabulky, podobá hašování se separovanými řetězci. Existují základní tři varianty:

- LICH - late-insertion coalesced hashing - vkládá prvek na konec řetězce,
- VICH - early-insertion coalesced hashing - vkládá prvek na řádek pokud je prázdný a nebo hned za prvek na řádku ,
- EICH - varied-insertion coalesced hashing - vkládá se za poslední prvek řetězce, který je ještě v pomocné části. Pokud v pomocné části žádný není, vkládá se hned za prvek na pozici .

Tyto metody nepodporují přirozené efektivní algoritmy pro operaci DELETE.