Hašovací tabulky

Témata

• Hašovací tabulky
• Metody řešení kolizí
• Druhý zápočtový úkol (více informací zde)

Organizační

• Příští týden (22.4.2025) nás čeká druhá písemka.
• Obsahovat bude vše od AVL po hašovací tabulky.
• Dnešní úkol je druhá část zápočtového úkolu.

Průběh cvičení

• prošli jsme principy schované za hašovacími tabulkami:
  • hašovací funkce
  • kolize
  • řetězení
  • otevřené adresování
  • mazání při řešení kolizí otevřeným adresováním
• zadali jsme si druhou část domácího úkolu (viz níže)

Úkoly pro cvičení v C

Zde máte soubor s daty pro úkol. Každý řádek obsahuje jedno slovo a jedno číslo.
Napište program v jazyce C, který:

1. Definuje typ Row pro data z jednoho řádku a procedury
   int row_number(Row*) a
   char* row_word(Row*)
   vracející odpovídající složky struktury reprezentující data řádku.
2. Obsahuje proceduru
   Row* create_database(char* file_path)
   načítající obsah dodaného souboru uloženého v cestě file_path do pole struktur Row. Pole bude obsahovat data ve stejném pořadí, v jakém byly řádky v souboru.
   Toto je naivní databáze.
3. Obsahuje procedury pro vyhledávání v databázi:
   • Row* naive_search_by_number(Row database[], int database_size, int number)
     vyhledávající záznam s číselnou složkou rovnou number. Procedura vrátí odkaz na řádek, nebo NULL (0) pokud takový řádek neexistuje. Zároveň na standardní výstup vypíše, kolik řádků zkontrolovala než skončila a mezeru.
   • Row* naive_search_by_word(Row database[], int database_size, char* word)
     vyhledávající záznam s textovou složkou rovnou word. Procedura vrátí odkaz na řádek, nebo NULL (0) pokud takový řádek neexistuje. Zároveň na standardní výstup vypíše, kolik řádků zkontrolovala než skončila a mezeru.

Dále si vyberte jeden z následujících podúkolů (B-stromy nebo hašování):

• B-stromy:

1. Naprogramujte typ B_tree pro B-strom, který bude ukládat odkazy na řádky (Row*) a bude je řadit pomocí číselné části řádku. Tj. uzel bude obsahovat čísla z řádků spolu s odkazy na celé řádky, přičemž ve stromě budou tato data ukládána podle číselné části. Strom neobsahuje samotné řádky, jen ukazatele na ně a číselné části pro uspořádání dat.
2. Naprogramujte proceduru
   B_tree* create_b_tree_index(Row database[], int database_size)
   vytvářející tzv. index nad číselnou složkou naší databáze database z první části úkolu. Tj. tento strom umožní rychlý přístup k jednotlivým řádkům naší databáze na základě číselné části řádku.
3. Naprogramujte proceduru
   Row* b_tree_search(B_tree tree, int number)
   vyhledávající záznam s číselnou složkou rovnou number. Procedura vrátí odkaz na řádek nebo NULL (0) pokud takový řádek neexistuje. Zároveň na standardní výstup vypíše, kolik čísel ve stromě zkontrolovala než skončila a mezeru.

• Hašování:

1. Naprogramujte typ Hash_table pro Hašovací tabulku s řešením kolizí otevřeným adresováním, která bude pomocí haše ukládat textové částí řádků a odkazy na celé řádky (Row*). Tabulka neobsahuje samotné řádky, jen ukazatele na ně a textové částí pro porovnání s hledanou hodnotou.
2. Naprogramujte proceduru
   Hash_table* create_hash_table_index(Row database[], int database_size)
   vytvářející tzv. index nad textovou složkou naši databáze database z první části úkolu. Tj. tato tabulka umožní rychlý přístup k jednotlivým řádkům naší databáze na základě haše textové části řádku.
3. Naprogramujte proceduru
   Row* hash_search(Hash_table table, char* word)
   vyhledávající záznam s textovou složkou rovnou word. Procedura vrátí odkaz na řádek, nebo NULL (0) pokud takový řádek neexistuje. Zároveň na standardní výstup vypíše, kolik pozic v hašovací tabulce zkontrolovala než skončila a mezeru.

Poznámka:
Pro vybranou možnost budete muset implementovat alespoň:

• vytváření prázdné datové struktury (tabulky/stromu),
• přidávání do dané datové struktury,
• vyhledávání v dané datové struktuře s počítáním porovnání.

Poté už bude implementace požadovaných procedur jen přímočaré použití těchto možností.

Něco navíc:

• Indexy jsou ve skutečných databázích hojně využívány.
• Mezi nejčastěji používané indexy patří právě ty využívající hašování nebo varianty B-stromů (viz např. dokumentaci k indexům v PostgreSQL).
• V tomto úkolu je několik věcí dost zjednodušených (například neřešíme mazání a úpravy dat, duplicity, atd.).
• Více zjistíte v kurzech o databázích.

Úkoly pro cvičení v Pythonu

Vyberte si jeden z následujících úkolů:

1. Naprogramujte B-stromy dle minulého zadání.
2. Naprogramujte hašovací tabulku s řešením kolizí otevřeným adresováním.
   • implementujte vyhledávání v tabulce, které vrátí počet zkontrolovaných políček a True pokud hodnota v tabulce je nebo False, pokud tam není.
   • implementujte vkládání do tabulky vracející počet zkontrolovaných políček True, pokud vložení uspělo a False jinak.
   • implementujte mazání z tabulky vracející počet zkontrolovaných políček True, pokud ke smazání došlo a False jinak.