Z akých komponentov sa skladá hash tabuľka?

Hash tabuľa sa skladá zo dvoch hlavných komponentov:

1. Pole (alebo zoznam) buniek (kbelíkov): Toto je hlavná štruktúra na ukladanie. Každá bunka môže obsahovať jeden alebo viac prvkov dát (párov kľúč-hodnota).

2. Hashovacia funkcia: Algoritmus, ktorý transformuje vstupný kľúč na číselný index, ktorý sa používa na určenie bunky, kde má byť uložený alebo nájdený príslušný prvok dát.

Okrem toho sa na riešenie kolízií (situácií, keď rôzne kľúče hashujú na rovnaký index) používajú mechanizmy ako:

• Metóda reťazenia: V každej bunke sa uchováva zoznam (napríklad spojený zoznam) prvkov, ktoré boli hashované do tohto indexu.
• Metóda otvoreného adresovania: Pri kolízii algoritmus hľadá nasledujúcu voľnú bunku podľa určitej stratégie (lineárne sondovanie, kvadratické sondovanie, dvojité hashovanie).

# Príklad jednoduchej hashovacej funkcie
def simple_hash(kľúč, veľkosť_polia):
    # Transformácia kľúča na číslo
    if isinstance(kľúč, str):
        hodnota_hash = sum(ord(znak) for znak in kľúč)
    elif isinstance(kľúč, int):
        hodnota_hash = kľúč
    else:
        raise TypeError("Nepodporovaný typ kľúča")

    # Vrátenie indexu v rámci veľkosti poľa
    return hodnota_hash % veľkosť_polia

# Príklad komponentu poľa buniek pre metódu reťazenia
class HashTable:
    def __init__(self, veľkosť):
        self.veľkosť = veľkosť
        self.array = [[] for _ in range(self.veľkosť)] # Pole zoznamov (reťazce)

    def vlož(self, kľúč, hodnota):
        index = simple_hash(kľúč, self.veľkosť)
        self.array[index].append((kľúč, hodnota)) # Pridanie páru kľúč-hodnota do zoznamu

    def hľadaj(self, kľúč):
        index = simple_hash(kľúč, self.veľkosť)
        for k, v in self.array[index]:
            if k == kľúč:
                return v
        return None # Kľúč nenájdený