Tabulky s rozptýlenými položkami, vyhledávání v tabulkách - Historie editací

212.158.144.250: /* Otevřené rozptýlení - hash funkce */

2014-06-13T06:35:53Z

Otevřené rozptýlení - hash funkce

← Starší verze		Verze z 13. 6. 2014, 06:35
Řádka 21:		Řádka 21:
	4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi		4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi

−		+	Pro rovnoměrné rozptýlení prvků v tabulce se rozptylová funkce skládá ze dvou částí. Například když máme rozdělovat do tabulky podle počátečních písmen jmen -> 26 písmen, ale od Q moc jmen není. Modulární rozptylová funkce se vynásobí multiplikativní konstantou. Konstanta ''c'' je z intervalu ''0 ≤ c < 1''. Příkladem takové funkce potom je ''H(m,k)=0,97 * k mod m'', kde ''k'' je klíč a ''m'' velikost pole.

	== Uzavřené rozptýlení - přímé adresování ==		== Uzavřené rozptýlení - přímé adresování ==

Acolade: kategorizace

2014-02-20T06:44:26Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:44
Řádka 81:		Řádka 81:

	Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč		Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč
		+
		+
		+
		+	[[Kategorie:fav-kiv-bzinf]]

81.201.60.245 v 1. 6. 2012, 18:19

2012-06-01T18:19:24Z

← Starší verze		Verze z 1. 6. 2012, 18:19
Řádka 3:		Řádka 3:
	jen doplňky/opakování/upřesnění:		jen doplňky/opakování/upřesnění:

−	Vnitřní ~~zřetězení~~ - synonyma (položky s kolizemi) se ukládají do volných míst	+	'''Vnitřní zřetězen'''í - synonyma (položky s kolizemi) se ukládají do volných míst
−	Vnější zřetězení - synonyma se ukládají do seznamů pod klíči	+
		+	'''Vnější zřetězení''' - synonyma se ukládají do seznamů pod klíči
		+
		+
		+
		+	== Otevřené rozptýlení - hash funkce ==

−	~~Otevřené rozptýlení - hash funkce~~
	Kolize:		Kolize:
		+
	1) nedefinované chování při kolizi - nutno dodefinovat		1) nedefinované chování při kolizi - nutno dodefinovat
		+
	2) lineární posun - při kolizi vkládáme na první volné místo lineárně (na indexech 1,2,3,4 od původní polohy		2) lineární posun - při kolizi vkládáme na první volné místo lineárně (na indexech 1,2,3,4 od původní polohy
		+
	3) kvadratický posun - při kolizi hledáme první volné místo na indexech podle kvadratické funkce (vzdálenosti 1, 4, 9, 16...)		3) kvadratický posun - při kolizi hledáme první volné místo na indexech podle kvadratické funkce (vzdálenosti 1, 4, 9, 16...)
		+
	4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi		4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi

−	Uzavřené rozptýlení - přímé adresování	+
		+
		+	== Uzavřené rozptýlení - přímé adresování ==
		+
	metody 2) a 3) nejsou vhodné, vzniká shlukování (clustering), proto je dobré použít způsob 4) nebo lepší hash funkci		metody 2) a 3) nejsou vhodné, vzniká shlukování (clustering), proto je dobré použít způsob 4) nebo lepší hash funkci

−	Tabulky s uzavřeným rozptýlením a vnějším zřetězením	+
		+
		+	== Tabulky s uzavřeným rozptýlením a vnějším zřetězením ==
		+
	= kombinace obou		= kombinace obou
		+
	- adresujeme přímo, při kolizi si ale do tabulky na konec uložíme, kam budeme vnitžně zřetězovat. Hash funkce tedy může být při kolizi (třeba náhodná), nebo tabulku rozdělíme na 2 části, jednu pro vyhledávání klíčů, a druhou pro ukládání synonym. ta už může být dynamicky alokovaná.		- adresujeme přímo, při kolizi si ale do tabulky na konec uložíme, kam budeme vnitžně zřetězovat. Hash funkce tedy může být při kolizi (třeba náhodná), nebo tabulku rozdělíme na 2 části, jednu pro vyhledávání klíčů, a druhou pro ukládání synonym. ta už může být dynamicky alokovaná.

