Pourquoi un dictionnaire "n'est pas ordonné"?

Question

J'ai lu cela dans une réponse à beaucoup de questions ici. Mais que signifie exactement?

var test = new Dictionary<int, string>();
test.Add(0, "zero");
test.Add(1, "one");
test.Add(2, "two");
test.Add(3, "three");

Assert(test.ElementAt(2).Value == "two");

Le code ci-dessus semble fonctionner comme prévu. Oui, de quelle manière est un dictionnaire considéré comme non ordonnée? En vertu de ce que les circonstances pouvaient le code ci-dessus échouent?

Answer 1

Eh bien, pour une chose qu'il n'est pas clair si vous vous attendez à ce que cela soit l'insertion de l'ordre ou de la clé de commande. Par exemple, ce que vous vous attendriez à ce que le résultat soit si vous avez écrit:

var test = new Dictionary<int, string>();
test.Add(3, "three");
test.Add(2, "two");
test.Add(1, "one");
test.Add(0, "zero");

Console.WriteLine(test.ElementAt(0).Value);

Vous attendez-vous à "trois" ou "zéro"?

Comme il arrive, je pense que la mise en œuvre actuelle conserve d'insertion de la commande tant que vous ne supprimez jamais rien - mais vous ne devez pas compter sur cela. C'est un détail d'implémentation, et qui pourrait changer dans le futur.

Les suppressions également affecter cette. Par exemple, à quoi vous attendez-vous la suite de ce programme?

using System;
using System.Collections.Generic;

class Test
{ 
    static void Main() 
    {
        var test = new Dictionary<int, string>();
        test.Add(3, "three");
        test.Add(2, "two");
        test.Add(1, "one");
        test.Add(0, "zero");

        test.Remove(2);
        test.Add(5, "five");

        foreach (var pair in test)
        {
            Console.WriteLine(pair.Key);
        }
    }     
}

C'est en fait (ma boite) 3, 5, 1, 0. La nouvelle entrée pour 5 a utilisé le libérées entrée précédemment utilisé par 2. Cela ne va pas être garanti que ce soit à travers.

Ressasser (lorsque le dictionnaire de stockage sous-jacent doit être élargie) pourrait affecter des choses... toutes sortes de choses à faire.

Il suffit de ne pas la traiter comme une collection ordonnée. Il n'est pas conçu pour cela. Même si elle arrive à travailler maintenant, vous êtes en s'appuyant sur les sans-papiers, un comportement qui va à l'encontre de l'objectif de la classe.

Answer 2

Un Dictionary<TKey, TValue> représente une Table de Hachage et dans une table de hachage y a pas de notion d'ordre.

La documentation explique assez bien:

Pour les fins du recensement, chaque élément dans le dictionnaire est traité comme un KeyValuePair structure représentant une valeur et sa clé. L' l'ordre dans lequel les articles sont retournés n'est pas défini.

Answer 3

Il y a beaucoup de bonnes idées ici, mais dispersés, donc je vais essayer de créer une réponse qui pose mieux, même si le problème a été répondu.

Tout d'abord, un Dictionnaire n'a pas la garantie de l'ordre, de sorte que vous ne les utiliser que pour chercher rapidement une clé et trouver une valeur correspondante, ou de vous énumérer toutes les paires clé-valeur, sans se soucier de ce que l'ordre est.

Si vous souhaitez commander, vous pouvez utiliser un OrderedDictionary mais la différence est que la recherche est plus lent, donc, si vous n'avez pas besoin d'ordre, ne le demandez pas.

Les dictionnaires (et HashMap en Java) utiliser le hachage. Qui est O(1) quelle que soit la taille de votre table. Commandé dictionnaires utilisent généralement une forme d'équilibre de l'arbre qui est en O(log2(n)), de sorte que vos données augmente, l'accès devient plus lent. Pour comparer, pour 1 millions d'éléments, c'est de l'ordre de 2^20, de sorte que vous avez à faire sur l'ordre de 20 recherches pour un arbre, mais 1 pour une valeur de hachage de la carte. C'est BEAUCOUP plus rapide.

Le hachage est déterministe. Le Non-déterminisme signifie que lorsque vous hachage(5) la première fois, et vous hachage(5) la prochaine fois, vous obtenez un endroit différent. Que ce serait complètement inutile.

