elementat - dictionary c# methods
¿Cómo se implementa el diccionario c#/. Net 3.5? (4)
Estoy usando una aplicación que usa varios diccionarios grandes (hasta 10 ^ 6 elementos), cuyo tamaño se desconoce de antemano (aunque puedo adivinar en algunos casos). Me pregunto cómo se implementa el diccionario, es decir, qué tan malo es el efecto si no doy una estimación inicial del tamaño del diccionario. ¿Utiliza internamente una matriz (de crecimiento propio) en la forma en que lo hace List? en ese caso, dejar que los diccionarios crezcan podría dejar una gran cantidad de grandes matrices sin referencia en el LOH.
La mejor manera para mí sería usar el reflector .NET.
Use el código desmontado para ver la implementación.
Las tablas hash normalmente tienen algo llamado factor de carga, que aumentará la tienda de cubos de respaldo si se alcanza este umbral. IIRC el valor predeterminado es algo así como 0.72. Si has hashing perfecto, esto puede aumentarse a 1.0.
Además, cuando la tabla hash necesita más cubos, se debe volver a generar toda la colección.
Utilizando Reflector , encontré lo siguiente: El Diccionario mantiene los datos en una matriz de estructuras. Mantiene una cuenta de cuántos lugares vacíos quedan en esa matriz. Cuando agrega un elemento y no queda ningún lugar vacío, aumenta el tamaño de la matriz interna (consulte a continuación) y copia los datos de la matriz anterior a la nueva matriz.
Así que le sugiero que use el constructor en el que establece el tamaño inicial si sabe que habrá muchas entradas.
EDITAR: La lógica es realmente bastante interesante: hay una clase interna llamada HashHelpers para encontrar primos. Para acelerar esto, también ha almacenado algunos números primos en una matriz estática de 3 hasta 7199369 (algunos faltan, por la razón, ver más abajo). Cuando suministra una capacidad, encuentra la siguiente prima (el mismo valor o más grande) de la matriz, y la usa como capacidad inicial. Si le da un número mayor que en su matriz, comienza a verificar manualmente.
Entonces, si no se transfiere nada al Capacity como capacidad, la capacidad de inicio es tres.
Una vez que se excede la capacidad, multiplica la capacidad actual por dos y luego encuentra el siguiente primo más grande usando la clase auxiliar. Es por eso que en la matriz no se necesitan todos los primos, ya que los primos "muy juntos" no son realmente necesarios.
Entonces, si no aprobamos ningún valor inicial, obtendríamos (revisé el arreglo interno):
- 3
- 7
- 17
- 37
- 71
- 163
- 353
- 761
- 1597
- 3371
- 7013
- 14591
- 30293
- 62851
- 130363
- 270371
- 560689
- 1162687
- 2411033
- 4999559
Una vez que pase este tamaño, el siguiente paso queda fuera de la matriz interna, y buscará manualmente primos más grandes. Esto será bastante lento. Puede inicializar con 7199369 (el valor más grande de la matriz) o considerar si tener más de 5 millones de entradas en un diccionario puede significar que debe reconsiderar su diseño.
MSDN dice: "Recuperar un valor usando su clave es muy rápido, cerca de O (1), porque la clase Dictionary se implementa como una tabla hash". y más adelante, "la capacidad se aumenta automáticamente según sea necesario reasignando la matriz interna".
Pero obtienes menos reasignaciones si das una estimación inicial. Si tiene todos los elementos desde el principio, el método LINQ ToDictionary podría ser útil.