È possibile combinare i codici hash per i membri privati ​​per generare un nuovo codice hash?

Question

Ho un oggetto per il quale voglio generare un hash univoco (override GetHashCode()) ma voglio evitare overflow o qualcosa di imprevedibile.

Il codice dovrebbe essere il risultato della combinazione dei codici hash di una piccola raccolta di stringhe.

I codici hash faranno parte della generazione di una chiave di cache, quindi idealmente dovrebbero essere univoci, tuttavia il numero di possibili valori sottoposti ad hashing è piccolo, quindi PENSO che la probabilità sia a mio favore qui.

Qualcosa del genere sarebbe sufficiente E esiste un modo migliore per farlo?

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

MODIFICARE:Grazie per le risposte finora.@Jon Skeet:No, l'ordine non è importante

Immagino che questa sia quasi un'altra domanda, ma dal momento che sto utilizzando il risultato per generare una chiave di cache (stringa), avrebbe senso utilizzare una funzione hash crittografica come MD5 o semplicemente utilizzare la rappresentazione di stringa di questo int?

Answer 1

I fondamentali sottolineato da Marc e Jon non sono male ma sono tutt'altro che ottimale in termini di uniformità di distribuzione dei risultati. Purtroppo il 'moltiplicare per i numeri primi' approccio copiato da così tante persone da Knuth è href="http://www.codeproject.com/KB/recipes/hash_functions.aspx" la scelta migliore in molti casi migliore distribuzione possono essere raggiunti più conveniente per calcolare le funzioni (anche se questo è molto leggera su hardware moderno). In realtà gettando numeri primi in molti aspetti della hashing è panacea .

Se si utilizza questi dati per le tabelle hash in modo significativo dimensioni si raccomanda la lettura di eccellente studio e la spiegazione di Bret Mulvey di varie tecniche moderne (e non così moderni) hashing comodamente fatto con C #.

Si noti che il comportamento con le stringhe delle varie funzioni hash è fortemente sbilanciata verso wehther le stringhe sono brevi (grosso modo il numero di caratteri sono hash prima che le punte cominciano a oltre portata) o lungo.

Uno dei più semplici e più facile da implementare è anche uno dei migliori, il Jenkins uno alla volta hash.

private static unsafe void Hash(byte* d, int len, ref uint h)
{
    for (int i = 0; i < len; i++)
    {
        h += d[i];
        h += (h << 10);
        h ^= (h >> 6);
    }
}

public unsafe static void Hash(ref uint h, string s)
{
    fixed (char* c = s)            
    {
        byte* b = (byte*)(void*)c;
        Hash(b, s.Length * 2, ref h);
    }
}

public unsafe static int Avalanche(uint h)
{
    h += (h<< 3);   
    h ^= (h>> 11);  
    h += (h<< 15);  
    return *((int*)(void*)&h);
}

è possibile quindi utilizzare questo modo:

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

è possibile unire più tipi diversi in questo modo:

public unsafe static void Hash(ref uint h, int data)
{ 
    byte* d = (byte*)(void*)&data;
    AddToHash(d, sizeof(int), ref h);
}

public unsafe static void Hash(ref uint h, long data)
{ 
    byte* d= (byte*)(void*)&data;
    Hash(d, sizeof(long), ref h);
}

Se avete solo l'accesso al campo come un oggetto senza alcuna conoscenza dei meccanismi interni si può semplicemente chiamare GetHashCode () su ciascuno e combinare tale valore in questo modo:

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

Purtroppo non si può fare sizeof (T) così si deve fare ogni struct singolarmente.

Se si desidera utilizzare la riflessione si può costruire su una base per tipo di una funzione che fa l'identità strutturale e hashing su tutti i campi.

Se si vuole evitare il codice non sicuro, allora è possibile utilizzare tecniche di mascheramento po 'di tirare fuori i singoli bit da int (e caratteri, se si tratta di archi) con non troppa fatica in più.

Answer 2

Gli hash non sono significa per essere unico - sono solo destinate ad essere ben distribuiti nella maggior parte delle situazioni. Stanno solo scopo di essere coerenti. Si noti che trabocca non dovrebbe essere un problema.

Solo l'aggiunta non è generalmente una buona idea, e dividendo di certo non lo è. Ecco l'approccio Io di solito uso:

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

Se siete tuttavia in un contesto controllato, si potrebbe desiderare di fare deliberatamente incontrollato.

Notare che si suppone che l'ordine è importante, cioè che { "a", "b"} deve essere differente dalla { "b", "a"}. Fateci sapere se questo non è il caso.

Answer 3

Non c'è niente di sbagliato in questo approccio purché i membri di cui stai combinando gli hashcode seguano le regole dei codici hash.In breve ...

1. Il codice hash dei membri privati ​​non dovrebbe cambiare per tutta la durata dell'oggetto
2. Il contenitore non deve modificare l'oggetto puntato dai membri privati ​​per evitare che a sua volta cambi il codice hash del contenitore

Answer 4

Se l'ordine degli articoli non è importante (ad es.{"a","b"} è uguale a {"b","a"}), puoi utilizzare l'esclusivo o combinare i codici hash:

hash ^= item.GetHashCode();

[Modificare:Come ha sottolineato Mark in un commento a una risposta diversa, questo ha lo svantaggio di fornire anche raccolte come {"a"} e {"a","b","b"} lo stesso codice hash.]

Se l'ordine è importante, puoi invece moltiplicare per un numero primo e aggiungere:

hash *= 11;
hash += item.GetHashCode();

(Quando moltiplichi a volte otterrai un overflow che viene ignorato, ma moltiplicando con un numero primo perdi un minimo di informazioni.Se invece moltiplicassi per un numero come 16, perderesti quattro bit di informazione ogni volta, quindi dopo otto elementi il ​​codice hash del primo elemento scomparirebbe completamente.)