Ce que les gens veulent dire, c'est que si vous ajoutez quelque chose à un dictionnaire, l'ordre est compliqué, et sous réserve de modifier à tout moment vous ajouter (ou supprimer) un élément. Imaginez, par exemple, la table de hachage a 500k éléments, et vous avez 400k de valeurs. Lorsque vous ajoutez un de plus, vous atteignez le seuil critique parce qu'il a besoin d'environ 20% d'espace vide pour être efficace, il alloue une plus grande table (par exemple, 1 million d'entrées) et re-hachage toutes les valeurs. Maintenant ils sont tous dans des endroits différents qu'ils ne l'étaient avant.

Si vous construisez le même Dictionnaire à deux reprises (lire ma déclaration en détail, LE MÊME), vous obtiendrez le même ordre. Mais comme Jon correctement dit, ne comptez pas sur elle. Trop de choses peuvent faire pas les mêmes, même le initialement alloués taille.

Cela soulève un excellent point. C'est vraiment, vraiment cher pour redimensionner une hashmap. Cela signifie que vous devez allouer un plus grand tableau, et insérez-la de nouveau chaque paire clé-valeur. Alors, il vaut la peine de l'allocation de 10x la mémoire dont il a besoin, plutôt que d'avoir même un seul grandir arriver. Connaître votre taille de la table de hachage, et préallouer assez, si c'est possible, c'est une énorme performance de gagner. Et si vous avez une mauvaise mise en œuvre, qui n'est pas redimensionnée, il peut être une catastrophe si vous prenez trop petite de taille.

Maintenant, ce que Jon a fait valoir avec moi dans mon commentaire dans sa réponse a été que, si vous ajoutez des objets à un Dictionnaire en deux pistes, vous obtiendrez deux différents rangements. Vrai, mais ce n'est pas le dictionnaire de la faute.

Quand vous dites:

new Foo();

vous êtes à la création d'un nouvel objet à un nouvel emplacement dans la mémoire.

Si vous utilisez la valeur Foo que la clé dans un dictionnaire, sans aucune autre information, la seule chose qu'ils peuvent faire est d'utiliser l'adresse de l'objet en tant que clé.

Cela signifie que

var f1 = new Foo(1);
var f2 = new Foo(1);

f1 et f2 ne sont pas le même objet, même si elles ont les mêmes valeurs.

Donc, si vous étiez à les mettre dans les Dictionnaires:

var test = new Dictionary<Foo, string>();
test.Add(f1, "zero");

ne vous attendez pas à être le même que:

var test = new Dictionary<Foo, string>();
test.Add(f2, "zero");

même si f1 et f2 ont les mêmes valeurs. Qui n'a rien à voir avec le comportement déterministe du Dictionnaire.

Le hachage est un super sujet en informatique, mes favoris pour enseigner dans des structures de données.

Découvrez Cormen et Leiserson pour un livre sur les arbres rouge-noir vs hachage Ce gars nommé Bob a un excellent site sur le hachage, et d'optimiser les hachages: http://burtleburtle.net/bob

Answer 4

L'ordre est non-déterministe.

À partir d' ici

Pour les fins du recensement, chaque élément dans le dictionnaire est traité comme un KeyValuePair structure représentant une valeur et sa clé. L'ordre dans lequel les articles sont retournés est pas défini.

Peut-être pour répondre à vos besoins OrderedDictionary est requis.

Answer 5

Je ne sais pas C# ou tout de .NET, mais le concept général d'un Dictionnaire, c'est que c'est une collection de paires clé-valeur.
Vous n'avez pas accès de façon séquentielle dans un dictionnaire comme vous le feriez lorsque, par exemple, le parcours d'une liste ou d'une matrice.
Vous accédez à la clé, puis de trouver si il y a une valeur pour la clé sur le dictionnaire et ce qu'il est.
Dans votre exemple, vous avez publié un dictionnaire avec les touches du clavier numérique de qui se trouvent être séquentielle, sans interruption et dans l'ordre croissant de l'insertion.
Mais peu importe l'ordre dans lequel vous insérez une valeur pour la clé '2', vous obtiendrez toujours la même valeur lors de l'interrogation de la clé '2'.
Je ne sais pas si C# permet, je suppose que oui, pour avoir la clé de types autres que des chiffres, mais dans ce cas, c'est la même chose, il n'y a pas d'ordre explicite sur les touches.
L'analogie avec la vie réelle dictionnaire pourrait être déroutant, comme les clés, qui sont les mots sont classés par ordre alphabétique afin que nous puissions les retrouver plus rapidement, mais si ce n'était pas le cas, le dictionnaire serait de travailler de toute façon, parce que la définition du mot "Aardvark" aurait le même sens, même si c'est venu après "Zebra". Penser à un roman, en revanche, modifier l'ordre des pages n'aurait pas de sens, car ils sont une collection ordonnée par essence.