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

• 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