Usando (a * k)% M, donde a es un primo fijo. ¿Esto cambia los bits de mezcla lo suficiente como para que puedas usar M no primo?

Answer 1

La respuesta corta: en realidad no, solo permuta qué cubos se usan si hay una distribución desigual de claves.

Todo se remonta a si espera algún patrón en las teclas o no. ¿Por qué querríamos usar hash utilizando un módulo principal de todos modos? Debido a que los patrones en la entrada tienen menos probabilidades de ser múltiplos de un primo grande que de uno pequeño. Consulte Para una función hash simple h (k) = k mod M, ¿por qué M debería ser un número primo?

Por ejemplo, si tenemos una función hash f (x) = x mod 8, pero nuestros números son todos pares, entonces los cubos 0, 2, 4, 6 obtendrán todas las claves, mientras que los cubos 1, 3, 5 y 7 tendrán permanecer vacío Pero la función hash f (x) = x mod 7 evita este problema particular, aunque lo reintroduce para datos que son todos congruentes mod 7. En la vida real, estos ejemplos son raros.

¿Qué pasa con f (x) = 3x mod 8? Eso todavía no funciona para el caso completo. f (0) = 0, f (2) = 6, f (4) = 4, f (6) = 2, f (8) = 0, f (10) = 6, etc. Los cubos 1, 3, 5, 7 no se utilizan.

Si M tiene un divisor D, y A es coprimo con M, entonces los cubos 0, D, 2D, 3D, 4D, … mod M son exactamente el mismo conjunto que si todos los números se multiplicaran por A primero; pueden estar en un orden diferente. Esto se debe a que A tiene un modo inverso multiplicativo M, que establece un mapeo uno a uno entre los dos conjuntos de cubos.

Si A no es coprimo con M, es aún peor; entonces, incluso las entradas uniformes no se combinan uniformemente.

La multiplicación a veces es útil si queremos que los elementos adyacentes caigan en cubos no adyacentes, pero eso es todo.