−	Metoda rozptýlených indexů	+
		+
		+	== Metoda rozptýlených indexů ==
		+
	To co bylo v předchozím případě v tabulce vyjmeme, a vytvoříme vedle. Uděláme si mapu synonym (synonyma v seznamu pro každý klíč) a tyto pak ukazují na index do pole.		To co bylo v předchozím případě v tabulce vyjmeme, a vytvoříme vedle. Uděláme si mapu synonym (synonyma v seznamu pro každý klíč) a tyto pak ukazují na index do pole.

−	Vyhledávání	+
		+
		+	== Vyhledávání ==
		+
	Má samozřejmě smysl jen pokud nemáme orákulum (= hashovací fci). Pokud orákulum máme, není třeba hledat protože ideální orákulum vždy ví, kam se podívat pro správná data (The all-knowing Oracle is never surprised. How can she be, she knows everything. -- The Matrix: Revolution), reálné ví aspoň kde hledat.		Má samozřejmě smysl jen pokud nemáme orákulum (= hashovací fci). Pokud orákulum máme, není třeba hledat protože ideální orákulum vždy ví, kam se podívat pro správná data (The all-knowing Oracle is never surprised. How can she be, she knows everything. -- The Matrix: Revolution), reálné ví aspoň kde hledat.

	Jelikož je při přímém adresování orákulum pouhý index do tabulky (mno, to moc orákulum není, orákulum vždy ví, kam jít, aby nebyla kolize), alespoň nám napoví odkud hledat.		Jelikož je při přímém adresování orákulum pouhý index do tabulky (mno, to moc orákulum není, orákulum vždy ví, kam jít, aby nebyla kolize), alespoň nám napoví odkud hledat.

−	Sekvenční:	+
		+	'''Sekvenční:'''
		+
	Hledáme klíč lineárně, pokud na něj narazíme, vrátíme hodnotu		Hledáme klíč lineárně, pokud na něj narazíme, vrátíme hodnotu
		+
	+ snadná implementace		+ snadná implementace
		+
	+ tabulka nemusí být uspořádaná		+ tabulka nemusí být uspořádaná
		+
	- pomalé hledání		- pomalé hledání

−	Binární	+	'''Binární'''
		+
	Jako sekvenční, ale klíče musí být seřazeny, a nad nimi vytvoříme BVS, tedy hledáme vždy v půlce intervalu		Jako sekvenční, ale klíče musí být seřazeny, a nad nimi vytvoříme BVS, tedy hledáme vždy v půlce intervalu
		+
	+ rychlejší (O(log n))		+ rychlejší (O(log n))
		+
	- nutnost udržovat tabulku seřazenou		- nutnost udržovat tabulku seřazenou

−	Fibonacciho	+	'''Fibonacciho'''
		+
	Jako binární, ale nerozdělujeme v polovině, ale podle Fibonacciho posloupnosti (tedy ne 1:1 -> 1:(1:1) -> 1:((1:1): 1) ale (1:1) -> (1:(1:2)) - > (1:((2:3):2))		Jako binární, ale nerozdělujeme v polovině, ale podle Fibonacciho posloupnosti (tedy ne 1:1 -> 1:(1:1) -> 1:((1:1): 1) ale (1:1) -> (1:(1:2)) - > (1:((2:3):2))
		+
	Prvky vybíráme jako dvojice, první z dvojice je ve Fibonacciho posloupnosti na pozici odpovídající úrovni vnožení stromu (výška větve, ve které hledáme)		Prvky vybíráme jako dvojice, první z dvojice je ve Fibonacciho posloupnosti na pozici odpovídající úrovni vnožení stromu (výška větve, ve které hledáme)
		+
	Fibonacciho ppst: a1 = 1, a2 = 1, ai = ai-1 + ai - 2 , tedy 1,1,2,3,5,8,13,21,34,55, ....		Fibonacciho ppst: a1 = 1, a2 = 1, ai = ai-1 + ai - 2 , tedy 1,1,2,3,5,8,13,21,34,55, ....

−	Podle sekundárního klíče	+	'''Podle sekundárního klíče'''
		+
	Jen pouze pokud sekundární klíč existuje v datech, např seznam jmen, jméno je primární (není, ale pro vysvětlení řekněme, že je) a rok je sekundární. Vyhledáme jména v sekundárním klíči a v nich pak hledáme jméno podle primárního klíče.		Jen pouze pokud sekundární klíč existuje v datech, např seznam jmen, jméno je primární (není, ale pro vysvětlení řekněme, že je) a rok je sekundární. Vyhledáme jména v sekundárním klíči a v nich pak hledáme jméno podle primárního klíče.
		+
	Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč		Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč

Tester: Založena nová stránka: To samé jako PPA2 14 a 15, jen doplňky/opakování/upřesnění: Vnitřní zřetězení - synonyma (položky s kolizemi) se ukládají do volných míst Vnější zřet...

2011-08-08T15:08:17Z

Založena nová stránka: To samé jako PPA2 14 a 15, jen doplňky/opakování/upřesnění: Vnitřní zřetězení - synonyma (položky s kolizemi) se ukládají do volných míst Vnější zřet...

Nová stránka

To samé jako PPA2 14 a 15,

jen doplňky/opakování/upřesnění:

Vnitřní zřetězení - synonyma (položky s kolizemi) se ukládají do volných míst
Vnější zřetězení - synonyma se ukládají do seznamů pod klíči

Otevřené rozptýlení - hash funkce
Kolize:
1) nedefinované chování při kolizi - nutno dodefinovat
2) lineární posun - při kolizi vkládáme na první volné místo lineárně (na indexech 1,2,3,4 od původní polohy
3) kvadratický posun - při kolizi hledáme první volné místo na indexech podle kvadratické funkce (vzdálenosti 1, 4, 9, 16...)
4) opakovaný hash - hashovací fci použijeme víckrát pokud dojde ke kolizi

