datastruct
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
| datastruct [2013/06/05 15:08] – [Hash tabulka] djbuldog | datastruct [2025/08/28 10:09] (aktuální) – upraveno mimo DokuWiki 127.0.0.1 | ||
|---|---|---|---|
| Řádek 25: | Řádek 25: | ||
| * hashfunc -- hasovaci funkce. chceme aby byla rychla, mela dobre rozprostreni hodnot a minimum kolizi. Univerzalni hash funkce jsou napriklad CRC32 (akcelerovana na Intelu) | * hashfunc -- hasovaci funkce. chceme aby byla rychla, mela dobre rozprostreni hodnot a minimum kolizi. Univerzalni hash funkce jsou napriklad CRC32 (akcelerovana na Intelu) | ||
| * hash_lookup -- dostane klic a musi vratit index do tabulky, kde se klic nachazi. Pro prevod hash na cislo radku se pouziva napriklad modulo poctu radku tabulky (pro staticke tabulky) nebo n-bitu prefixu hashe (dynamicke tabulky) | * hash_lookup -- dostane klic a musi vratit index do tabulky, kde se klic nachazi. Pro prevod hash na cislo radku se pouziva napriklad modulo poctu radku tabulky (pro staticke tabulky) nebo n-bitu prefixu hashe (dynamicke tabulky) | ||
| - | * hash_insert -- vyhleda pomoci lookup klic. pokud nenajde, zalozi novy. pokud najde, mel by overit, ze je skutecne stejne hodnoty. | + | * hash_insert -- vyhleda pomoci lookup klic. pokud nenajde, zalozi novy na radku s indexem z lookup. pokud najde, mel by overit, ze je skutecne stejne hodnoty. |
| * radek tabulky vetsinou obsahuje kapsu, kam se davaji stejne hash hodnoty (kolize). Pouziva se zde linearne zretezeny seznam | * radek tabulky vetsinou obsahuje kapsu, kam se davaji stejne hash hodnoty (kolize). Pouziva se zde linearne zretezeny seznam | ||
datastruct.1370437722.txt.gz · Poslední úprava: (upraveno mimo DokuWiki)