Metodi di codice hash adatti per una matrice di byte?

Question

Qual è il miglior metodo di hash per un array di byte?

Gli array sono oggetti di classe serializzati contenenti l'immagine jpeg passata tra le applicazioni su TCP/IP.

La dimensione dell'array è di circa 200k.

Answer 1

Qualsiasi funzione di hashing incorporata dovrebbe essere eseguita; a seconda di quanto vi preoccupate per le collisioni queste sono le opzioni (dalla maggior parte delle collisioni al meno):

• MD5
• SHA1
• SHA256
• SHA384
• SHA512

Essi sono semplici da usare come:

var hash = SHA1.Create().ComputeHash(data); 

Punti bonus: Se non ti importa della sicurezza (che non credo ti faccia dato che stai ottenendo gli hash per le immagini) potresti voler esaminare l'hash di Murmur, che è progettato per l'hashing del contenuto e hashing sicuro (ed è quindi molto più veloce). Tuttavia, non è nel framework, quindi dovrai trovare un'implementazione (e probabilmente dovresti optare per Murmur3).

Edit: Se siete alla ricerca di un HashCode per un [] array di byte è interamente a te, di solito costituita da bit spostamento (da numeri primi) e XOR. Per esempio.

public class ByteArrayEqualityComparer : IEqualityComparer<byte[]> 
{ 
    public static readonly ByteArrayEqualityComparer Default = new ByteArrayEqualityComparer(); 
    private ByteArrayEqualityComparer() { } 

    public bool Equals(byte[] x, byte[] y) 
    { 
     if (x == null && y == null) 
      return true; 
     if (x == null || y == null) 
      return false; 
     if (x.Length != y.Length) 
      return false; 
     for (var i = 0; i < x.Length; i++) 
      if (x[i] != y[i]) 
       return false; 
     return true; 
    } 

    public int GetHashCode(byte[] obj) 
    { 
     if (obj == null || obj.Length == 0) 
      return 0; 
     var hashCode = 0; 
     for (var i = 0; i < obj.Length; i++) 
      // Rotate by 3 bits and XOR the new value. 
      hashCode = (hashCode << 3) | (hashCode >> (29))^obj[i]; 
     return hashCode; 
    } 
} 
// ... 
var hc = ByteArrayEqualityComparer.Default.GetHashCode(data); 

EDIT: Se si desidera convalidare che il valore non è cambiato si dovrebbe usare CRC32.

Answer 2

Qualsiasi componente di hashing crittografico dovrebbe funzionare. Non sono sicuro della velocità. Forse MD5?

Answer 3

Sulla base del Compiler Generated GetHashCode()

public static int GetHashCode(byte[] array) { 
    unchecked { 
     int i = 0; 
     int hash = 17; 
     int rounded = array.Length & ~3; 

     hash = 31 * hash + array.Length; 

     for (; i < rounded; i += 4) { 
      hash = 31 * hash + BitConverter.ToInt32(array, i); 
     } 

     if (i < array.Length) { 
      int val = array[i]; 
      i++; 

      if (i < array.Length) { 
       val |= array[i] << 8; 
       i++; 

       if (i < array.Length) { 
        val |= array[i] << 16; 
       } 
      } 

      hash = 31 * hash + val; 
     } 

     return hash; 
    } 
} 

Ah ... e un collegamento a C# Murmurhash http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html

Answer 4

Jon Skeet has a good answer su come ignorare GetHashCode, che si basa su tecniche di hash efficaci generali in cui si inizia con un numero primo, aggiungerlo ai codici hash dei componenti moltiplicati per un altro numero primo, consentendo l'overflow.

Per il vostro caso, si dovrebbe fare:

static int GetByteArrayHashCode(byte[] array) 
{ 
    unchecked 
    { 
     int hash = 17; 

     // Cycle through each element in the array. 
     foreach (var value in array) 
     { 
      // Update the hash. 
      hash = hash * 23 + value.GetHashCode();    
     } 

     return hash; 
    } 
} 

nota in risposta di Jon va sul perché questo è meglio di XOR gli hash dei singoli elementi (e che tipi anonimi in C# attualmente non XOR il hash dei singoli elementi, ma usa qualcosa di simile al precedente).

Mentre questo sarà più veloce degli algoritmi hash dal System.Security.Cryptography namespace (perché si tratta di hash più piccoli), lo svantaggio è che si potrebbero avere più collisioni.

È necessario testare i dati e determinare la frequenza con cui si verificano collisioni o il lavoro da eseguire in caso di collisione.