Di quali componenti è composta una tabella hash?

Una tabella hash è composta da due componenti principali:

1. Array (o lista) di celle (bucket): È la struttura principale di memorizzazione. Ogni cella può contenere uno o più elementi di dati (coppie chiave-valore).

2. Funzione hash: Algoritmo che trasforma la chiave di input in un indice numerico, utilizzato per determinare la cella in cui deve essere salvato o trovato l'elemento di dati corrispondente.

Inoltre, per risolvere le collisioni (situazioni in cui chiavi diverse vengono hashate nello stesso indice), si utilizzano meccanismi come:

• Metodo di chaining: In ogni cella viene memorizzata una lista (ad esempio, una lista collegata) di elementi hashati in quell'indice.
• Metodo di open addressing: In caso di collisione, l'algoritmo cerca la prossima cella libera seguendo una strategia definita (sondaggio lineare, sondaggio quadratico, doppio hashing).

# Esempio di funzione hash semplice
def simple_hash(chiave, dimensione_array):
    # Trasformazione della chiave in un numero
    if isinstance(chiave, str):
        valore_hash = sum(ord(carattere) for carattere in chiave)
    elif isinstance(chiave, int):
        valore_hash = chiave
    else:
        raise TypeError("Tipo di chiave non supportato")

    # Restituisce l'indice entro la dimensione dell'array
    return valore_hash % dimensione_array

# Esempio di componente di array di celle per metodo di chaining
class HashTable:
    def __init__(self, dimensione):
        self.dimensione = dimensione
        self.array = [[] for _ in range(self.dimensione)] # Array di liste (catene)

    def inserisci(self, chiave, valore):
        indice = simple_hash(chiave, self.dimensione)
        self.array[indice].append((chiave, valore)) # Aggiunta della coppia chiave-valore alla lista

    def cerca(self, chiave):
        indice = simple_hash(chiave, self.dimensione)
        for k, v in self.array[indice]:
            if k == chiave:
                return v
        return None # Chiave non trovata