Uvažujme dále situaci, že množina A prvků uložených v tabulce je daleko menší než množina všech hodnot klíče, tedy │A│<<│K│. Pokud prvky množiny resp. ukazatele na ně budeme kvůli rychlosti přístupu chtít uchovávat v poli, abychom nemrhali pamětí, toto pole by mělo mít rozměr úměrný │A│. Zatím ponechme stranou jeho velikost ve vztahu k počtu uložených prvků množiny │A│ a označme jeho velikost a tím i velikost tabulky m, přičemž m <<│K│. V tabulce budou nyní prvky množiny identifikované svým klíčem zpřístupňovány pomocí indexu s hodnotami 0 až m-1. Potřebujeme tedy hodnotu klíče prvku transformovat na hodnotu indexu, jinými slovy musíme definovat funkci
h: K → {0,1, ... m -1}
kterou budeme nazývat rozptylovací funkcí (hash function).
Prvek s klíčem kÎK bude mít v tabulce index h(k), jak je znázorněno na obr.. Vzhledem k tomu, že m <<│K│, tedy počet všech klíčů je daleko větší než počet hodnot indexů, na které je zobrazujeme, nevyhnutně musí rozptylová funkce zobrazit obecně dva a více různých klíčů na stejný index, tj. pro u≠ v a u,vÎK bude h(u) = h(v), což je také znázorněno na obr.
. Tento jev nazýváme kolizí.
V ideálním případě, kdy rozptylová funkce je dostatečně „náhodná“, budou všechny klíče množiny uložených prvků zobrazeny na různé hodnoty indexů, samozřejmě za předpokladu m ≥ │A│. Na druhé straně je možné, že v nejhorším případě se klíče všech uložených prvků zobrazí na jeden index. Při náhodném výběru prvků nelze kolize obecně vyloučit a musíme se zabývat řešením této situace.
Při postupném vkládání prvků dynamické množiny do tabulky, v případě, že prvek má být umístněn na pozici v tabulce, která je již obsazena, v zásadě existují dvě možnosti. První je vnější zřetězení prvků, kterých klíče rozptylová funkce zobrazí na stejnou hodnotu. Druhou je otevřené adresování, kdy v případě kolize je prvek množiny systematicky umístněn a následně hledán v tabulce. V tomto případě musí být m ≥ │A│, zatímco v prvním případě přichází do úvahy všechny možnosti, tj. m < │A│, m = │A│ i m < │A│. Dále se budeme zabývat první přístupem.
Kolize jsou při této metodě řešeny tak, že se vytvoří seznam prvků, jejichž klíče jsou zobrazeny na stejnou pozici v tabulce, což je znázorněno na obr..
Prvky dynamické množiny jsou reprezentovány objekty třídy Prvek (obr.), která kromě klíče a dat obsahuje ukazatel na další a předcházející objekt této třídy. Ukazatel predch není obecně nutný, a proto není ani uveden na předcházejícím obrázku, ale jak již víme, umožní nám efektivní implementaci operace vybrání prvku z tabulky.
Operace hledej, vlož a vyber jsou implementovány stejnojmennými metodami na obr., které je převádí na operace nad seznamem, reprezentovaným prvkem pole t[h(k)], kde k je klíč, respektive t[h(x.klic)], kde x je prvek.
Vkládáme-li prvek na začátek odpovídajícího seznamu a parametrem metody je ukazatel na vkládaný prvek, operace vložení prvku do tabulky je O(1). To znamená, že na předcházejícím obrázku byl jako první vložen prvek s klíčem u a za ním prvek s klíčem v. Obecně totiž hledání prvků není založeno na jejich upořádaní jako tomu bylo například u BVS. Dokonce, u některých aplikací zpracovávajících vnořené struktury, například
{int identifikator1 ...
{int identifikator2 ...
} ...
}
je zásobníkový charakter takového seznamu výhodou, protože identifikátory jsou do něj vkládány v pořadí výskytu v textu a zpracovávány jsou napřed vnořené. Na druhé straně jako u BVS předpokládáme, že všechny klíče jsou různé.
Operace odebrání prvku, protože parametrem metody vyber je také ukazatel na prvek a seznam je implementován jako obousměrný, je také O(1). Časová náročnost operace hledej zřejmě závisí na tom, kolik prvků je před hledaným prvkem v odpovídajícím seznamu vloženo v důsledku kolizí.
Připomeňme, že do tabulky o m pozicích vkládáme │A│ prvků s různými klíči z množiny všech klíčů o velikosti │K│, přičemž m <<│K│.
Pro triviální případ │A│= 1, kolize nemůže vzniknout. Pro │A│≤ m, má rozptylovací funkce šanci přidělit každému vkládanému prvku různou pozici, ale je i možnost, že všechny prvky budou vloženy na stejnou pozici v tabulce a vytvoří seznam délky │A│.
Pokud do m přihrádek umístíme n > m kuliček, alespoň v jedné přihrádce musí být více než jedna kulička. (Důkaz se provede sporem.)
Pro │A│>m, tedy bude alespoň jeden seznam obsahovat více než jeden prvek a kolize musí nastat.
Zkoumejme, jaká je pravděpodobnost vzniku kolize, je-li 1 ≤ │A│≤ m. Tato pravděpodobnost bude záviset na vlastnostech rozptylovací funkce, tedy na tom jestli distribuuje množinu klíčů do pozic v tabulce rovnoměrně. Předpokládejme, že tak činíme a to náhodně. To znamená, že pro každou hodnotu klíče je stejně pravděpodobné jeho zobrazení na každou z m pozic tabulky.
Narozeninový problém dává odpověď na otázku, při vložení kolika prvků je 50% pravděpodobnost vzniku kolize.
Kolik lidí se musí nacházet v místnosti, aby, ignorujíc 29. únor, dva z nich měli narozeniny ve stejný den roku s pravděpodobností alespoň 50%.
Označme Q(n) pravděpodobnost, že žádní dva lidé ve skupině velikosti k nemají narozeniny ve stejný den, přičemž všech 365 v dnů roce je stejně pravděpodobných.
Začněme libovolným dnem narození jednoho člověka ze skupiny. Potom na to, aby dva lidé neměli narozeniny ve stejný den, narozeniny druhého z nich musí být v jednom ze zbývajících 364 dnů z 365 dnů v roce, tedy
Q(2) = 364/365
Na to, aby tři lidé měli narozeniny v různé dny, musí mít dva narozeniny v různé dny a třetí musí mít narozeniny v jednom ze zbývajících 363 dnů, tedy
Q(3) = Q(2) * (363/365)
až nakonec
Q(n) = Q(n - 1) * [365 - (n - 1)] / 365
364*363*...*[365 - (n - 1)] 365!
Q(n) = ───────────────── = ──────────
365 n - 1 365 n (365 - n)!
je hledaná pravděpodobnost, že žádní dva lidé ve skupině o velikosti n nemají narozeniny ve stejný den. Pravděpodobnost P(n), že alespoň dva lidé v této skupině mají narozeniny ve stejný den tedy je
365!
P(n) = 1 - Q(n) = 1 - ───────────
365n (365 - n)!
Spočítejme tyto pravděpodobnosti pro n = 2, 3, ... .
n P(n)
5 0.027
10 0.117
15 0.253
20 0.411
22 0.476
23 0.507
25 0.569
30 0.706
40 0.891
50 0.970
60 0.994
Odpověď je, že hledaná velikost je 23 lidí.
Pro rozptylovou tabulku to znamená, že je-li její velikost m = 365, je 50% pravděpodobnost vzniku kolize již po vložení 23 prvků, což je 6,3% z počtu kdy kolize vzniknout musí. Lze tedy očekávat, že kolize budou poměrně časté, i když velikost aktuální množiny prvků │A│bude o dost menší než velikost tabulky m.
To nás vede k bližšímu prozkoumání situace, kdy velikost aktuální množiny je větší než počet pozic v tabulce, tj. │A│> m. Zkoumejme otázku, jaký je průměrný počet vložených prvků, když už při každém dalším vložení vznikne kolize. Jinými slovy, v každém seznamu t[i], i = 0,1, ..., m-1, bude alespoň jeden prvek. Odpověď dává řešení problému sběratele kupónů.
Mějme neomezené množství kuponů m typů. Vybereme-li náhodně vždycky jeden kupón, jaká je průměrná hodnota počtu výběrů W na to, abychom získali alespoň jeden kupón z každého typu.
Pravděpodobnost, získání typu kupónu, který ještě nemáme, když již máme i různých typů je
m - i
pi = ──── i = 0, 1, ..., m-1
m
Pravděpodobnost P(k) tohoto získání po k výběrech je tedy dána součinem pravděpodobností k-1 neúspěšných výběrů a pravděpodobnosti úspěšného výběru
P(k) = pi (1 - pi )k - 1
Vlastníme-li i různých typů kupónů, kupón typu, který ještě nemáme, získáme průměrně po Wi výběrech
∞ ∞
Wi = ∑ k pi (1 - pi )k - 1 = - pi [ ∑ (1 - pi )k ]´ = 1/ pi = m / (m-i )
k=1 k=0
Průměrný počet výběrů kuponů na získání všech typů potom je
m-1 m-1 m
W = ∑ Wi = m ∑ 1 / (m-i) = m ∑ 1 / j
i=0 i=0 j=1
Distribuuje-li rozptylová funkce klíče rovnoměrně náhodně do m pozic v tabulce, potom uvedený vztah udává průměrný počet vložených prvků, kdy už v každém seznamu t[i], i = 0,1, ..., m-1 bude alespoň jeden prvek a tedy při každém dalším vložení prvku vznikne kolize.
Pro tabulku s 365 pozicemi tato situace průměrně nastane po vložení více než 2364 prvků, tedy až množina uložených prvků bude mít asi 6.5 krát více prvků než je pozic v tabulce.
Uvedená analýza vzniku kolizí napovídá, že na zabránění kolizím, nemá význam volit velký počet pozic v tabulce vzhledem k velikosti ukládané množiny prvků. Navíc, situace se dramaticky nezhorší, ani tehdy, bude-li pozic v tabulce „rozumně“ méně než je počet prvků aktuální množiny.
Pro odvození časové náročnosti operace hledání musíme zkoumat délku seznamů prvků vznikajících v důsledku kolizí. Uvažujme tabulku o m pozicích s množinou uložených prvků o velikosti │A│= n. Podíl α = n /m nazveme koeficient zatížení.
Označme di délku seznamu t[i], i = 0,1, ..., m-1. Potom
n = d0 + d1 + … + dm-1
a protože rozptylovací funkce distribuuje klíče prvků rovnoměrně a náhodně, mají všechny seznamy stejnou průměrnou délku α = n /m.
Odhlédneme-li od času výpočtu O(1) rozptylovací funkce a přístupu k seznamu t[h(k)], bude čas hledání prvku v tabulce záviset lineárně na délce prohledávaného seznamu. Budeme rozlišovat případ, kdy hledaný prvek se v tabulce nenachází a případ, kdy se v tabulce nachází, jinými slovy úspěšné a neúspěšné hledání.
V případě neúspěšného hledání, jeho klíč se může se stejnou pravděpodobností zobrazit na libovolnou pozici, tedy průměrná doba hledání v seznamu je stejná a rovna α. Celková doba hledání včetně času výpočtu rozptylovací funkce a přístupu k seznamu je Θ(1 + α).
V případě, kdy hledaný prvek se nachází mezi uloženými prvky, bude se nacházet s větší pravděpodobností v dlouhém seznamu než v seznamu krátkém.
Čas hledání v seznamu vyjádřeme počtem prvků, které musíme při hledání projít. Pokud jsme zvolili vkládání na začátek seznamu je tento počet roven počtu prvků vložených před hledaný prvek plus jeden (ten, který hledáme).
Nechť byl hledaný prvek vložen jako j - tý v pořadí z n vložených prvků, j =1, 2, …, n. Po něm bylo vloženo n-j prvků, přičemž klíč každého z nich se zobrazil na libovolnou pozici v tabulce se stejnou pravděpodobností 1/m. Průměrná délka seznamů, které takto vznikly z uvažovaných n-j prvků, bude tedy (n-j ) /m.
Průměrný počet prvků, které nutno projít pro libovolný vložený prvek potom je
n n
1/n ∑ [ 1 + (n - j ) /m] = 1 + 1/(nm)∑(n - j ) =
j=1 j=1
n n
1 + 1/(nm)(∑n -∑ j ) =
j=1 j=1
1 + [n2 - n(n+1) /2] /nm = 1 + (n-1) /2m = 1 + α /2 - α /2n
Čas hledání existujícího prvku v tabulce včetně času výpočtu rozptylovací funkce a přístupu k seznamu je Θ(2 + α /2 - α /2n) = Θ(1 + α).
Je-li počet prvků dynamické množiny úměrný počtu pozic v tabulce, tj. n /m = konstanta, potom je průměrný čas hledání prvku v tabulce O(1). Připomeňme, že za jistých předpokladů jsme v úvodu této kapitoly odvodili, že čas vložení a vybrání prvku z tabulky je v nejhorším případě také O(1), pak jsou všechny uvedené operace nad tabulkou v průměru O(1).
Známe-li, nebo umíme alespoň odhadnout, počet prvků n, které chceme uložit v tabulce, jak zvolíme její velikost m? Z uvedeného zřejmě plyne, že pokud je kritická rychlost hledání, volíme m > n, za cenu větších nároků na paměť, když alespoň m-n pozic v tabulce bude nevyužitých. V opačném případě volíme m < n, kdy se úměrně prodlouží průměrný čas hledání. Obecně se doporučuje zvolit m = n a i když nakonec bude nutno vložit více prvků, vlastnosti se výrazně nezhorší.