Z jakých komponent se skládá hash tabulka?

Hashtabul se skládá ze dvou hlavních komponent:

1. Pole (nebo seznam) buněk (kbelíků): Jedná se o hlavní strukturu pro ukládání. Každá buňka může obsahovat jeden nebo více datových prvků (páry klíč-hodnota).

2. Hashovací funkce: Algoritmus, který převádí vstupní klíč na číselný index, který se používá k určení buňky, kde má být uložen nebo nalezen odpovídající datový prvek.

Kromě toho se pro řešení kolizí (situací, kdy různé klíče jsou hashovány na stejný index) používají mechanismy jako:

• Metoda řetězení: V každé buňce je uložena seznam (například spojový seznam) prvků, které byly hashovány na tento index.
• Metoda otevřeného adresování: Při kolizi algoritmus hledá následující volnou buňku podle určité strategie (lineární sondování, kvadratické sondování, dvojité hashování).

# Příklad jednoduché hashovací funkce
def simple_hash(klic, velikost_pole):
    # Převod klíče na číslo
    if isinstance(klic, str):
        hash_hodnota = sum(ord(znak) for znak in klic)
    elif isinstance(klic, int):
        hash_hodnota = klic
    else:
        raise TypeError("Nepodporovaný typ klíče")

    # Vrácení indexu v rámci velikosti pole
    return hash_hodnota % velikost_pole

# Příklad komponenty pole buněk pro metodu řetězení
class HashTable:
    def __init__(self, velikost):
        self.velikost = velikost
        self.array = [[] for _ in range(self.velikost)] # Pole seznamů (řetězce)

    def vloz(self, klic, hodnota):
        index = simple_hash(klic, self.velikost)
        self.array[index].append((klic, hodnota)) # Přidání páru klíč-hodnota do seznamu

    def najdi(self, klic):
        index = simple_hash(klic, self.velikost)
        for k, v in self.array[index]:
            if k == klic:
                return v
        return None # Klíč nenalezen