Cormackovo hašování: Porovnání verzí
Smazaný obsah Přidaný obsah
m Stránka Perfektní hešovaní (Cormack) přemístěna na stránku Perfektní hašovaní (Cormack): Koukal jsem se do literatury, anglické HASH se počešťuje jako hašování ne jako hešování |
Typos, nadbytečné řádky, dvojitý nadpis |
||
Řádek 1:
Cormakovo hašování je založeno na existenci primární hašovací funkce <math>h(k)</math>, a celé třídy sekundárních hašovacích funkcí <math>h_{i}(k,r)</math>. funkce <math>h(k)</math> musí mít [[obor hodnot]] roven velikosti adresáře.
Položky jsou ukládány do primárního souboru (pevné velikosti), způsobem, který bude popsán za pomoci adresáře (pevné velikosti). Protože je i primární soubor i adresář pevné velikosti, řadí se Cormacovo hašování do tzv. [[statické metody hešování|statických metod hešování]].
Primární soubor si jde představit jako pole pevné velikosti. Adresář vypadá následujícím způsobem:
{| border="1" cellpadding="2" cellspacing="2"
|+Adresář
! pozice !! p !! i !! r
|-
Řádek 32 ⟶ 30:
'''pozice''' je index položky v adresáři.
=== Příklad 1
<table border="0" cellpadding="20">
<tr><td>
{| border="1" cellpadding="2" cellspacing="2"
|+Adresář
! pozice !! p !! i !! r
|-
Řádek 105 ⟶ 103:
* Adresář[<math>h(k)</math>].p = p<sub>new</sub>
▲===Příklad 2.===
Zvolne velikost adresáře M=7.
Potom <math>h(k)</math> navrhneme ve tvaru <br>
Řádek 124 ⟶ 117:
{| border="1" cellpadding="2" cellspacing="2"
|+Adresář
! pozice !! p !! i !! r
|-
Řádek 245 ⟶ 238:
* spočteme <math>h(k)</math>.
* podle Adresář[<math>h(k)</math>].r se buď podíváme na přímo příslušné místo do primárního souboru, nebo spočteme příslušnou (Adresář[<math>h(k)</math>].i) sekundární hašovací funkci, najdeme příslušný blok a v něm příslušnou položku.
Další často používanou sekundární funkcí je funkce
<math>h_{i}(k,r)=(k \quad mod \quad (2i + 100r +1))\quad mod \quad r</math>
Predpokladá se, že <math> k << 2i + 100r +1</math>.
=== Pseudokód ===
Zadefinujeme si ješte nějaké datové položky:
Řádek 263 ⟶ 253:
body_1 *body=new body_1[];
</code>
==== Vyhledávání ====
<code>
int h(int k, int s) {}
Řádek 284 ⟶ 271:
==== Vkládání ====
...je trošku zložitejšie, c-like algoritmus není kompletní, ale je názorný...
Řádek 305 ⟶ 291:
}
</code>
[[Kategorie:
| |||