Din ce componente este format un tabel hash?

O tabela hash constă din două componente principale:

1. Array (sau listă) de celule (buckets): Aceasta este structura principală de stocare. Fiecare celulă poate conține unul sau mai multe elemente de date (perechi cheie-valoare).

2. Funcție hash: Algoritmul care transformă cheia de intrare într-un indice numeric, utilizat pentru a determina celula în care trebuie să fie stocat sau găsit elementul de date corespunzător.

De asemenea, pentru rezolvarea coliziunilor (situații în care diferite chei sunt hash-uite în același indice), se folosesc mecanisme precum:

• Metoda de lanț: În fiecare celulă se stochează o listă (de exemplu, o listă înlănțuită) de elemente hash-uite în acel indice.
• Metoda de adresare deschisă: În cazul unei coliziuni, algoritmul caută următoarea celulă liberă urmând o strategie definită (sondare liniară, sondare pătratică, dublu hash).

# Exemplu de funcție hash simplă
def simple_hash(cheie, dimensiune_array):
    # Transformarea cheii în număr
    if isinstance(cheie, str):
        valoare_hash = sum(ord(caracter) for caracter in cheie)
    elif isinstance(cheie, int):
        valoare_hash = cheie
    else:
        raise TypeError("Tip de cheie nesuportat")

    # Returnarea indicelui în limitele dimensiunii array-ului
    return valoare_hash % dimensiune_array

# Exemplu de componentă a array-ului de celule pentru metoda de lanț
class HashTable:
    def __init__(self, dimensiune):
        self.dimensiune = dimensiune
        self.array = [[] for _ in range(self.dimensiune)] # Array de liste (lanțuri)

    def insert(self, cheie, valoare):
        indice = simple_hash(cheie, self.dimensiune)
        self.array[indice].append((cheie, valoare)) # Adăugarea perechii cheie-valoare în listă

    def search(self, cheie):
        indice = simple_hash(cheie, self.dimensiune)
        for k, v in self.array[indice]:
            if k == cheie:
                return v
        return None # Cheie negăsită