¿Convertir el tamaño de matriz en un número primo ayuda en la implementación de la tabla hash? ¿Por qué?

Un objetivo clave de la implementación de la tabla hash es minimizar las colisiones, y muchas tablas hash de libros de texto operan evaluando una suma de combinaciones lineales de partes de su módulo de datos n.

Si el número n de ranuras utilizables en la tabla hash es un número primo, se garantiza que cualquier módulo de valor n solo tiene un módulo inverso n, pero esto no se cumple si n no es primo. La existencia de inversas múltiples o la inexistencia de inversas dará como resultado una distribución desigual de sus valores mapeados, porque ya no hay una x única que satisfaga a * x mod n = b, que tiene el efecto de mapear dos valores diferentes módulo n al mismo valor. Esto dará como resultado una mayor probabilidad de colisión.

Puede pensarlo de la siguiente manera, si a tiene dos inversos módulo n, entonces:

ax mod n puede ser igual a ay mod n si x e y son inversas de a. En este caso, tendrá una colisión evitable, ya que x o y habrían encajado en la matriz (ya que son números mod n) pero no colisionaron. Sin embargo, después de la multiplicación por a pueden colisionar. Se garantiza que esto no sucederá si n es primo.

La pregunta es un poco de arenque rojo. El tamaño de la matriz simplemente dicta el módulo aplicado después de la función hash, que simplemente asigna objetos a los enteros. Es el comportamiento de esta función (quizás en relación con el módulo) lo que * realmente * importa. Si tengo 100 elementos que se asignan perfectamente a los números del 1 al 100, entonces no importa mucho si coloco esos elementos en 13 cubos o 14 cubos porque se distribuirán uniformemente de cualquier manera.

Ahora, si su función hash agrupa los datos, entonces el módulo * podría * ayudar dividiendo un grupo en dos secciones, pero eso no tiene nada que ver con la primalidad y todo lo que tiene que ver con dónde están los grupos en relación con su módulo .

Entonces, lo que necesita es una función de hashing que distribuya suficientemente datos arbitrarios sobre un área determinada (creo que probablemente haya un enlace a la entropía de cifrado aquí), no un módulo en particular. Sin embargo, podría estar equivocado y me encantaría ver evidencia de lo contrario.