De acuerdo con this question, un diccionario .Net cambia el tamaño de su espacio asignado a los números primos que son al menos dos veces el tamaño actual. ¿Por qué es importante usar números primos y no solo el doble del tamaño actual? (Intenté usar mis poderes de google-fu para encontrar una respuesta, pero fue en vano)¿Por qué los diccionarios .Net cambian el tamaño de los números primos?
Es un detalle de implementación de algoritmo relacionado con choosing a good hashing function y que proporciona una distribución uniforme. Una distribución no uniforme aumenta la cantidad de colisiones y el costo de resolverlas.
Elegir el número primo no ** proporciona ** distribución uniforme, no es necesario simplificar demasiado. Con 'hashsize = prime_number', tienes absolutamente las mismas posibilidades de obtener colisiones que con' hashsize = 2^k' o cualquier otro. Es solo que algunos tamaños de hash hacen que las colisiones parezcan "impredecibles", "aleatorias" o "distribuidas uniformemente". Por otro lado, tener 'hashsize = 2^k' significaría que cualquier función hash basada en xor será mala. –
Debido a las matemáticas de los números primos. No pueden tenerse en cuenta en diferentes números más pequeños. Cuando divide el número hash de los elementos almacenados, obtiene una distribución igual. Si no tiene un número primo, según los objetos, la distribución puede no ser par.
El cubo en el que se coloca un elemento viene determinado por (hash & 0x7FFFFFF) % capacity. Esto necesita ser distribuido uniformemente. De esto se deduce que si múltiples entradas que son múltiplos de una cierta base (hash1 = x1 * base, hash2 = x2 * base, ...) donde base y capacity no son coprime (mayor divisor común> 1), algunas ranuras se usan demasiado, y algunas nunca usado. Dado que los números primos son coprimos a cualquier número, excepto a sí mismos, tienen relativamente buenas posibilidades de lograr una buena distribución.
Una propiedad particularmente buena de esto es que para capacity > 30 la contribución de cada bit al código de hash es diferente. Por lo tanto, si la variación del hash se concentra en solo unos pocos bits, se obtendrá una buena distribución. Esto explica por qué las capacidades que son poderes de dos son malas: enmascaran los bits altos. Un conjunto de números donde solo los bits altos son diferentes no es tan improbable.
Personalmente, creo que eligen esa función mal. Contiene una operación de módulo caro y si las entradas son múltiplos de la capacidad principal, su rendimiento se rompe. Pero parece ser lo suficientemente bueno para la mayoría de las aplicaciones.
como una idea secundaria para su pregunta, ¿alguien sabe una estructura de datos equilibrada similar a un árbol que cambia el tamaño a tamaños principales? tal vez debería publicar otra pregunta –
¿Cuál es la estructura de datos de árbol detrás del diccionario de .Net? –
Hice la pregunta aquí http://stackoverflow.com/questions/4639122/balanced-tree-like-data-structure-that-resizes-to-prime-sizes –