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ů

### Externí hašování

Externí hašování řeší trochu jiný problém, než výše popsané metody. Chceme uložit data na externí médium a protože přístup k externím médiím je o několik řádů pomalejší, než práce v interní paměti, bude naším cílem minimalizovat počet přístupů do ní. Externí paměť bývá rozdělena na stránky a ty většinou načítáme do interní paměti celé. Tato operace je však velice pomalá. Problémem externího hašování je tedy nalézt datovou strukturu pro uložení dat na vnější paměti a algoritmy pro operace INSERT, DELETE a MEMBER, tak abychom použili co nejmenší počet komunikací mezi vnější a vnitřní pamětí.

Metod externího hašování je opět mnoho. Některé používají pomocnou datovou strukturu v interní paměti, kterou často nazýváme adresář. Pokud metody nemají žádnou takovou pomocnou strukturu neobejdou se obvykle bez oblasti přetečení. Některé známější metody vnějšího hašování jsou například: Litwinovo lineární hašování, Faginovo rozšiřitelné hašování, Cormackovo perfektní hašování nebo Perfektní hašování Larsona a Kajli.