Ilmari y leonbloy ya han dicho bastante y proporciona conexiones pertinentes; he aquí algunas ideas:
En primer lugar, acerca de los números primos: el aceptado la respuesta a esta pregunta en stackoverflow suena bien para mí. No es que el multiplicador o el tamaño de la tabla hash deben ser primos; que debe ser sólo coprime. Si usted está escribiendo el código, por tanto, no hay razón para que ellos se prime, pero si usted está escribiendo el código para que sólo uno de ellos (lo cual sucede a menudo en la práctica), es posible que desee elegir los números primos, o al menos con los números primos grandes factores, para reducir las posibilidades de un "primer choque" entre el multiplicador y el tamaño de la tabla hash.
Segundo, acerca de hashcodes ser "bien distribuida" o "de forma óptima propagación": Eso es sólo parte de la historia. Para cadenas largas, donde la inyectividad no es una opción, la dispersión aleatoria es buena, pero para cadenas cortas, de inyectividad es incluso mejor que la dispersión aleatoria. Idealmente, un multiplicador basado en la función hash debe tener una extensión aleatoria inicial de entradas, pero ser inyectiva con respecto a las últimas entradas.
Los códigos ASCII de las letras de la misma caso de que sólo se diferencian en el bajo $5$ bits. Así que para las cadenas que terminan en letras minúsculas y $32$-bit valores de hash, usted puede obtener de inyectividad con respecto a los últimos seis caracteres, si el multiplicador es mayor que $32$, mientras que para los multiplicadores de menos de $32$ el bit más bajo de la penúltima entrada de influencias en la mayoría de los últimos $5$ bits y por lo tanto su contribución no es linealmente independientes de las contribuciones de todos los demás bits. En el caso de que usted está usando sólo la mitad de la disposición de los valores hash, y los valores de los últimos seis entradas formar parejas que se asignan a los mismos valores de hash.
Si el multiplicador es mayor que $32$, y la multiplicación no se desborde, de inyectividad con respecto al último de los $6$ caracteres en minúsculas está garantizada. Este es el caso, hasta un multiplicador de $47$ (desde $2^4\cdot47^5\lesssim2^{32}$), pero más allá de eso, las contribuciones de los distintos bits generalmente son linealmente independientes (hay una buena oportunidad para $30$ random vectores en $\mathbb F_2^{32}$ a es linealmente independiente); el primer impar multiplicador para los que no están es $95$.
Así que no es inmediatamente claro por qué se $33$ debe ser mejor para cadenas de caracteres ASCII que cualquier otro impar multiplicador mayor que $32$ resto $1$ mod $4$ (ver Ilmari la respuesta). Sin embargo, en términos más generales, menor es el multiplicador, el final más entradas se correlacionan injectively antes de que empiecen revueltos por el desbordamiento. Por lo que bien podría ser que el $33$ es un buen trade-off entre la obtención de la parte inferior $5$ bits de los caracteres ASCII de cada uno de los otros de la manera que requiere el $f\ge32$) y el retraso de la aparición de la codificación, por desbordamiento (que requiere un bajo $f$).
Una nota sobre la diferencia entre el XOR variante y la donde $j$ lugar: Mi consideraciones anteriores sobre la independencia lineal sólo se aplican a la operación XOR caso, en el que nos puede tratar el valor de hash como un vector en un $\mathbb F_2^{32}$ y la función de hash como una transformación afín en ese espacio. En el caso de la suma, no es necesario que el multiplicador sea mayor que la de $32$ para el hash a ser inyectiva con respecto a los últimos seis entradas, apenas mayor que el número de letras minúsculas, que es $26$, así que en ese caso no hay ninguna ventaja en particular a $33$. Eso es confirmado por los resultados experimentales que leonbloy vinculado a, donde a $31$ (con la etiqueta "K&R") incluso ligeramente mejor en las palabras de $33$ (con la etiqueta "Bernstein"); se puede ver cerca de la parte superior de la página o siguiendo las Bernstein vínculo que estos resultados se refieren al caso con la adición. (Esto es consistente con la idea de que los multiplicadores más bajos son generalmente mejor mientras mapa de las letras minúsculas injectively, pero parece arrojar algunas dudas sobre Ilmari del punto sobre el resto de mod $4$?)
Ejemplos en los que la combinación de $31$ y XOR no es inyectiva ya ocurre con $3$ letras; por ejemplo, "rox" y "rng" no se asignan a 1A607.
Esto es todo acerca de las ventajas de un multiplicador con respecto a la evitación de colisiones de hash. A menudo la velocidad de computación de la función de hash es al menos tan importante como evitar colisiones, y en ese sentido $33$ tiene la ventaja sobre la mayoría de los otros multiplicadores (aunque no más de $31$) que puede ser fácilmente calculada con un turno, y además, como usted ha explicado.
