Milyen összetevőkből áll egy hash-tábla?

Egy hash-tábla két fő összetevőből áll:

1. Tömb (vagy lista) cellákból (kádak): Ez a fő tárolási struktúra. Minden cella egy vagy több adat elemet tartalmazhat (kulcs-érték párok).

2. Hash függvény: Olyan algoritmus, amely a bemeneti kulcsot numerikus indexre alakítja, amit a megfelelő adat elem tárolására vagy megtalálására használnak.

Ezenkívül a kollíziók (amikor különböző kulcsok ugyanarra az indexre hash-ölődnek) megoldására olyan mechanizmusokat alkalmaznak, mint:

• Láncolási módszer: Minden cellában egy lista (pl. összekapcsolt lista) tárolódik az adott indexhez hash-ölt elemekből.
• Nyitott címzés: Kollízió esetén az algoritmus a következő szabad cellát keresi egy meghatározott stratégia szerint (lineáris szondázás, kvadratikus szondázás, dupla hash-elés).

# Egyszerű hash függvény példája
def simple_hash(kulcs, tomb_meret):
    # A kulcs átalakítása számra
    if isinstance(kulcs, str):
        hash_ertek = sum(ord(karakter) for karakter in kulcs)
    elif isinstance(kulcs, int):
        hash_ertek = kulcs
    else:
        raise TypeError("Nem támogatott kulcs típus")

    # Visszatérés a tömb méretén belüli indexhez
    return hash_ertek % tomb_meret

# Példa a láncolási módszerhez tartozó cella komponensre
class HashTable:
    def __init__(self, meret):
        self.meret = meret
        self.array = [[] for _ in range(self.meret)] # Lista tömb (láncok)

    def beszúr(self, kulcs, ertek):
        index = simple_hash(kulcs, self.meret)
        self.array[index].append((kulcs, ertek)) # Pár hozzáadása a listához

    def keres(self, kulcs):
        index = simple_hash(kulcs, self.meret)
        for k, v in self.array[index]:
            if k == kulcs:
                return v
        return None # Kulcs nem található