Nekolik dotazu

[Vilem Vychodil]

On Mon, Aug 16, 1999 at 11:30:24AM +0200, Pavel Smerk wrote:
> - Co jsou to rozptylene tabulky, pomoci nichz jsou implementovany hashe
> a ktere zustavaji stejne rychle nezavisle na poctu vlozenych hodnot, jak
> na strane 8 pravi Programovani v jazyce Perl (v originale je ten vyznam
> myslim jiny, ale stejne)?

	Zdravim,
	
	v podstate jde o tabulky, ktere nejsou adresovany primo, nybrz
existuje nejaka deterministicka hashovaci funkce, ktera je schopna
pro kazdy klic (a zadany pokus) stanovit index (slot) do teto tabulky.
Tim padem se mohou nahashovat klice z pomerne velkeho univerza (treba retezce)
do tabulky omezene delky.

	V praxi to vypada zhruba tak, ze pri vkladani se urci slot v tabulce,
pokud je jiz zaplneny, tak se to bud resi zretezenim (pomale), nebo se
hashuje tak dlouho, dokud se nenarazi na volny slot (jelikoz je funkce
deterministicka, tak se nalezne vzdy stejny). V takove situaci lze
zhruba rict, ze vyhledavani `je nezavisle na poctu vlozenych hodnot'.
Ono to tak idealni neni, kdyz je tabulka prilis zaplnena, tak se doba
vyhledavani prodluzuje, ale pokud je zaplneni rozumne, da se rict, ze
vse probehne v konstantnim case.


	S pozdravem,
							Vilem Vychodil