Slovníky

Slovníky

• datová struktura k ukládání dat
• klíč — hodnota
• unikátní klíče
• dynamický rozsah
• operace:
• nalezení hodnoty podle klíče
• vložení hodnoty podle klíče
• odstranění hodnoty podle klíče

Vyvažování

• paměťové vs. časové nároky
• universum klíčů
• v praxi obrovské číslo
• bitové pole

Hešovací tabulka

• universum klíčů $U$
• konečný počet přihrádek $P = \{0, 1, \ldots, m-1\}$
• hešovací funkce $h: U \rightarrow P$


• uložení hodnoty $v \in U$ pod klíčem $h(v)$
• při hledání hodnoty víme, že bude v přihrádce $h(v)$

Kolize

• kolize — $h(v_1) = h(v_2)$
• způsobeno díky velikosti $U$ a $P$
• kolize jsou nevyhnutelné
• řešení různými způsoby

Příklady

$P = \{0, 1, \ldots, 9\}$

$h(v) = v \mod 10$

$U = \mathbb{N}$

Hešovací funkce

• složitost hledání a vkládán je závislá na složitosti výpočtu hešovací funkce
• ideální hešovací funkce
• konsantní složitost/čas
• rozdělení hodnot do přihrádek je rovnoměrné
• každá přihládka max. $\lceil \frac{n}{m} \rceil$ hodnot
• prakticky nemožné
• v praxi prakticky náhodné

Příklady hešovacích funkcí

Lineární kongurence

$h(v) = (a \cdot v) \mod m$

• $a$ je náhodné číslo z intervalu $\left<1, m-1\right>$
• $m$ je počet přihrádek
• $a$ a $m$ musí být nesoudělná

Vyšší bity součinu

Práce

Zjistěte, co tato funkce dělá.

Pro posloupnosti

Po posloupnosti existují speciální hešovací funkce, např. skalární součin či polyonomiální součet.

Řešení kolizí

Řetízkování

• každá přihrádka je spojový seznam
• při vkládání se nová hodnota přidá na konec seznamu pro danou přihrádku
• při hledání se projde seznam
• při mazání se hodnota odstraní ze seznamu

Řetízkování

$P = \{0, 1, \ldots, 9\}$

$h(v) = v \mod 10$

$U = \mathbb{N}$

Řetízkování

Práce

Implementujme řetízkování v hešovací tabulce.

Hroby

• přestává platit, že prvek musí být vždy v přihrádce, která odpovídá jeho heši
• závisí na zaplnění přihrádek
• hešovací funkce přijímá druhý parametr — počet pokusů
• při vkládání se zkusí vložit do přihrádky, pokud je obsazená, zkusí se další přihrádka, atd.

Hroby — hledání

find(key):
    for i = 0 to m - 1:
        j = h(key, i)
        if T[j] == key:
            return j
        else if T[j] == undefined:
            return undefined
    return undefined

Hroby — mazání

Komplikované, protože může dojít k tomu, že smazáním prvku se ztratí cesta k jinému prvku v pořadí. Místo smazání se proto nastaví na speciální hodnotu $\dagger$.

delete(key):
    for i = 0 to m - 1:
        j = h(key, i)
        if T[j] == key:
            T[j] = †
            return
        else if T[j] == undefined:
            return

Hroby — vkládání

insert(key):
    if find(key) != undefined:
        return
    for i = 0 to m - 1:
        j = h(key, i)
        if T[j] == undefined or T[j] = †
            T[j] = key
    throw table overflow

Dvojité hašování

Práce

Zjistěte, jak funguje dvojité hašování.