.Net GetHashCode Bit operación de cambio

Question

que estaba buscando a través de algunas de la fuente .net ayer y vi varias implementaciones de GetHashCode con algo en la línea de este:

(i1 << 5) + i^i2 

Entiendo lo que el código está haciendo y por qué . Lo que quiero saber es por qué usaron (i1 < < 5) + i en lugar de (i1 < < 5) - i.

La mayoría de los marcos que he visto usan -i porque eso es equivalente a multiplicar por 31 que es primo, pero el modo de Microsoft es equivalente a multiplicar por 33 que tiene 11 y 3 como factores y por lo tanto no es primo.

¿Existe una justificación conocida para esto? ¿Alguna hipótesis razonable?

Answer 1

Hice la misma pregunta en math.stackexchange.com: Curious Properties of 33.

La conjetura entre los matemáticos y la investigación que hice sobre el tema me lleva a creer que la respuesta es la siguiente:

bien, descubrí por qué Microsoft utiliza 33. Eso se llama el Hash Bernstein . Resulta que 33 tiene algunas propiedades mágicas que producen una buena distribución de los códigos hash y hay muy poco conocimiento teórico de por qué.

Básicamente, en comparaciones de entropía y velocidad, Bernstein lo hace bastante bien y es bastante ágil. Dan Bernstein, el tipo que creó los 33 constantes, no pudo explicar qué propiedad de 33 produjo una distribución de hashes tan buena.

Varios documentos han sido escritos comparando las funciones de hash y han corroborado este hallazgo sin explicar aún más la ventaja de usar 33. Además, no pude encontrar qué Java utiliza 31 en su lugar. Parece ser un misterio matemático y de programación hasta la fecha.

Answer 2

No recuerdo si 31 es uno de esos números primos, pero hay ciertos números primos, que se acostumbra como las capacidades de Dictionary<K,V>. Y si usa el campo de la izquierda ya no influye en el cubo elegido y el hash degenera.