Skip to content

7.2 Hešovací funkce

Ideální a dobře fungující hešovací funkce

  • Složitost operací Find\((k)\) a Insert\((x)\) zjevně závisí na složitosti výpočtu hešovací funkce a na tom, jak rozmísťuje ukládané prvky do přihrádek.
  • Ideální hešovací funkce \(h: U \to P\) vypočte číslo přihrádky v konstantním čase a zadanou \(n\)-prvkovou množinu vstupních klíčů \(K\) rozprostře mezi \(m\) přihrádek \(P\) dokonale rovnoměrně, tzn. všechny přihrádky budou mít nejvýše \(\lceil n/m \rceil\) prvků.
  • Ideální hešovací funkce je obvykle nemožné sestrojit, proto se používají funkce, které se chovají „prakticky náhodně“.
  • Ukážeme několik příkladů hešovacích funkcí, pro které bylo experimentálně ověřeno, že dobře hešují nejrůznější typy dat.

Příklady dobře fungujících hešovacích funkcí

1. Lineární kongruence

Lineární kongruence: \(k \mapsto ak\ mod\ m\).

  • Zde \(m\) je typicky prvočíslo a \(a\) je nějaká dostatečně velká konstanta nesoudělná s \(m\).
  • Často se a nastavuje blízko celé části \(0.618m\).

2. Vyšší bity součinu

Vyšší bity součinu: \(k \mapsto \lfloor (ak\ mod\ 2^w)/2^{w−ℓ} \rfloor\).

  • Pokud hešujeme \(w\)-bitové klíče do \(m = 2^l\) přihrádek, vybereme \(w\)-bitovou lichou konstantu \(a\) (nesoudělnou s \(2^w\)).
  • Pak pro každé \(k\) spočítáme \(ak\), ořízneme ho na \(w\) bitů a z nich vezmeme nejvyšších \(l\).
  • Vzhledem k tomu, že přetečení ve většině programovacích jazyků automaticky ořezává výsledek, stačí k výpočtu hešovací funkce jedno násobení a bitový posun.

3. Skalární součin

Skalární součin: \(k_0,...,k_{d-1} \mapsto (\sum_{i=0}^{d-1} a_ik_i)\ mod\ m\)

  • Posloupnost klíčů zahešujeme tak, že zahešujeme každý klíč zvlášť a výsledky sečteme.
  • Pokud \(i\)-tý klíč \(k_i\) zahešujeme lineární kongruencí \(k_i \to a_ik_i\ mod\ m\), je heš celé posloupnosti její skalární součin s vektorem konstant \((a_0, a_1, . . . , a_{d−1})\) modulo \(m\)
  • Podobně lze heš počítat v dvojkové soustavě pomocí operace XOR místo součtu.

4. Polynom

Polynom: \(k_0,...,k_{d-1} \mapsto (\sum_{i=0}^{d-1} a^ik_i)\ mod\ m\)

  • Zvolíme jednu konstantu \(a\) a počítáme skalární součin zadané posloupnosti s vektorem mocnin \((a^0,a^1,...,a^{d−1})\) a opět modulo \(m\).

Ideální hešování

  • Přestože jsou vlastnosti hešovacích funkcí často postaveny na experimentálních výsledcích, pro některé případy hešování lze provést i exaktní analýzu.

  • Požadované vlastnosti hešovací funkce:

  • Výpočet \(h(k)\) je rychlý (\(O(1)\)) a funkce \(h\) neukládá žádná data do paměti. Speciálně je tedy její výpočet nezávislý na historii předchozích volání

  • Hešovací funkce \(h\) rozděluje univerzum \(\mathcal{U}\) do přihrádek rovnoměrně, například takto:
\[\forall i \neq j \in \{0,...,m-1\} : |h^{-1}(i)| = |h^{-1}(j)| \pm 1\]

Časová složitost ideálního hešování

Fakt (neformální)

Uvažujme hešovací tabulku velikosti \(m\) s \(n\) prvky a s hešovací funkcí \(h\) a nechť jsou splněny předpoklady 1) a 2). Nechť navíc platí, že vstupní data jsou z univerza \(\mathcal{U}\) vybírána nezávisle rovnoměrně náhodně. Potom

  1. průměr počtu prvků v přihrádce je \(n/m\)
  2. počet prvků v přihrádce je \(O(n/m)\) pro skoro všechny přihrádky
  3. průměrný počet operací vykonaných při hledání, vkládání imazání je \(O(n/m)\).

Nafukovací hešovací tabulka a přehešování

  • Předpokládejme, že počet zahešovaných prvků \(n\) předem neznáme a nedokážeme jej rozumně odhadnout.
  • Jak máme zvolit počet přihrádek \(m\) hešovací tabulky, pokud budeme chtít zajistit, aby faktor naplnění hešovací tabulky \(α = n/m\) nepřekročil zadanou konstantu \(Z\)?

  • Pomůže nám technika amortizovaného nafukovacího pole.

    • Na počátku založíme prázdnou hešovací tabulku s nějakým počátečním počtem přihrádek \(m = m_0\).
    • Po vložení prvku zkontrolujeme \(α = n/m\).
    • Pokud \(α \gt Z\), je hešovací tabulka přeplněná. Pak zdvojnásobíme \(m\), zvolíme novou hešovací funkci a všechny prvky přehešujeme: pro každý prvek ze staré tabulky spočteme novou hešovací funkci a vložíme do nové tabulky.