.NET ConcurrentDictionary capacidad inicial configurada en número primo arbitrario en lugar de la capacidad esperada en la documentación de ejemplo de MSDN. ¿Por qué?

Question

que solo estaba buscando en el MSDN documentation for ConcurrentDictionary, y vi esto en el "ejemplo" código:

// We know how many items we want to insert into the ConcurrentDictionary. 
// So set the initial capacity to some prime number above that, to ensure that 
// the ConcurrentDictionary does not need to be resized while initializing it. 
int NUMITEMS = 64; 
int initialCapacity = 101; 

Como referencia, el diccionario en el ejemplo de MSDN se inicia de la siguiente manera:

ConcurrentDictionary<int, int> cd = new ConcurrentDictionary<int, int>(Environment.ProcessorCount * 2, initialCapacity); 
for (int i = 0; i < NUMITEMS; i++) cd[i] = i * i; 

En el ejemplo, el diccionario nunca contendrá más de 64 elementos. ¿Por qué no establecer la capacidad inicial en 64, en lugar de un número primo aparentemente arbitrario mayor que 64? El comentario dice que esto es para asegurar que el diccionario no necesita ser redimensionado al inicializarlo, pero ¿por qué un diccionario similar con initialCapacity = 64 necesita ser redimensionado? ¿Por qué se eligió este número primo?

Answer 1

Diccionario o tabla hash se basa en hash la clave para obtener un índice más pequeño para buscar en la tienda correspondiente (matriz). Entonces la elección de la función hash es muy importante. La elección típica es obtener el código hash de una clave (para que tengamos una buena distribución aleatoria) y luego dividir el código entre un número primo y usar un recordatorio para indexar en un número fijo de segmentos. Esto permite convertir códigos hash arbitrariamente grandes en un conjunto limitado de números pequeños para los cuales podemos definir una matriz para buscar. Por lo tanto, es importante tener un tamaño de matriz en número primo y luego la mejor opción para el tamaño se convertirá en el número primo que es más grande que la capacidad requerida. Y eso es exactamente lo que hace la implementación del diccionario.

Así que, básicamente, cualquier implementación del diccionario Modulo N (n es el número primo) necesitará su capacidad para estar en el número primo. Entonces, si usted dice que la capacidad requerida es X, entonces esta implementación típicamente elegirá el número de cebador más grande que la capacidad requerida.