¿Por qué la aplicación código hash “basada en prime” se utiliza en lugar de la “ingenua”?

Question

he visto que un número primo aplicación de la función GetHashCode está siendo recomienda, por ejemplo aquí . Sin embargo, utilizando el siguiente código (en VB, lo siento), parece como si la aplicación que da la misma densidad de hash como una aplicación XOR "ingenua". Si la densidad es la misma, yo supongo que es la misma probabilidad de colisión en ambas implementaciones. Me estoy perdiendo algo sobre por qué se prefiere el enfoque primordial?

Estoy supossing que si el código hash es un byte que no pierda generalidad para el caso entero.

Sub Main()
    Dim XorHashes(255) As Integer
    Dim PrimeHashes(255) As Integer

    For i = 0 To 255
        For j = 0 To 255
            For k = 0 To 255
                XorHashes(GetXorHash(i, j, k)) += 1
                PrimeHashes(GetPrimeHash(i, j, k)) += 1
            Next
        Next
    Next

    For i = 0 To 255
        Console.WriteLine("{0}: {1}, {2}", i, XorHashes(i), PrimeHashes(i))
    Next
    Console.ReadKey()
End Sub

Public Function GetXorHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Return CByte((valueOne Xor valueTwo Xor valueThree) Mod 256)
End Function

Public Function GetPrimeHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Dim TempHash = 17
    TempHash = 31 * TempHash + valueOne
    TempHash = 31 * TempHash + valueTwo
    TempHash = 31 * TempHash + valueThree

    Return CByte(TempHash Mod 256)
End Function

Answer 1

La probabilidad de colisiones también depende de la distribución esperada de los datos de entrada. En su ejemplo se asume de datos de entrada que se distribuye de manera uniforme en todo el rango. Esta es la situación ideal y no es de extrañar que tanto los algoritmos funcionan bien.

Sin embargo, si se asume que los datos de entrada general es similar en los bits altos y difiere en su mayoría sólo en los bits bajas (nota: una gran cantidad de datos reales es así), el método de los números primos se extenderá esta variación a lo largo de todo el hash mientras que el método XOR no - pequeños cambios en los bits bajos de dos o más valores puede cancelar fácilmente entre sí cuando XOR'ed. Por lo que el método de número primo es menos probable que chocan en este caso.

También se debe utilizar valores de 32 bits para GetHashCode, no valores de 8 bits.

Answer 2

truncar el hash es el problema aquí. El método Xor tan sólo puede producir 256 valores distintos. El método Primer puede generar más de 750.000 valores distintos, pero que tirar a la basura 749 744 utilizando sólo los 8 bits bajos. Y por lo tanto nunca puede hacer un mejor trabajo que Xor.

En su caso específico, se puede hacer mucho mejor. Hay suficientes bits en un número entero de generar un hash único, con 16 millones de valores distintos:

  Public Shared Function GetGoodHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Integer
    Return valueOne And 255 + (valueTwo And 255) << 8 + (valueThree And 255) << 16
  End Function

El método Xor está bien cuando los valores de entrada están bien distribuidas. Un problema con el método primordial es que es fácil de provocar una excepción de desbordamiento. Eso es difícil de tratar en el código VB.NET, que no tiene el equivalente de la palabra clave de C # sin marcar. Usted tiene que apagar eso a nivel mundial con proyecto + Propiedades, ficha compilar, Opciones de compilación avanzadas, marque "Eliminar comprobaciones de desbordamiento de entero". Evitar que calculando el hash como un Int64. Lo que lo hace un poco caro.