¿Por qué no hay Dictionary.TrimExcess()?

Question

En .NET, hay un constructor para Dictionary<TKey, TValue> que toma un parámetro, int capacity. Esto es lo mismo que con muchas otras colecciones como List<T>, Queue<T> y Stack<T>; además, según the MSDN documentation:

La capacidad de un diccionario es la cantidad de elementos que se pueden agregar al diccionario antes de que sea necesario cambiar el tamaño. A medida que se agregan elementos a un diccionario, la capacidad se incrementa automáticamente según sea necesario al reasignar la matriz interna.

Esto me suena más o menos lo mismo que con otras colecciones como List<T>, etc Dado que estas colecciones característica de auto-cambiar el tamaño de la conducta cuando sea necesario y, por tanto, son propensos a tener una mayor capacidad que la requerida, la mayoría de ellos cuentan con una TrimExcess método. Esto es útil si, por ejemplo, está agregando un número desconocido de elementos a la colección a la vez, y después de eso no agregará ningún elemento adicional.

¿Por qué Dictionary<TKey, TValue> no tiene este mismo método TrimExcess?

(Negación: estoy bastante familiarizado con las "características no existe por defecto" respuesta; supongo que estoy en su mayoría sólo se pregunta si hay una razón particular por la TrimExcess para un Dictionary no tiene sentido, o por qué sería significativamente más difícil de implementar que para colecciones más simples como List.)

Answer 1

Por MSDN Dictionary se implementa como una tabla hash. Si eliminaste el exceso, tendrías que encontrar un algoritmo que proporcionara casi O (1) tiempos de búsqueda en lo que efectivamente sería una lista ordenada aleatoriamente.

Answer 2

Supongo que en este caso el argumento de capacidad ayuda a definir la función de hashing así como el número de segmentos; cambiar el tamaño/recorte de una colección dispersa de datos requeriría volver a calcular hashes de todos los elementos almacenados restantes.

Answer 3

Esto es parcialmente una suposición: un diccionario está "ordenado" como una tabla hash. La capacidad reservada no es simplemente un montón de direcciones de memoria libres en la parte superior de su diccionario. En cambio, consiste en una habitación vacía en todo el Diccionario. Esto se hace para que agregar/mover/eliminar etc. sea muy eficiente. Si tuviera un método TrimExcess para el Diccionario, todo el Diccionario tendría que copiar todo en una nueva ubicación sin ningún espacio entre los elementos.

realidad: los vacíos deben permanecer por lo demás el beneficio de una tabla hash expira, el recorte (TrimExcess), en caso de aplicarse, sólo se debe recortar el ValueCollection interna.

Actualización: expandido y modificado mis palabras mal elegido
Actualización:the BCL team says TrimExcess for Dictionaries "could be useful".
Actualización: la solicitud de función resuelta como No se solucionará: "Desafortunadamente, no podremos acceder a esto para la próxima versión de .NET, así que estoy resolviendo esto como No se solucionará "

Answer 4

En realidad, yo fui quien le pidió a Microsoft que implementara TrimExcess. Ya presenté más de un artículo que trata sobre diccionarios y en todos los casos implementé TrimExcess.De hecho, el tamaño utilizado cuando los cubos son demasiado pequeños puede invocarse al aumentar o disminuir el tamaño de los cubos.

Hoy me acabo de publicar otro artículo, se trata de una implementación en C++ de un diccionario, que apoya TrimExcess: http://www.codeproject.com/Articles/761040/A-NET-like-Dictionary-in-Cplusplus

Otra aplicación (.NET) se puede encontrar en este artículo: http://www.codeproject.com/Articles/548406/Dictionary-plus-Locking-versus-ConcurrentDictionar