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ů

## Hašování

Definice (slovníkový problém)

Dáno univerzum , máme reprezentovat a navrhnout algoritmy pro operace

- MEMBER(x) - zjistí zda a pokud ano nalezne kde,
- INSERT(x) - pokud , vloží do struktury reprezentující ,
- DELETE(x) - když , smaže ze struktury reprezentující .

Například pomocí pole můžeme tyto operace implementovat rychle, ale nevýhodou je prostorová náročnost. Pro velké množiny je to někdy dokonce nemožné. Hašování se snaží zachovat rychlost operací a odstranit prostorovou náročnost.

Podívejme se nyní na základní ideu hašování. Mějme univerzum a množinu takovou, že . Dále mějme funkci . Množinu potom reprezentujeme tabulkou (polem) o velikosti tak, že prvek je uložen na řádku .

Definice (Hašovací funkce, kolize)

Funkci potom nazýváme hašovací funkcí. Situaci , pro nazveme kolize.

Jelikož mohutnost univerza je větší než velikost hašovací tabulky, nelze se kolizím úplně vyhnout. Existuje spousta různých metod, jak kolize řešit. Podívejme se tedy na některé podrobněji.

Definice

Ještě si zavedeme některé značení. Velikost (hašované množiny) označme n, velikost tabulky (pole) označme m, a faktor naplnění .

Subsections

- Hašování se separovanými řetězci
  - Očekávaný počet testů
- Hašování s uspořádanými řetězci
  - Očekávaný počet testů
- Hašování s přemísťováním
  - Očekávaný počet testů
- Hašování se dvěma ukazateli
  - Očekávaný počet testů
- Srůstající hašování
- Hašování s lineárním přidáváním
- Shrnutí
- Univerzální hašování
- Perfektní hašování
- Externí hašování