Rozptylové tabulky s s vnějším řetězením - Historie editací

212.158.144.250 v 13. 6. 2014, 06:34

2014-06-13T06:34:44Z

← Starší verze		Verze z 13. 6. 2014, 06:34
Řádka 31:		Řádka 31:
	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.		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.

−	Mohli bychom použít i ~~kdyptografické~~ hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.	+	Mohli bychom použít i kryptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
	[[Kategorie:fav-kiv-bzinf]]		[[Kategorie:fav-kiv-bzinf]]

212.158.144.250: Přidání informací o rozšířené rozptylovací funkci

2014-06-13T06:34:16Z

Přidání informací o rozšířené rozptylovací funkci

← Starší verze		Verze z 13. 6. 2014, 06:34
Řádka 28:		Řádka 28:
	Vlastnost 1: na toto číslo použijeme operaci modulo. Tato operace je pomalá (jde o dělení), použijeme tedy ideálně velikosti tabulky, které jsou mocninou 2, a po té je dělení pouhým bitovým posunem		Vlastnost 1: na toto číslo použijeme operaci modulo. Tato operace je pomalá (jde o dělení), použijeme tedy ideálně velikosti tabulky, které jsou mocninou 2, a po té je dělení pouhým bitovým posunem
	Vlastnost 2: vazby v tomto postupu existují (například anagramy se namapují do stejného pole). Použijeme tedy například následující postup: (( (1. písmeno * (2k+1) ) + 2. písmeno) * (2k+1)) + ... Tím zrušíme vazby mezi podobnými slovy. (2k+1) použijeme, protože jde o bitový posun a přičtení 1, což je velmi rychlé a 1 přičítáme, protože by poté modulo ztratilo význam.		Vlastnost 2: vazby v tomto postupu existují (například anagramy se namapují do stejného pole). Použijeme tedy například následující postup: (( (1. písmeno * (2k+1) ) + 2. písmeno) * (2k+1)) + ... Tím zrušíme vazby mezi podobnými slovy. (2k+1) použijeme, protože jde o bitový posun a přičtení 1, což je velmi rychlé a 1 přičítáme, protože by poté modulo ztratilo význam.
		+
		+	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.

	Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.		Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.

Acolade: kategorizace

2014-02-20T06:35:51Z

kategorizace

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

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester v 30. 8. 2011, 16:45

2011-08-30T16:45:32Z

← Starší verze		Verze z 30. 8. 2011, 16:45
Řádka 30:		Řádka 30:

	Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.		Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.
		+
		+	{{fav-kiv-bzinf}}

Tester v 10. 8. 2011, 09:26

2011-08-10T09:26:36Z

← Starší verze		Verze z 10. 8. 2011, 09:26
Řádka 1:		Řádka 1:
	HASH		HASH
	Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento přístup je nemožné používat přímé adresování, jelikož by docházelo ke kolizím.		Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento přístup je nemožné používat přímé adresování, jelikož by docházelo ke kolizím.
		+
		+	[[Soubor:Rozptylova-tabulka.jpg]]

	Můžeme ale v poli využít prázdná místa a do nich duplicitní hodnoty ukládat. Vyhladávání a ukládání potom obecně nebude v konstantním čase. Můžeme tedy například uložit duplicitní hodnotu do následujícího prázdného místa v tabulce. Problémy jsou však následující:		Můžeme ale v poli využít prázdná místa a do nich duplicitní hodnoty ukládat. Vyhladávání a ukládání potom obecně nebude v konstantním čase. Můžeme tedy například uložit duplicitní hodnotu do následujícího prázdného místa v tabulce. Problémy jsou však následující:

Tester: Založena nová stránka: HASH Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento pří...

2011-08-08T15:02:37Z

Založena nová stránka: HASH Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento pří...

Nová stránka

HASH
Pokud máme množinu záznamů, ve které mohou v klíčích existovat duplicity pro různé hodnoty (například tabulka slov podle prvího písmena). Pro tento přístup je nemožné používat přímé adresování, jelikož by docházelo ke kolizím.

Můžeme ale v poli využít prázdná místa a do nich duplicitní hodnoty ukládat. Vyhladávání a ukládání potom obecně nebude v konstantním čase. Můžeme tedy například uložit duplicitní hodnotu do následujícího prázdného místa v tabulce. Problémy jsou však následující:

Můžeme zabrat místo pro klíč, který má na toto místo právoplatný nárok (kolize tedy nastanou nejen pro hodnoty se stejným klíčem, ale i obecně pro libovolný klíč)
Odsuneme-li i tento klíč, dojde k vytváření shluků (a nabalovíní dalších klíču na tyto shluky, na obr. skluk od písmene A)
Dochází také k fragmentaci, je tedy nutné hledat až do prvního prázdného klíče, což je při shlukování a vyšší saturaci tabulky pomalé

Tento přístup tedy použijeme, pokud vímě, že jsou klíče hodnot rovnoměrně rozmístěny, a že hodnot není více než klíčů, a nazývá se vnitřní zřetězení.

Vnější zřetězení znamená, že ke kažnému klíči přiřadíme seznam hodnot. Nedochází tedy ke kolizím, ale vyhledání hodnoty je O(m), kde m je počet hodnot ke každému klíči, tedy nejhůže O(n) (všechny hodnoty jsou v jednom klíči). Tento způsob však zvládá i situace, kde je více hodnot než klíčů

Rozptýlení klíčů.

Pro vnitřní zřetezení lze použít lepší vyhledáváci (a ukládací) funkci, než lineární posun, třeba kvadratickou fci. Kvadratická funkce se může protonout s jinou kv. fcí s jiným počátkem jen jednou) Tím omezíme clustery a kolize, a ukládání a hledání je rychlejší.

Pro vnější zřetezení, nebo pokud je při vnitřním zřetězení mnoho podobných klíčů, je vhodné použít orákulum, rozptylovou (hashovací) funkci. Ta má 2 vlastnosti:

Namapuje hodnoty do rozsahu počtu klíčů
Ideálně zruší nebo alespoň naruší vztahy mezi podobnými klíči

Příklad: Slovník se vnitřním zřetězením. Slovo převedeme na číslo součtem ASCII hodnot znaků

Vlastnost 1: na toto číslo použijeme operaci modulo. Tato operace je pomalá (jde o dělení), použijeme tedy ideálně velikosti tabulky, které jsou mocninou 2, a po té je dělení pouhým bitovým posunem
Vlastnost 2: vazby v tomto postupu existují (například anagramy se namapují do stejného pole). Použijeme tedy například následující postup: (( (1. písmeno * (2k+1) ) + 2. písmeno) * (2k+1)) + ... Tím zrušíme vazby mezi podobnými slovy. (2k+1) použijeme, protože jde o bitový posun a přičtení 1, což je velmi rychlé a 1 přičítáme, protože by poté modulo ztratilo význam.

Mohli bychom použít i kdyptografické hashování, jako MD5, to je však pro O(1) přístup k seznamům příliš pomalé.