Knihovna pro stromy v C

[Dalibor Straka]

On Tue, Sep 11, 2007 at 04:40:08PM +0200, Jan Kasprzak wrote:
> Dalibor Straka wrote:
> : A coz udelat hash. S tabuli 2^24 (8MB) budete mit malo kolizi,
> 
Jeste chybka 2^24 je samozrejme 16MB.

> 	Praveze pro 24-bitove klice budu mit podle narozeninoveho
> paradoxu docela dost kolizi.
> 

Spatne jsem se vyjadril kolizi bude dost, ale nebudou zdrzovat. Zajimavy
je ocekavany cas pro vyhledani klice pri jednoduchem hashovani O(1 + a)
a ocekavany cas pro neuspesne vyhledani. Kde "a" je prumerna delka
retizku v prihradce. Coz je a = n/m = 2^(pocet ruznych klicu)/2^(pocet
prihradek).

Jestli budete mit 24bit cisla, nebudou kolize zadne a rychlost metody
bude zarucene O(1).

-- Dalibor Straka