7.4 Volba vyhledávací posloupnosti

• Jak volit vyhledávací posloupnosti?
• Ukážeme základní možnosti, které se často používají v praxi

Lineární přidávání

Lineární přidávání (Linear Probing): Vyhledávací posloupnost je dána funkcí \(h(k,i) = (f(k) + i)\ mod\ m\), kde \(f(k)\) je „obyčejná“ hešovací funkce a \(i\) je počet neúspěšných pokusů v aktuální operaci.

• Zkoušíme tedy jednoduše za sebou jdoucí přihrádky.
• Výhodou je sekvenční přístup do paměti, který je na dnešních počítačích se skrytými pamětmi (cache memory) rychlejší.
• Nevýhodou je to, že jakmile se vytvoří souvislé bloky obsazených přihrádek, další vkládání se do nich často strefí a bloky dále porostou.
• Bez důkazu uvádíme, že pro neúspěšné hledání platí odhad průměrného počtu navštívených přihrádek
  1/\((1 − α)^2\). A to pouze, je-li \(f\) dokonale náhodná.
• Není-li, chování struktury obvykle degraduje. Lze zobecnit na lineární přidávání s krokem, kde \(h(k,i) = (f(k) + c \cdot i)\ mod\ m\) a \(c \gt 1\) je konstanta nesoudělná s \(m\).

Dvojité hešování

Dvojité hešování (Double Hashing): Vyhledávací posloupnost je dána funkcí \(h(k,i) = (f(k) + i · g(k))\ mod\ m\), kde \(f : \mathcal{U} \to \{0,...,m − 1\}\) a \(g : \mathcal{U} \to \{1,...,m − 1\}\) jsou dvě různé hešovací funkce, \(m\) je prvočíslo a \(i\) je počet neúspěšných pokusů v aktuální operaci

• Protože \(m\) je prvočíslo, je s ním \(g(k)\) vždy nesoudělné a vyhledávací posloupnost navštíví každou přihrádku právě jednou.
• Je známo, že pro dokonale náhodné funkce \(f\) a \(g\) se dvojité hešování chová stejně dobře, jako při použití plně náhodných vyhledávacích posloupností.
• Toto tvrzení též ponecháváme bez důkazu.

Věta 7.1 (O efektivitě otevřené adresace)

Věta O efektivitě otevřené adresace

Pokud jsou vyhledávací posloupnosti náhodné permutace, pak neúspěšné hledání nahlédne v průměru do nejvýše 1/(1 − \(α\)) přihrádek, kde \(α = n/m\), \(n \lt m\), je faktor naplnění.

Důkaz Věty 7.1

• Nechť \(k\) je hledaný klíč a \(h_1,h_2,...,h_m\) jeho vyhledávací posloupnost.
• Označme \(p_i\) pravděpodobnost toho, že během hledání projdeme a zkusíme alespoň \(i\) přihrádek. Tedy pravděpodobnost toho, že přihrádky \(h_1,...,h_{i−1}\) jsou obsazené.
• Přihrádku \(h_1\) projdeme vždy, proto \(p_1 = 1\).
• Pravděpodobnost \(p_2\) je pravděpodobnost toho, že přihrádka \(h_1\) (náhodně vybraná z \(m\) možností) je obsazena libovolným klíčem z \(n\) možných.
• Proto \(p_2 = n/m = α\)
• Obecně \(p_{i+1}\) je pravděpodobnost toho, že i přihrádka \(h_i\) je obsazená, stejně jako \(i − 1\) předchozích.
• Čili náhodně vybraná přihrádka ze zbývajících \(m − (i − 1)\) možných přihrádek je obsazena libovolným klíčem ze zbývajících \(n − (i − 1)\) možných klíčů.
• Proto \(p_{i+1} = p_i \cdot (n − i + 1)/(m − i + 1) \le p_i · n/m = p_i \cdot α\)
• Indukcí dostaneme \(p_{i+1} \le α^i\)
• Nechť \(S\) = střední hodnota počtu navštívených přihrádek.
• Pak \(S = \sum_{i=1}^m i \cdot q_i\), kde \(q_i\) je pravděpodobnost, že jsme navštívili právě \(i\) přihrádek. Tedy, že přihrádky \(h_1,...,h_{i−1}\) jsou obsazené a přihrádka \(h_i\) je prázdná.
• Protože \(\mathbb{P}[h_1,...,h_{i−1}\ jsou\ obsazené] =\) \(\mathbb{P}[h_1,...,h_{i−1}\ jsou\ obsazené\ a\ h_i\ je\ prázdná] + \mathbb{P}[h_1,...,h_{i−1}\ jsou\ obsazené\ a h_i\ je\ obsazená]\), platí \(p_i = q_i + p_{i+1}\) čili \(q_i = p_i - p_{i+1}\). Proto

\[S = \sum_{i=1}^{m} i \cdot (p_i - p_{i+1}) = \sum_{i=1}^{m} i \cdot p_i - \sum_{i=1}^{m} i \cdot p_{i+1}\]

\[= \sum_{i=1}^{m} i \cdot p_i - \sum_{i=2}^{m} (i - 1) \cdot p_i = \sum_{i=1}^{m} p_i \cdot \big(i - (i - 1)\big)\]

\[= \sum_{i=1}^{m} p_i.\]

• Tedy

\[S = \sum_{i=1}^{m} p_i \leq \sum_{i=1}^{m} \alpha^{i-1} < \sum_{i=0}^{\infty} \alpha^i = \frac{1}{1-\alpha}\]

• Neboť α < 1 a jedná se tedy o konvergentní geometrickou řadu

Pozorování

• Jelikož \(n \lt m\), platí \(\forall i \ge n + 2\); \(p_i = 0\) a \(\forall i \ge n + 2\); \(q_i = 0\).
• Tudíž \(q_{n+1} = p_{n+1}\).