c# - ¿Por qué establecer la longitud de HashTable en un número primo es una buena práctica?

arrays hashcode

Question

Estaba revisando la última publicación de Eric Lippert en el blog para obtener pautas y reglas para GetHashCode cuando llegué a este para:

Podríamos ser incluso más inteligentes aquí; al igual que una Lista se redimensiona a sí misma cuando se llena, el conjunto de cubos también podría redimensionarse a sí mismo, para garantizar que la longitud promedio de la cubeta permanezca baja. Además, por razones técnicas, a menudo es una buena idea hacer que la longitud del conjunto de cubetas sea un número primo , en lugar de 100. Hay muchas mejoras que podríamos realizar en esta tabla hash. Pero este rápido bosquejo de una implementación ingenua de una tabla hash servirá por ahora. Quiero que sea sencillo.

Así que parece que me estoy perdiendo algo. ¿Por qué es una buena práctica establecer un número primo?

Answer 1

Porque esto produce una mejor función hash y reduce el número de posibles colisiones. Esto se explica en Elegir una buena función de hash :

Un requisito básico es que la función debe proporcionar una distribución uniforme de los valores hash. Una distribución no uniforme aumenta el número de colisiones y el costo de resolverlas.

La distribución debe ser uniforme solo para los tamaños de tabla que se producen en la aplicación. En particular, si uno usa el cambio de tamaño dinámico con la duplicación y reducción exactas de s, la función hash debe ser uniforme solo cuando s es una potencia de dos. Por otro lado, algunos algoritmos de hash proporcionan hashes uniformes solo cuando s es un número primo.

Answer 2

Puedes encontrar personas que sugieran los dos extremos opuestos del espectro. Por un lado, elegir un número primo para el tamaño de la tabla hash reducirá las posibilidades de colisiones, incluso si la función hash no es demasiado efectiva en la distribución de los resultados. Tenga en cuenta que si (en el ejemplo más simple sobre el que se discute) se decide una potencia de 2 tamaños, solo los bits más bajos afectan al depósito, mientras que para un número primo, se utilizarán la mayoría de los bits en el resultado del hash.

Por otro lado, puede obtener más al elegir una mejor función de hash, o incluso volver a usar el resultado de la función de hash aplicando algunas operaciones de bit, y utilizando una potencia de 2 hash para acelerar los cálculos.

Como ejemplo de la vida real, Java HashTable se implementó inicialmente usando prime (o casi prime prime), pero a partir de Java 1.4, el diseño se cambió para usar la potencia de dos cubetas y se agregó una segunda función hash rápida aplicada al resultado del hash inicial. Un interesante artículo comentando que el cambio se puede encontrar here .

Así que básicamente:

• un número primo ayuda a dispersar las entradas en los diferentes grupos, incluso en el caso de funciones hash no tan buenas.

• se puede lograr un efecto similar mediante el procesamiento posterior del resultado de la función hash y el uso de una potencia de 2 tamaños para acelerar la operación de módulo (máscara de bits) y compensar el procesamiento posterior.

Answer 3

Digamos que la longitud del conjunto de cubos es una potencia de 2, lo que hace que los cálculos de mod sean bastante rápidos. También significa que la selección del grupo se determina únicamente por los m bits superiores del código hash. (Donde m = 32 - n , donde n es la potencia de 2 que se está utilizando). Así que es como si estuvieras tirando fragmentos útiles del código hash inmediatamente.

O como en esta publicación del blog de 2006 lo pone:

Supongamos que la función hashCode genera los siguientes códigos hash entre otros {x, 2x, 3x, 4x, 5x, 6x ...}, entonces todos estos se agruparán en m número de grupos, donde m = table_length / GreatestCommonFactor ( table_length, x). (Es trivial verificar / derivar esto). Ahora puede realizar una de las siguientes acciones para evitar la agrupación en clústeres:

...

O simplemente haga que m sea igual a table_length haciendo que GreatestCommonFactor (table_length, x) sea igual a 1, es decir, haciendo que table_length coprime con x. Y si x puede ser casi cualquier número, entonces asegúrese de que table_length sea un número primo.