Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- datastruct [2013/06/05 11:34] – vytvořeno djbuldog
+++ datastruct [2025/08/28 10:09] (aktuální) – upraveno mimo DokuWiki 127.0.0.1
@@ Řádek 3: / Řádek 3: @@
 Obecne pouzitelne datove stuktury pro rychle vyhledavani, ukladani, dynamickou alokaci pameti
+  * pole s pevnou delkou pro male mnozstvi hodnot
+    * nejrychlejsi vyhledavani, prostorove narocne, nevyuzite misto
   * dynamicke pole
     * lepsi alokovat po vecich celcich
+  * zretezeny seznam
+    * jednosmerne/obousmerne
   * slovnik/indexovani
     * pomocna struktura pro zmenseni prohledavane domeny
@@ Řádek 11: / Řádek 15: @@
     * pri kolizi znovu hash
     * index napriklad podle prvnich n-bitu
+===== Hash tabulka =====
+  * chceme efektivne vyuzivat alkovane misto
+  * chceme vyhledavat zaznamy s konstantni slozitosti
+Implementace:
+  * 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_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
+  * pokud vypocitame hash a zjistime, ze hodnota je jina nez u jiz ulozenho, muzeme hash znovu zahashovat a dostat tak novou hodnotu pro ulozeni