Slovníky, hashovací tabulky
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Slovník – ADT
•Kolekce dvojice klíč-prvek
•Operace se slovníkem
•findElement(k) insertItem(k, o) removeElement(k)
•size() isEmpty()
•keys() elements()
•Aplikace
•Adresář, autorizace kreditních karet, slovník, překlad doménového jména na IP adresu

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Log File
•Log file – slovník implementovaný jako neuspořádaná sekvence
•Ukládáme objekty jako sekvence (obousměrný spojový seznam) v libovolném pořadí
•insertItem() O(1)
•findElement(), removeElement() O(n)
•
•Log file je výhodný pro malé slovníky, nebo aplikace, kde je vkládání nejčastější operací, kdežto
vyhledávání a odebírání se provádí zřídka

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Binární vyhledávání
•Operace findElement() na slovníku implementovaném pomocí sekvence založené na poli uspořádané
podle klíčů
•V každém kroku je číslo kandidáta dělené dvěma
•Končí po logaritmickém počtu kroků
•
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
0
0
0
0
m
l
h
m
l
h
m
l
h
l=m =h

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Vyhledávací tabulka
•Slovník implementovaný pomocí uspořádané sekvence
•Uchováváme položky slovníku v sekvenci založen=é na poli uspořádané podle klíčů
•Nutný externí comparator pro klíče
•findElement() O(logn)
•insertItem(k, o), removeElement O(n)
•
•Efektivní pro malé slovníky, nebo aplikace, kde nejčastější operací je vyhledávání.

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Binární vyhledávací strom

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Hashovací tabulka
•Hash funkce h
•Přiřazuje klíči daného typu celočíselnou hodnotu z intervalu [0, N-1]
•Př.: h(x)=x mod N
•h(x) – hodnota hashe
•Cílem je uniformě rozložit klíče v daném intervalu
•Hashovací tabulka pro daný typ klíče obsahuje
•Hashovací funkci
•Pole (tabulku) o velikosti N
•Klíč se nahradí hash hodnotou
•Kolize – dva klíče mají stejnou hash hodnotu
•Řešení: zřetězení, otevřené adresování
•