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í se dvěma ukazateli

Hašování s přemísťováním má tu nevýhodu, že díky přemisťování prvků jsou operace INSERT a DELETE časově náročné. Tato metoda tedy implementuje řetězce jako jednosměrné seznamy, ale takové které nemusejí začínat na svém místě, tj. řetězec obsahující prvky takové, že , nemusí začínat na -tém řádku. Místo ukazatele na předchozí prvek tak do položek pro práci s tabulkou přidáme ukazatel na místo, kde začíná řetězec příslušný danému řádku. Položky pro práci s tabulkou tedy budou: next - číslo řádku tabulky kde je další prvek seznamu, begin - číslo řádku tabulky obsahující první prvek seznamu příslušného tomuto místu.

Algoritmus (Hašování se dvěma ukazateli)

Položka begin v -tém řádku je vyplněna právě tehdy, když reprezentovaná množina obsahuje prvek takový, že . Algoritmy jsou potom podobné těm u hašování s přemísťováním, ale přemísťování prvků je nahrazeno odpovídajícími změnami v položce begin daných řádků.

Díky práci s položkami jsou operace INSERT a DELETE rychlejší než při hašování s přemísťováním, ale začátek řetězce v jiném řádku tabulky přidá navíc jeden test, což změní složitost operace MEMBER.

Subsections

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