Una funzione di hashing non e' altro che una funzione che traspone un dato di qualche tipo in un numero (potrebbe non essere un numero, ma qui semplifico) 'relativamente' piccolo, creando una sorta di 'impronta digitale'. E' una funzione one-way nel senso che dal dato si puo' derivare il valore numerico, ma non viceversa. Per questo motivo si presta particolarmente bene per il mondo della security e delle basi dati.

Il problema principale delle funzioni di hashing e' rappresentato dalle collisioni. Dato che i dati di input hanno potenzialmente un numero di combinazioni superiore al numero finito di hash possibili, non e' raro il caso in cui piu' dati di input corrispondano lo stesso hash, da cui nasce appunto una collisione.

Il framework .NET fornisce un metodo per calcolare l'hash dell'oggetto, GetHashCode(). Ovviamente si tratta di un metodo virtuale, e quindi ogni tipo puo' implementarsi il proprio algoritmo di hashing. Ma quanto e' buono questo algoritmo. Dipende dal tipo e dal numero di elementi da prendere in considerazione. Vediamo un esempio banale:

HashSet<int> set = new HashSet<int>();

for (int i = 0; i < 100000; i++) {
    bool added = set.Add(Guid.NewGuid().GetHashCode());
    if (!added) {
        Console.WriteLine("Trovato un duplicato!");
    }
}

Se eseguite il codice di cui sopra e' molto probabile che troviate delle collisioni. Nei miei esperimenti ne ho trovati da 1 a 4 ad ogni esecuzione. Se riducessi il numero di cicli (ad esempio di un ordine di grandezza), non avrei piu' collisioni. Dato che non posso ridurre il numero di cicli debbo trovare una soluzione alternativa.

Fra gli algoritmi piu' promettenti troviamo quelli legati al mondo della security, come SHAx e MD5. Il vantaggio di questi algoritmi e' che hanno una dispersione decisamente elevata e quindi una probabilita' di collisione molto bassa. Lo svantaggio e' che richiedono molte computazioni e quindi sono lenti nei contesti in cui le prestazioni sono fondamentali.

Fra le alternative piu' promettenti debbo citare l'algoritmo di Glenn Fowler, Landon Noll e Phong Vo (http://isthe.com/chongo/tech/comp/fnv/) i quali hanno trovato una funzione di hashing decisamente performante e semplice. Rimando al sito ufficale per la discussione teorica e proseguo con l'implementazione. Dato che debbo estendere una funzionalita' del tipo Guid, faccio uso di un extension method (senza cambiare l'algoritmo per il momento):

public static class HashFuction {
    public static long ComputeHashCode(this Guid guid) {
        return guid.GetHashCode();
    }
}

e modifico la chiamata

for (int i = 0; i < 100000; i++) {
    bool added = set.Add(Guid.NewGuid().ComputeHashCode());
    if (!added) {
        Console.WriteLine("Trovato un duplicato!");
    }
}

Eseguendo il codice avro' le stesse collisioni di prima. A questo punto implemento l'algoritmo FNV-1a:

public static class HashFuction
{
    public static long ComputeHashCode(this Guid guid)
    {
        return fnv(guid.ToByteArray());
    }

    private static long fnv(byte[] buf)
    {
        long hash = FNV_offset_basis;
        for (int i = 0; i < buf.Length; i++)
        {
            hash ^= buf[i];
            hash *= FNV_prime;
        }
        return hash;
    }

    private const long FNV_prime = 16777619;
    private const long FNV_offset_basis = 2166136261;
}

Rieseguo i test e non ottengo alcuna collisione. Aumento il numero di cicli di un ordine di grandezza e niente. Eseguendo 10.000.000 di cicli non ho trovato alcun duplicato. E' probabile che aumentando il numero di cicli si trovi un qualche duplicato, in tal caso bastera' usare un altro numero primo ed un altro offset come descritto nel sito.

Dove sta il segreto? Fondamentalmente nella scelta dei numeri primi. Ho fatto alcune ricerche e non ho trovato alcun riferimento teorico, pertanto piu' che numeri primi dovrei parlare di numeri magici :-)