¿Por qué las entradas son orden adicional en un diccionario.Net?
dictionary string object (11)
Acabo de ver este comportamiento y estoy un poco sorprendido por eso ...
Si agrego 3 o 4 elementos a un diccionario y luego hago un "para cada uno" para obtener todas las claves, aparecen en el mismo orden en que los agregué.
La razón por la que esto me sorprende es que se supone que un diccionario es un HashTable internamente, por lo que esperaba que las cosas salieran en CUALQUIER orden (ordenadas por el hash de la clave, ¿no?)
¿Que me estoy perdiendo aqui? ¿Es este un comportamiento con el que puedo contar?
EDITAR: OK, ya pensé en muchas de las razones por las que esto podría suceder (como la lista separada de las entradas, si esto es una coincidencia, etc.). Mi pregunta es, ¿alguien sabe cómo funciona esto realmente?
¿Qué teclas agregó en su prueba y en qué orden?
Creo que esto proviene del antiguo .NET 1.1 veces en el que tenía dos tipos de diccionarios "ListDictionary" y "HybridDictionary". ListDictionary era un diccionario implementado internamente como una lista ordenada y fue recomendado para "pequeños conjuntos de entradas". Luego tenía HybridDictionary , que inicialmente estaba organizado internamente como una lista, pero si crecía más de lo que un umbral configurable se convertiría en una tabla hash. Esto se hizo porque los diccionarios históricos basados en hash se consideraban costosos. Ahora, un día que no tiene mucho sentido, pero supongo que .NET simplemente basó su nueva clase genérica Dictionary en el viejo HybridDictionary.
Nota : De todos modos, como alguien más ya señaló, nunca debes contar con el orden del diccionario para nada
Es posible que todas las entradas estén en el mismo cubo hash en el diccionario. Cada cubo es probablemente una lista de entradas en el cubo. Esto explicaría las entradas regresando en orden.
Hasta un determinado tamaño de lista, es más barato simplemente verificar cada entrada en lugar de hash. Eso es probablemente lo que está sucediendo.
Agregue 100 o 1000 artículos y vea si todavía están en el mismo orden.
La pregunta y muchas de las respuestas parecen malinterpretar el propósito de una tabla hash o diccionario. Estas estructuras de datos no tienen comportamientos especificados con respecto a la enumeración de los valores (o, de hecho, las claves) de los elementos contenidos en la estructura de datos.
El propósito de un diccionario o hashtable es poder buscar de manera eficiente un valor específico dada una clave conocida. La implementación interna de cualquier diccionario o hashtable debería proporcionar esta eficiencia en las búsquedas, pero no es necesario que proporcione ningún comportamiento específico con respecto a enumeraciones o iteraciones de tipo "para cada" en los valores o claves.
En resumen, la estructura de datos interna puede almacenar y enumerar estos valores de la forma que desee, incluido el orden en que se insertaron.
No puede contar con este comportamiento, pero no es sorprendente.
Considere cómo implementaría la iteración clave para una tabla hash simple. Debería iterar sobre todos los intervalos de hash, tengan o no algo en ellos. Obtener un pequeño conjunto de datos de una gran tabla hash podría ser ineficiente.
Por lo tanto, podría ser una buena optimización mantener una lista de claves duplicada por separado. Usando una lista de doble enlace aún obtienes inserción / eliminación a tiempo constante. (Usted mantendría un puntero del cubo de hashtable en esta lista.) De esa manera, iterar a través de la lista de claves depende únicamente del número de entradas, no del número de segmentos.
Odio este tipo de funcionalidades "por diseño". Creo que al darle a tu clase un nombre genérico como "Diccionario", también debería comportarse "como generalmente se espera". Por ejemplo, std :: map siempre mantiene sus valores clave ordenados.
Editar: aparentemente la solución es usar SortedDictionary, que se comporta de manera similar a std :: map.
Por lo que sé, este no debería ser un comportamiento en el que confiar. Para verificarlo rápidamente use los mismos elementos y cambie el orden en que los agrega al diccionario. Verás si los recuperas en el orden en que fueron agregados o si fue solo una coincidencia.
Si usa .NET Reflector en las bibliotecas de clase 3.5, puede ver que la implementación de Dictionary realmente almacena los elementos en una matriz (que se redimensiona según sea necesario) y los índices de hash en esa matriz. Al obtener las claves, ignora por completo la tabla hash e itera sobre la matriz de elementos. Por esta razón, verá el comportamiento que ha descrito ya que se agregan nuevos elementos al final de la matriz. Parece que haces lo siguiente:
add 1
add 2
add 3
add 4
remove 2
add 5
usted recibirá 1 5 3 4 porque reutiliza las ranuras vacías.
Es importante tener en cuenta que, al igual que muchos otros, no puede contar con este comportamiento en versiones futuras (o pasadas). Si quiere que su diccionario esté ordenado, hay una clase SortedDictionary para este fin.
Un diccionario recupera elementos en orden hash. El hecho de que salieron en orden de inserción fue una coincidencia total.
La documentación de MSDN dice:
El orden de las claves en KeyCollection no está especificado, pero es el mismo orden que los valores asociados en ValueCollection devueltos por la propiedad Values.
Una cita de MSDN :
El orden de las claves en el Diccionario <(Of <(TKey, TValue>)>). KeyCollection no está especificado, pero es el mismo orden que los valores asociados en el Diccionario <(Of <(TKey, TValue>)>) .ValueCollection devuelto por la propiedad Dictionary <(Of <(TKey, TValue>)>). Values.