¿Por qué un cubo de hashtable toma un número primo?
Tener una función hash
H (c) = c % n;
Cuando n toma un número compuesto, el ejemplo más simple es tomar 2^n, por ejemplo, tomar 2^3 = 8, en este momento
H (11100 (binario)) = H (28) = 4
H (10100 (binario)) = H (20) = 4
En este momento, el cuarto binario de binario (de derecha a izquierda) de C "fallará", lo que significa que no importa qué valor se tome en el cuarto bit de C, conducirá al mismo valor de h (c). En este momento, el cuarto bit de C no participa en la operación de H (c) en absoluto, por lo que H (c) no puede reflejar completamente las características de C, lo que aumenta las posibilidades de conflicto.
Al tomar otros números compuestos, algunos bits de C serán "fallidos" en diversos grados, lo que resulta en conflictos en algunas aplicaciones comunes.
Sin embargo, tomar números primos básicamente puede garantizar que cada bit de C participe en la operación de H (c), reduciendo así la posibilidad de conflictos en aplicaciones comunes. ．
(Opinión personal: a veces la eficiencia de no tomar números primos no es tan mala ... pero sin duda es más segura tomar números primos ...)
Lo anterior es mi comprensión
Para agregar a esto, esto significa que en aplicaciones comunes, algunos datos a menudo son similares. Es mejor usar números primos en este momento. Por ejemplo, los datos que se almacenarán están en un estado comprimido, como almacenar una tabla que describe el estado de búsqueda actual. En este momento, la probabilidad de hashing sin números primos es relativamente alta.
Si es un entero distribuido aleatoriamente, entonces el módulo hash será el mismo siempre que se tome lo suficientemente grande, pero esto obviamente está fuera de aplicación práctica.
Lo que dijo es una situación especial, porque cuando se selecciona un número primo relativamente pequeño, cuando se selecciona el gran número primo N, solo puede fallar en un cierto bit del sistema N-Digit. Combinado con las características del sistema informático, la representación N-Digit a menudo no es crítica, mientras que el sistema 2^n-digit comúnmente utilizado es más crítico, por lo que se pueden evitar conflictos.
De hecho, he usado algunos números grandes para probarlo para almacenar una matriz de adyacencia comprimida en binario. Cuando el módulo es lo suficientemente grande, incluso el número compuesto puede tener un efecto muy cercano al número primo, pero en algunos números compuestos (varias docenas), la eficiencia se reducirá severamente, por lo que los números primos son relativamente seguros.
También podría hacer sus propios experimentos, no elegir enteros aleatorios, pero considere algunas aplicaciones comunes, usar números primos y números compuestos para probar, examinando principalmente el factor de carga promedio, y la conclusión que obtiene puede ser lo mismo que los míos: los números compuestos también son buenos en la mayor parte del tiempo, pero el efecto es sorprendentemente pobre en algunos números compuestos, y casi todos los números primos tienen buenos resultados.
Personalmente, creo que en un sentido más general, si no tomas números primos, habrá algún peligro. El peligro ocurre cuando se supone que se selecciona el número no de procuración M = X*y, y si la clave del hash está relacionada con este divisor X, será miserable. En el peor de los casos, todos suponen que son múltiplos de x, entonces puedes imaginar que el resultado del hash es: 1 ~ y, no 1 ~ m. Sin embargo, si el tamaño del cubo se selecciona como un número primo, no habrá ningún problema.
Gracias por leer, espero que pueda ayudarte. ¡Gracias por su apoyo para este sitio!