Uzavřené rozptýlení - přímé adresování
metody 2) a 3) nejsou vhodné, vzniká shlukování (clustering), proto je dobré použít způsob 4) nebo lepší hash funkci

Tabulky s uzavřeným rozptýlením a vnějším zřetězením
= kombinace obou
- adresujeme přímo, při kolizi si ale do tabulky na konec uložíme, kam budeme vnitžně zřetězovat. Hash funkce tedy může být při kolizi (třeba náhodná), nebo tabulku rozdělíme na 2 části, jednu pro vyhledávání klíčů, a druhou pro ukládání synonym. ta už může být dynamicky alokovaná.

Metoda rozptýlených indexů
To co bylo v předchozím případě v tabulce vyjmeme, a vytvoříme vedle. Uděláme si mapu synonym (synonyma v seznamu pro každý klíč) a tyto pak ukazují na index do pole.

Vyhledávání
Má samozřejmě smysl jen pokud nemáme orákulum (= hashovací fci). Pokud orákulum máme, není třeba hledat protože ideální orákulum vždy ví, kam se podívat pro správná data (The all-knowing Oracle is never surprised. How can she be, she knows everything. -- The Matrix: Revolution), reálné ví aspoň kde hledat.

Jelikož je při přímém adresování orákulum pouhý index do tabulky (mno, to moc orákulum není, orákulum vždy ví, kam jít, aby nebyla kolize), alespoň nám napoví odkud hledat.

Sekvenční:
Hledáme klíč lineárně, pokud na něj narazíme, vrátíme hodnotu
+ snadná implementace
+ tabulka nemusí být uspořádaná
- pomalé hledání

Binární
Jako sekvenční, ale klíče musí být seřazeny, a nad nimi vytvoříme BVS, tedy hledáme vždy v půlce intervalu
+ rychlejší (O(log n))
- nutnost udržovat tabulku seřazenou

Fibonacciho
Jako binární, ale nerozdělujeme v polovině, ale podle Fibonacciho posloupnosti (tedy ne 1:1 -> 1:(1:1) -> 1:((1:1): 1) ale (1:1) -> (1:(1:2)) - > (1:((2:3):2))
Prvky vybíráme jako dvojice, první z dvojice je ve Fibonacciho posloupnosti na pozici odpovídající úrovni vnožení stromu (výška větve, ve které hledáme)
Fibonacciho ppst: a1 = 1, a2 = 1, ai = ai-1 + ai - 2 , tedy 1,1,2,3,5,8,13,21,34,55, ....

Podle sekundárního klíče
Jen pouze pokud sekundární klíč existuje v datech, např seznam jmen, jméno je primární (není, ale pro vysvětlení řekněme, že je) a rok je sekundární. Vyhledáme jména v sekundárním klíči a v nich pak hledáme jméno podle primárního klíče.
Sekundární klíče máme v seznamu, který obsahuje seznam primárních klíčů zabulky pro každý sekundární klíč