Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze Následující verze Obě strany příští revize | ||
mgr-szz:in-pos:3-pos [2019/06/08 18:41] lachmanfrantisek dotazy, transakce, zabezpečení |
mgr-szz:in-pos:3-pos [2019/06/13 20:29] lachmanfrantisek indexy, hašování |
||
---|---|---|---|
Řádek 77: | Řádek 77: | ||
- | === Kompresní kódování dat === | ||
- | |||
- | Cílem: | ||
- | |||
- | * minimalizace stupně kódu | ||
- | * při schopnosti on-line dekódování slov bez vkládání separátorů | ||
- | |||
- | <box 90% red|Kraftova nerovnost> | ||
- | Prefixový q-ární kód s délkami kódových slov d1,d2,...,dm existuje právě tehdy, když je splněna Kraftova nerovnost: | ||
- | |||
- | <m>sum{i=1}{m}{q^{{-d}_{i}}} <= 1</m> | ||
- | |||
- | </box> | ||
- | |||
- | <box 90% red|McMillanova veta> | ||
- | Kraftova nerovnost platí pro libovolné jednoznačně dekódovatelné kódování. | ||
- | </box> | ||
== Eliasovy kódy == | == Eliasovy kódy == | ||
- | <box 90% blue|Eliasův kód> | + | <box 90% blue|Eliasův kód C1> |
Kódování celých čísel u kterých není předem známá horní hranice. | Kódování celých čísel u kterých není předem známá horní hranice. | ||
Řádek 104: | Řádek 87: | ||
- Zapíšeme číslo dvojkově. | - Zapíšeme číslo dvojkově. | ||
- Odečteme 1 od počtu bitů zapsaných v kroku 1 a na začátek připojíme takový počet nul. | - Odečteme 1 od počtu bitů zapsaných v kroku 1 a na začátek připojíme takový počet nul. | ||
- | + | - Prefix 0 při dekódování určuje délku binární reprezentace. | |
- | </box> | + | |
- | + | ||
- | <box 90% blue|Eliasův kód C1> | + | |
- | + | ||
- | Prefix 0 určuje délku binární reprezentace. | + | |
Př.: | Př.: | ||
Řádek 126: | Řádek 104: | ||
Př.: | Př.: | ||
- | * <m>C_2(5)</m> = 0<color red>0</color>0<color red>1</color>1 | + | * <m>C_2(5)</m> = <color red>0</color>0<color red>0</color>1<color red>1</color> |
</box> | </box> | ||
Řádek 144: | Řádek 122: | ||
* <m>C_3(50)</m> = <color red>01001</color>10010 | * <m>C_3(50)</m> = <color red>01001</color>10010 | ||
</box> | </box> | ||
+ | |||
+ | === Kompresní kódování dat === | ||
+ | |||
+ | Cílem: | ||
+ | |||
+ | * minimalizace stupně kódu | ||
+ | * při schopnosti on-line dekódování slov bez vkládání separátorů | ||
+ | |||
+ | <box 90% red|Kraftova nerovnost> | ||
+ | Prefixový q-ární kód s délkami kódových slov d1,d2,...,dm existuje právě tehdy, když je splněna Kraftova nerovnost: | ||
+ | |||
+ | <m>sum{i=1}{m}{q^{{-d}_{i}}} <= 1</m> | ||
+ | |||
+ | </box> | ||
+ | |||
+ | <box 90% red|McMillanova veta> | ||
+ | Kraftova nerovnost platí pro libovolné jednoznačně dekódovatelné kódování. | ||
+ | </box> | ||
+ | |||
== Komprese == | == Komprese == | ||
Řádek 210: | Řádek 207: | ||
* **Slovníkové metody**: Vytváří se slovník dříve přečtených řetězců výstupem jsou indexy do slovníku. | * **Slovníkové metody**: Vytváří se slovník dříve přečtených řetězců výstupem jsou indexy do slovníku. | ||
- | <box 90% blue|LZ77> | + | <box 90% blue|LZ77 (Lempel-Ziv)> |
- | * Jako slovník se používá jistá zpracovaná část zdrojového textu, vybíraná klouzajícím oknem, kódují se v něm obsažené řetězce proměnlivé. | + | * Jako slovník se používá jistá zpracovaná část zdrojového textu, vybíraná klouzajícím oknem, kódují se v něm obsažené řetězce proměnné délky. |
* Výstupem je trojice: | * Výstupem je trojice: | ||
* ukazatel počátku vzoru ve slovníku | * ukazatel počátku vzoru ve slovníku | ||
Řádek 218: | Řádek 215: | ||
</box> | </box> | ||
- | <box 90% blue|LZ78> | + | <box 90% blue|LZ78 (Lempel-Ziv)> |
* Používá se samostatný dynamicky vytvářený slovník. | * Používá se samostatný dynamicky vytvářený slovník. | ||
* Výstupem je dvojice: | * Výstupem je dvojice: | ||
Řádek 225: | Řádek 222: | ||
</box> | </box> | ||
- | <box 90% blue|LZW> | + | <box 90% blue|LZW (Lempel-Ziv-Welch)> |
* Používá se samostatný dynamicky vytvářený slovník. | * Používá se samostatný dynamicky vytvářený slovník. | ||
* Potenciální elementy slovníku jsou v kódové knize přednastaveny. | * Potenciální elementy slovníku jsou v kódové knize přednastaveny. | ||
Řádek 285: | Řádek 282: | ||
</box> | </box> | ||
+ | == Statické x dynamické soubory == | ||
- | === 1. Statické organizace souborů ==== | + | * návrh **statických** (neměnných souborů) je snadno dosažitelný |
- | * homogenní soubor -- hodnoty položek jsou primitivní typy, všechny záznamy jsou jednoho typu | + | * návrh **dynamický struktur** je obtížnější |
- | *je deklarovatelný formou S(A1:D1,...,An:Dn), kde Ax je jméno atributu a Dx je doména hodnot | + | * dochází k doplňování, modifikaci a odstraňování záznamů |
- | * nehomogenní soubor -- hodnoty položek jeho záznamů nejsou primitivní typy nebo záznamy nejsou jednoho typu | + | * příklady: |
+ | * B-strom | ||
+ | * dynamický haš soubor | ||
+ | * založený na rozšiřitelném hašování nebo lineárním hašování | ||
- | **Do statické organizace souborů patří:** | + | == Záznamy pevné x proměnné délky == |
- | * **hromada (neuspořádaný sekvenční soubor)** | + | |
- | * Hromada (heap) je nejjednodušší schéma organizace souboru, kdy jsou záznamy v souboru jen náhodně naházeny za sebou. Časová složitost vyhledávání je O(n) (lineární), pokud n je počet záznamů. Jde o nehomogenní soubor, kde záznamy obvykle nemají pevnou délku. | + | |
- | * **neuspořádaný sekvenční soubor** | + | |
- | * homogenní soubor | + | |
- | * sekvenční přístup | + | |
- | * homogenní obdoba hromady | + | |
- | {{:home:prog:neusek.jpg?500|}} | + | |
- | * **uspořádaný sekvenční soubor** | + | |
- | * V uspořádaném sekvenčním souboru jsou záznamy řazeny podle vyhledávacího klíče. Aktualizované záznamy se umístí do zvláštního souboru a až při další operaci //reorganization// jsou přidány do primárního souboru. Složitost nalezení záznamu je také O(n) (lineární), ale pokud se hledá podle klíče, podle kterého jsou záznamy seřazeny, a navíc je soubor na médiu s přímým přístupem, sníží se na O(log n) (logaritmická). | + | |
- | * **Primární soubor** + **soubor aktualizací** (dodatečných změn) | + | |
- | * **Soubor aktualizací** nebývá seřazený (dopisuje se na konec) | + | |
- | * **Reorganizace**: seřadíme soubor aktualizací + zatřídíme s primárním souborem do nového primárního souboru | + | |
- | * nevýhody primárního souboru -- při vkládání je nutná náročná reorganizace | + | |
- | * **keysort** -- snižuje náklady na reorganizaci -- udržuje se soubor (nemusí být seřazený) + index (je vždy seřazený) | + | |
- | * **řetězené struktury** -- řetězení usnadní následná vkládání a rušení záznamů | + | |
- | Ukázka uspořádaného sekvenčního souboru -- keysort: | + | |
- | {{:home:prog:usp_sekv_soubor_1_obr.png?500| Uspořádaný sekvenční soubor -- keysort}} | + | |
- | Ukázka uspořádaného sekvenčního souboru -- řetězené struktury: | + | |
- | {{:home:prog:usp_sekv_soubor_2_obr.png?500| Uspořádaný sekvenční soubor -- řetězené struktury}} | + | |
- | * **index-sekvenční soubor** | + | |
- | * části: primární soubor, index a oblast přetečení | + | |
- | * primární soubor je seřazený podle primárního klíče, ke kterému je vytvořena struktura indexů | + | |
- | * 2 možné přístupy -- indexový i sekvenční | + | |
- | * Indexem se vymezuje oblast stránek v primárním souboru, kde záznam může ležet, tato oblast se prohlíží sekvenčně | + | |
- | * buckety pro přesahy, nutná občasná reorganizace | + | |
- | {{:home:prog:index-sekvencni.png?500|}} | + | |
- | * **indexovaný soubor** | + | |
- | * seřadí se index, primární soubor se záznamy je neseřazený | + | |
- | * Indexovaný soubor znamená primární soubor plus indexy pro různé vyhledávací klíče. Neindexují se už stránky, ale přímo záznamy, a proto primární soubor nemusí být nutně seřazený. Index může být podobný jako u index-sekvenčního souboru, pro záznamy se stejným klíčem je ale vhodné, aby byly na všech úrovních indexu kromě poslední sloučené. Při aktualizaci se nepoužívá oblast přetečení, mění se pouze index. | + | |
- | {{:home:prog:index.png?500|}} | + | |
- | * **soubor s přímým přístupem** (tak kdyz je tam hash tak to asi patri do dynamickych struktur) | + | |
- | * algoritmická transformace vyhledávacího klíče na adresu záznamu | + | |
- | * hašování | + | |
+ | * implicitní (fixní) délka záznamu | ||
+ | * neuvádějí se oddělovače záznamů | ||
+ | * variabilní délka záznamu se vyjadřuje: | ||
+ | * explicitně (např. na začátku záznamu) | ||
+ | * oddělovačem na konci záznamu | ||
+ | * ukazatelem na záznam uloženým v jiném souboru (indexu) | ||
- | === 2. Dynamické organizace souborů === | + | Položky: |
- | Motivace: změny dat neznamenají velké (globální) reorganizace, které jsou drahé, ale spíše reorganizace lokální. | + | * fixní struktura |
- | - B-strom | + | * bez oddělovačů |
- | - dynamický haš soubor | + | * variabilní |
- | * založený na rozšiřitelném hašování nebo lineárním hašování | + | * explicitně |
+ | * oddělovačem | ||
+ | Důvod volitelných délek: | ||
+ | * obsah proměnné délky | ||
+ | * seznam hodnot | ||
+ | * volitelné položky | ||
+ | |||
+ | <box 90% red|Blok> | ||
+ | Samostatně manipulovatelná/adresovatelná datová jednotka na vnější paměti. | ||
+ | |||
+ | * neblokovaný záznam | ||
+ | * blok obsahuje právě jeden logický záznam | ||
+ | * blokovaný záznam | ||
+ | * blok obsahuje celistvý počet logických záznamů | ||
+ | * přerostlé záznamy | ||
+ | * záznamy jsou zapisované do bloků nezávisle na hranice | ||
+ | </box> | ||
+ | * **homogenní soubor** | ||
+ | * hodnoty položek jsou primitivní typy | ||
+ | * všechny záznamy jsou jednoho typu | ||
+ | * je deklarovatelný formou S(A1:D1,...,An:Dn), kde Ax je jméno atributu a Dx je doména hodnot | ||
+ | * **nehomogenní soubor** | ||
+ | * hodnoty položek jeho záznamů nejsou primitivní typy nebo záznamy nejsou jednoho typu | ||
Řádek 344: | Řádek 340: | ||
* logická paměť obsahuje primární soubory i sekundární (pomocné) soubory (indexy, rejstříky) | * logická paměť obsahuje primární soubory i sekundární (pomocné) soubory (indexy, rejstříky) | ||
* **Fyzické schéma** | * **Fyzické schéma** | ||
- | * Zobrazení logických stránek do fyzických stránek konkríétního použitého typu vnější paměti. | + | * Zobrazení logických stránek do fyzických stránek konkrétního použitého typu vnější paměti. |
* **Implementační schéma** | * **Implementační schéma** | ||
* Zajišťuje alokaci fyzických stránek v použitém zařízení. | * Zajišťuje alokaci fyzických stránek v použitém zařízení. | ||
Řádek 351: | Řádek 347: | ||
+ | ==Přístup k souborům== | ||
+ | * sekvenční | ||
+ | * aplikovatelné na pásce disku | ||
+ | * přímý přístup | ||
+ | * aplikovatelné na disku | ||
+ | * určení místa pomocí indexu, nebo hašování | ||
+ | ==Formy organizace souborů== | ||
+ | * hromada | ||
+ | * sekvenční soubor | ||
+ | * indexovaný sekvenční soubor | ||
+ | * indexovaný soubor | ||
+ | * hašovaný soubor (soubor s přímým přístupem) | ||
- | <box 90% round blue | Definice>**soubor 1** = pojmenovaná kolekce souvisejících záznamů | ||
- | **soubor 2** = logická paměťová jednotka zobrazovaná operačním systémem do fyzického paměťového zařízení | ||
- | **záznam** = kolekce atributů charakterizujících jistý objekt | ||
- | **adresář** = kolekce dat obsahující informace o souborech uchovávaných na disku (jméno, typ, adresa, délka, maximální délka, čas posledního přístupu...)</box> | ||
- | == Možná formátování == | + | ==Zamykání souborů== |
- | - volné formátování -- sekvenčně řazené záznamy pevné i proměnlivé délky | + | * **povinné**: zamčený soubor je nepřístupný |
- | - komplexní formátování -- soubor obsahuje vhodné řídící struktury nebo se k záznamům přistupuje přes přístupové funkce (B-stromy, haše...) | + | * **poradní**: proces si může zjistit stav zámku a rozhodnout se |
- | == Uložení souborů na disku == | + | ==Popis dat== |
- | - souvislá alokace datových bloků | + | * **implicitní**: aplikace/uživatel data zná |
- | * soubor je na disku uložen v souvislé posloupnosti datových bloků | + | * **metadata**: uvedená v hlavičce souboru |
- | - alokace datových bloků pomocí zřetězeného seznamu | + | * častá standardizace pro třídu aplikací |
- | * každý datový blok obsahuje data a ukazatel na následující datový blok | + | |
- | - alokace datových bloků pomocí tabulky | + | |
- | * alokace datových bloků je založená na zřetězeném seznamu, ale ukazatele na následující datový blok jsou uloženy v tabulce FAT | + | |
- | - i-nodes | + | |
- | * i-node je struktura, která obsahuje jak atributy souboru, tak adresy datových bloků, ve kterých je uložen obsah souboru | + | |
+ | ==Adresář== | ||
+ | Kolekce dat obsahující informace o souborech uchovávaných na disku (jméno, typ, adresa, délka, maximální délka, čas posledního přístupu...) | ||
- | * Popis dat | + | * Sám je souborem. |
- | * implicitní: aplikace/uživatel data zná | + | |
- | * metadata: uvedená v hlavičce souboru | + | |
- | * častá standardizace pro třídu aplikací | + | |
- | + | **Struktury:** | |
- | * **Klasifikace souborových organizací** | + | |
- | * sekvenční přístup (aplikovatelné na pásce, na disku) | + | |
- | * přímý přístup (aplikovatelné na disku) | + | |
- | * Určení místo pomocí **indexu**, nebo **hašování** | + | |
- | + | ||
- | * Zamykání souborů | + | |
- | * povinné: zamčený soubor je nepřístupný | + | |
- | * poradní: proces si může zjistit stav zámku a rozhodnout se | + | |
- | + | ||
- | * Adresář = kolekce dat obsahující informace o souborech uschovaných na disku. | + | |
- | * Sám je souborem. | + | |
- | * Struktury: | + | |
<box 90% red|1-úrovňový adresář> | <box 90% red|1-úrovňový adresář> | ||
Řádek 422: | Řádek 408: | ||
- | * Řízení přístupu | + | == Řízení přístupu == |
- | * volitelné řízení přístupu (vlastní určuje KDO a CO kdo může) | + | |
- | * UNIX rwx/ugo | + | |
- | * Access control lists | + | |
- | * Capability Tickets | + | |
- | * povinné řízení (práva k souborům prosazována bezpečnostní politikou) | + | |
- | <box 90% blue|Inode> | + | * volitelné řízení přístupu (vlastní určuje KDO a CO kdo může) |
- | Řídící struktura obsahující klíčové informace potřebné pro oeprační systém při správě konkrétního souboru. | + | * UNIX rwx/ugo |
- | </box> | + | * Access control lists |
+ | * Capability Tickets | ||
+ | * povinné řízení (práva k souborům prosazována bezpečnostní politikou) | ||
- | === Implementace systému souborů === | ||
- | <box 90% blue|File Allocation Table (FAT)> | + | |
- | = vázané přidělování diskového prostoru | + | |
- | * využití v MS-DOS, Windows | ||
- | * jednoduchá metoda | ||
- | * vázaný seznam nesousedních bloků disku | ||
- | * ➖ pevný počet položek | ||
- | </box> | + | ==== Indexování a hašování ==== |
- | <box 90% blue|Mapa disku, UNIX> | + | * procházení přímo záznamů je při operacích velice pomalé -- indexy mají řádově menší velikost než samotné záznamy a jejich prohledávání je výrazně rychlejší |
- | * Inode obsahuje (mimo jiné): | + | * díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk |
- | * přímé odkazy na bloky (12x4KB) | + | * často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů -- na základě indexů je možné efektivně provádět filtrování |
- | * single indirect (až 48MB) | + | * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color> |
- | * double indirect (až 4GB) | + | |
- | * triple indirect (až 4TB) | + | |
- | </box> | + | |
- | <box 90% blue|NTFS> | + | __typy indexů:__ |
- | * základem je NTFS svažek (volume) uložýí na diskové oblasti | + | |
- | * všechna metadata ukládána do svazku jako soubory | + | |
- | * struktura | + | |
- | * ID sektor (boot) | + | |
- | * tabulka Master File Table (MFT) -- obsahuje záznamy o souborech (i metadata) | + | |
- | * ostatní systémové soubory | + | |
- | * zrcadlová kopie MFT | + | |
- | * soubor s protokolem pro obnovu | + | |
- | * metadata souborového systému | + | |
- | * soubor s bitovou mapou volných a přidělených alokačních bloků | + | |
- | * soubor s definicí vadných sektorů | + | |
- | * uživatelské adresáře a data | + | |
- | </box> | + | |
+ | * **řádné, lineární indexy**: | ||
+ | * v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče | ||
+ | * **hašované indexy** | ||
+ | * využití hašovací funkce vyhledávacího klíče | ||
+ | * **stromové indexy** | ||
+ | * využití grafové struktury strom | ||
+ | * **indexové bitové mapy** | ||
+ | * pozice bitů v bitovém vektoru určují lokality záznamů | ||
+ | * vhodné pro atributy s malým množstvím různých hodnot (uchováváme bitovou mapu pro každou hodnotu) | ||
+ | Indexy mohou být víceúrovňové -- "index do indexu" -- nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy | ||
+ | === Řádné indexy === | ||
+ | Obvykle pokud se mluví o indexech, jsou myšleny řádné. | ||
+ | **Primární x sekundární** | ||
+ | * **primární index** | ||
+ | * podle jeho klíče je uspořádán primární soubor se záznamy | ||
+ | * může být hustý nebo řídký | ||
+ | * sekundární index | ||
+ | * určený pro dotazy založené na jiném vyhledávacím klíči než na primárním | ||
+ | * musí být hustý | ||
+ | **Hustý x řídký** | ||
+ | * **hustý** | ||
+ | * indexový záznam pro každou hodnotu vyhledávacího klíče. | ||
+ | * Typicky bývá uspořádán podle hodnoty klíče | ||
- | ==== Indexování a hašování ==== | + | {{:home:prog:husty.jpg?500|}} |
- | * procházení přímo záznamů je při operacích velice pomalé -- indexy mají řádově menší velikost než samotné záznamy a jejich prohledávání je výrazně rychlejší | + | * **řídký** |
- | * díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk | + | * indexový záznam pouze pro některé hodnoty vyhledávacího klíče |
- | * často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů -- na základě indexů je možné efektivně provádět filtrování | + | * použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán |
- | * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color> | + | |
- | * __typy indexů:__ | + | |
- | *řádné, lineární indexy -- v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče | + | |
- | *hašované indexy -- využití hašovací funkce vyhledávacího klíče | + | |
- | *stromové indexy -- využití grafové struktury strom | + | |
- | *indexové bitové mapy -- pozice bitů v bitovém vektoru určují lokality záznamů | + | |
- | * indexy mohou být víceúrovňové -- "index do indexu" -- nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy | + | |
- | === Řádné indexy === | ||
- | Obvykle pokud se mluví o indexech, jsou myšleny řádné. | ||
- | **Dělení 1** | ||
- | - primární index -- podle jeho klíče je uspořádán primární soubor se záznamy; může být hustý nebo řídký | ||
- | - sekundární index -- určený pro dotazy založené na jiném vyhledávacím klíči než na primárním; musí být hustý | ||
- | **Dělení 2** | ||
- | //hustý// -- indexový záznam pro každou hodnotu vyhledávacího klíče. Typicky bývá uspořádán podle hodnoty klíče | ||
- | {{:home:prog:husty.jpg?500|}} | ||
- | //řídký// -- indexový záznam pouze pro některé hodnoty vyhledávacího klíče; použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán | ||
{{:home:prog:ridky.jpg?500|}} | {{:home:prog:ridky.jpg?500|}} | ||
Řádek 532: | Řádek 500: | ||
=== Hašování === | === Hašování === | ||
- | <box 90% round blue | Definice>**hašovací funkce (obecně)** = převedení libovolně dlouhého vstupu na výstup pevné délky | + | |
- | **hašovací funkce (ve smyslu organizace souborů)** = funkce řešící přístup k záznamům souboru s konstantní složitostí | + | |
+ | <box 90% round blue | Definice> | ||
+ | |||
+ | **hašovací funkce (obecně)** = Funkce, která mapuje libovolně velký vstup na výstup fixní délky a není prostá. | ||
+ | **hašovací funkce (ve smyslu organizace souborů)** = Funkce řešící přístup k záznamům souboru s konstantní složitostí. | ||
**kolize** = situace, kdy je pro více záznamů spočítána stejná adresa | **kolize** = situace, kdy je pro více záznamů spočítána stejná adresa | ||
- | * obvykle se řeší pomocí bucketů -- každé paměťové místo má předepsanou kapacitu záznamů, ve které se následně vyhledává lineárně | + | * při nalezení kolize umisťujeme nový prvek: |
+ | * ve stejné paměti (**otevřené adresování**) | ||
+ | * lineární, kvadratické adresování | ||
+ | * řetězení kolizí | ||
+ | * násobné hašování | ||
+ | * v jiné paměťové oblasti (**closed addressing**) | ||
+ | * umístění do **kapes** | ||
</box> | </box> | ||
- | Perfektní hašovací funkce -- hašovací funkce //h//, která je prostá. | + | |
Požadované vlastnosti hašovací funkce: | Požadované vlastnosti hašovací funkce: | ||
* je deterministická | * je deterministická | ||
Řádek 543: | Řádek 522: | ||
* vypočítává se z hodnot všech nebo alespoň většiny bitů klíče | * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče | ||
* pokrývá cílový prostor rovnoměrně | * pokrývá cílový prostor rovnoměrně | ||
+ | * drobná změna ve vstupu vede k výrazné změně ve výstupu | ||
+ | * prostá = //perfektní hašování// | ||
== Statické hašování == | == Statické hašování == | ||
* používá se u souborů, které procházejí jen minimem změn | * používá se u souborů, které procházejí jen minimem změn | ||
- | * případné změny mohou negativně ovlivnit efektivitu hašování -- pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost | + | * případné změny mohou negativně ovlivnit efektivitu hašování |
+ | * pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost | ||
== Dynamické hašování == | == Dynamické hašování == | ||
+ | |||
+ | <box 90% blue|Rozšiřitelné hašování> | ||
+ | |||
* k výpočtu adresy se používá pouze prvních //i// bitů z výstupu hašovací funkce; toto //i// se dynamicky mění -- pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se //i// zmenšuje | * k výpočtu adresy se používá pouze prvních //i// bitů z výstupu hašovací funkce; toto //i// se dynamicky mění -- pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se //i// zmenšuje | ||
* používá se u souborů s proměnným počtem záznamů | * používá se u souborů s proměnným počtem záznamů | ||
* buckety jsou naplněné rovnoměrně -- pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují | * buckety jsou naplněné rovnoměrně -- pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují | ||
- | * Druhy: | + | |
- | * rozšiřitelné hašování | + | |
{{:home:prog:rozhas.jpg|}} | {{:home:prog:rozhas.jpg|}} | ||
- | <note> | + | |
* hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce) | * hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce) | ||
* jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)** | * jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)** | ||
Řádek 562: | Řádek 546: | ||
* globální hloubka > lokální hloubka -- na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva | * globální hloubka > lokální hloubka -- na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva | ||
* globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes | * globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes | ||
- | </note> | + | </box> |
- | * lineární hašování | + | |
- | <note> | + | |
+ | <box 90% blue|Lineární hašování> | ||
* řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s **přetokovými kapsami** | * řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s **přetokovými kapsami** | ||
* počet kapes udržuje tak, aby byly naplněny z např. 80 % | * počet kapes udržuje tak, aby byly naplněny z např. 80 % | ||
* rozdíl oproti rozšiřitelnému hašování: **nemusí se vytvářet ani udržovat adresář kapes**, přesto počet kapes roste **lineárně**. | * rozdíl oproti rozšiřitelnému hašování: **nemusí se vytvářet ani udržovat adresář kapes**, přesto počet kapes roste **lineárně**. | ||
- | </note> | + | </box> |