Cvičení 11

Téma

• hashování
• řešení kolizí řetězením
• otevřené adresování

Úkoly

1. Implementujte struktury a následující funkcionalitu pro hashovací tabulky nad řetězci s řešením kolizí řetězením. Vše navrhněte tak, aby se Vaše tabulka dala použít s následujícím API:
   • chaining_table* create_chaining_table(int size, int (*hash)(char*));
   • int add_ct(char* data, chaining_table* table);
   • int remove_ct(char* data, chaining_table* table);
   • int contains_ct(char* data, chaining_table* table);
   Druhý parametr procedury create_chaining_table je ukazatel na hashovací funkci. Poslední tři procedury budou vracet 1 při úspěchu (provedení požadované operace) a 0 jinak (nenalezeno, nepřidáno, nelze smazat atd.). Hashovací funkcí pro řetězce si zvolte sami dle přednášek.
2. Implementujte struktury a následující funkcionalitu pro hashovací tabulky nad řetězci s řešením kolizí otevřeným adresováním. Vše navrhněte tak, aby se Vaše tabulka dala použít s následujícím API:
   • oa_table* create_oa_table(int size, int (*hash)(char*), int (*probe)(int, int));
   • int add_oat(char* data, oa_table* table);
   • int remove_oat(char* data, oa_table* table);
   • int contains_oat(char* data, oa_table* table);
   Druhý parametr procedury create_oa_table je ukazatel na hashovací funkci a třetí ukazatel na průzkumnou funkci. Poslední tři procedury budou vracet 1 při úspěchu (provedení požadované operace) a 0 jinak (nenalezeno, nepřidáno, nelze smazat atd.). Hashovací funkcí pro řetězce si zvolte dle přednášek.
3. Napište main s ukázkami použití implementací. U otevřeného adresování ukažte použití na tabulkách s lineární a kvadratickou průzkumnou funkcí.
4. (*) Zkuste si otevřené adresování s bilineární průzkumnou funkcí. Tj budete muset zobecnit strukturu pro oa_table tak, abyste ji mohli předat dvě hashovací funkce.