Tabella Hash

Le tabelle hash sono strutture dati che sfruttano le caratteristiche degli algoritmi di hash e mescolano strutture dati come gli array e le liste.

Sostanzialmente si impiega un array di N elementi. Quando un oggetto a deve essere inserito, si calcola il suo codice hash. Tramite una qualche procedura, si fa corrispondere questo codice ad una posizione dell'array, ovvero ad un numero nell'intervallo (0, N-1). Il numero diventa la posizione dell'oggetto. In questo modo è molto veloce la ricerca di un oggetto. Essa procede calcolando il codice hash e ricostruendo la sua posizione.

A volte il numero degli oggetti è superiore a N, oppure non è garantito che la procedura per assegnare un numero (0, N-1) generi un numero unico per ogni codice hash. Infatti un algoritmo di hash produce un numero totale di codici diversi in genere molto superiore a N. Quindi è necessario gestire il caso in cui un oggetto debba essere inserito in una posizione già occupata da un altro oggetto.

Se gli oggetti sono pochi rispetto alle posizioni N disponibili, si può determinare una nuova posizione in questo modo: sia n la posizione di un oggetto che è stata già occupata. Allora si controlla la posizione n+n; se è superiore al numero totale di posizioni N allora si calcola il modulo: 2n mod N. Se questa posizione è occupata si procede nuovamente calcolando 3n mod N.

Alternativamente si può inserire l'oggetto nella prima posizione disponibile successiva a quella corrispondente al codice hash.

La soluzione consiste nel concatenare gli oggetti che devono essere inseriti nella stessa locazione dell'array in una lista. L'array deve quindi essere modificato per contenere il puntatore ad una lista. La ricerca di un elemento viene penalizzata, ma non di molto. L'algoritmo di ricerca calcola il codice hash dell'oggetto da trovare, ricava la locazione e scorre la lista. La ricerca in una lista è lenta, poiché impiega O(n), ma se gli oggetti sono distribuiti in modo uniforme, il peggioramento delle prestazioni non è considerevole. Dati M oggetti e un array con N elementi, se essi sono distribuiti in modo uniforme, la ricerca di un oggetto si riduce al calcolo di un codice hash (complessità costante O(1)) e lo scorrimento di una lista di M/N elementi.

Implementazione

Nell'implementazione di una tabella di hash è necessario scegliere un algoritmo che generi codici hash e determinare un metodo per far corrispondere ad un hash una posizione dell'array. Inoltre, nelle implementazioni gli oggetti sono contenuti in una struttura dove è presente una chiave e un valore. Il valore corrisponde all'oggetto, mentre la chiave è una sorta di etichetta a cui corrisponde l'oggetto. Se si sceglie questo tipo di implementazione, viene calcolato l'hash della chiave e non dell'oggetto.

class HashTableNode
{
    HashTableNode next;
 
    public HashTableNode Next
    {
        get { return next; }
        set { next = value; }
    }
 
    object data;
 
    public object Data
    {
        get { return data; }
    }
 
    string key;
 
    public string Key
    {
        get { return key; }
        set { key = value; }
    }
 
    public HashTableNode(string k, object o)
    {
        key = k;
        data = o;
    }
 
}

In .NET la classe object è presente il metodo GetHashCode. Nei tipi personalizzati è possibile re-implementare questo metodo per generare un codice hash. Una semplice funzione che trasforma il codice hash (in .NET è un tipo int a 32 bit) in un numero corrispondente ad una posizione è il modulo. Quindi una implementazione semplice può essere la seguente:

class HashTable
{
    HashTableNode[] data;
 
    public HashTable(int size)
    {
        data = new HashTableNode[size];
    }
 
    public void AddNode(HashTableNode node)
    {
        int h = node.Key.GetHashCode();
        int position = h % data.Length;
 
        position = Math.Abs(position);
 
        if (data[position] != null)
        {
            // posizione occupata, vado in fondo alla lista
            HashTableNode n = data[position];
 
            while (n.Next != null)
                n = n.Next;
 
            n.Next = node;
        }
        else
        {
            // la posizione non è occupata
            data[position] = node;
        }
    }
 
    public HashTableNode GetNode(string k)
    {
        int h = k.GetHashCode();
        int position = h % data.Length;
 
        position = Math.Abs(position);
 
        if (data[position] != null)
        {
            HashTableNode n = data[position];
 
            while (n != null && n.Key != k)
                n = n.Next;
 
            return n;
        }
        else
            return null;    
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License