====== Datove struktury ======

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
  * vyhledavaci strom
  * hash tabulka, hash funkce
    * 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