Pourquoi les entrées sont-elles en plus classées dans un dictionnaire .Net?

Question

Je viens de voir ce comportement et je suis un peu surpris par cela ...

Si j'ajoute 3 ou 4 éléments à un dictionnaire, puis effectuez une " Pour chaque " pour obtenir toutes les clés, elles apparaissent dans le même ordre que je les ai ajoutées.

La raison pour laquelle cela me surprend est qu'un dictionnaire est censé être un HashTable en interne, alors je m'attendais à ce que les choses sortent dans TOUT ordre (ordonné par le hachage de la clé, non?)

Qu'est-ce qui me manque ici? Est-ce un comportement sur lequel je peux compter?

EDIT: OK, je pensais déjà aux nombreuses raisons pour lesquelles cela pourrait se produire (comme la liste séparée des entrées, qu’il s’agisse d’une coïncidence, etc.). Ma question est la suivante: est-ce que quelqu'un sait comment cela fonctionne vraiment?

Answer 1

Si vous utilisez .NET Reflector sur les bibliothèques de classe 3.5, vous pouvez constater que l’implémentation de Dictionary stocke les éléments dans un tableau (qui est redimensionné en fonction des besoins) et que des index de hachage sont insérés dans ce tableau. Lors de l'obtention des clés, il ignore complètement la table de hachage et effectue une itération sur le tableau d'éléments. Pour cette raison, vous verrez le comportement que vous avez décrit depuis que de nouveaux éléments sont ajoutés à la fin du tableau. Cela ressemble à ce que vous faites comme suit:

add 1
add 2
add 3
add 4
remove 2
add 5

vous obtiendrez 1 5 3 4 car il réutilise les emplacements vides.

Il est important de noter que, comme beaucoup d’autres, vous ne pouvez pas compter sur ce comportement dans les versions futures (ou antérieures). Si vous souhaitez que votre dictionnaire soit trié, il existe une classe SortedDictionary pour cet objectif.

Answer 2

Un dictionnaire récupère les éléments dans un ordre haché. Le fait qu'ils soient sortis dans l'ordre d'insertion était une coïncidence totale.

La documentation MSDN indique:

  

L'ordre des clés dans KeyCollection n'est pas spécifié, mais il s'agit du même ordre que celui des valeurs associées dans ValueCollection renvoyé par la propriété Values.

Answer 3

Vous ne pouvez pas compter sur ce comportement, mais ce n'est pas surprenant.

Réfléchissez à la manière dont vous implémenteriez l'itération de clé pour une table de hachage simple. Vous auriez besoin de parcourir tous les seaux de hachage, qu'ils aient ou non quelque chose dans ceux-ci. Obtenir un petit ensemble de données à partir d'une grande table de hachage peut s'avérer inefficace.

Par conséquent, il pourrait être judicieux de conserver une liste de clés dupliquée distincte. En utilisant une liste à double liaison, vous obtenez toujours une insertion / suppression en temps constant. (Vous garderiez un pointeur du panier de la table de hachage dans cette liste.) De cette manière, l'itération dans la liste des clés dépend uniquement du nombre d'entrées, pas du nombre de compartiments.

Answer 4

Je pense que cela provient de l'ancien .NET 1.1 fois où vous aviez deux types de dictionnaires & "ListDictionary &"; et & "; HybridDictionary &"; ListDictionary était un dictionnaire implémenté en interne en tant que liste ordonnée et a été recommandé pour " petits ensembles d'entrées " ;. Ensuite, vous deviez HybridDictionary , qui était initialement organisée en interne sous forme de liste, mais si elle devenait plus grande qu'un seuil configurable, elle deviendrait une table de hachage. Cela a été fait parce que des dictionnaires historiquement corrects basés sur le hachage étaient considérés comme coûteux. Maintenant, un jour qui n’a pas beaucoup de sens, mais je suppose. .NET vient de fonder sa nouvelle classe générique Dictionary sur l’ancien HybridDictionary.

Remarque : Quoi qu'il en soit, comme quelqu'un l'a déjà souligné, vous ne devez jamais compter sur l'ordre du dictionnaire pour rien

.

Answer 5

Citation de MSDN :

  

L'ordre des clés dans le   Dictionnaire & Lt; (Of & Lt; (TKey,   TValue & Gt;) & Gt;). KeyCollection est   non spécifié, mais c'est le même ordre   comme les valeurs associées dans le   Dictionnaire & Lt; (Of & Lt; (TKey,   TValue & Gt;) & Gt;). ValueCollection   retourné par le dictionnaire < (Of < (TKey,   TValue & Gt;) & Gt;). Propriété Values.

Answer 6

Quelles clés avez-vous ajoutées dans votre test et dans quel ordre?

Answer 7

Vos entrées peuvent toutes se trouver dans le même panier de hachage dans le dictionnaire. Chaque compartiment est probablement une liste d'entrées dans le compartiment. Cela expliquerait les entrées qui reviennent dans l'ordre.

Answer 8

D'après ce que je sais, cela ne devrait pas être un comportement sur lequel compter. Pour le vérifier rapidement, utilisez les mêmes éléments et modifiez l'ordre dans lequel vous les ajoutez au dictionnaire. Vous verrez si vous les récupérez dans l'ordre dans lequel ils ont été ajoutés, ou ce n'était qu'une coïncidence.

Answer 9

Jusqu'à une certaine taille de liste, il est moins coûteux de vérifier chaque entrée au lieu de procéder au hachage. C’est probablement ce qui se passe.

Ajoutez 100 ou 1000 éléments et vérifiez s’ils sont toujours dans le même ordre.

Answer 10

Je déteste ce genre de " de par sa conception " fonctionnalités. Je pense que lorsque vous donnez à votre classe un nom générique tel que & "Dictionnaire &", Il devrait également se comporter comme & "Comme prévu" & "; Par exemple, std :: map conserve toujours ses valeurs-clés triées.

Edit: apparemment, la solution consiste à utiliser SortedDictionary, qui se comporte de la même manière que std :: map.

Answer 11

La question et de nombreuses réponses semblent mal comprendre le but d’une table de hachage ou d’un dictionnaire. Ces structures de données n'ont aucun comportement spécifié en ce qui concerne l'énumération des valeurs (ou en fait des clés) des éléments contenus dans la structure de données.

Le but d'un dictionnaire ou d'une table de hachage est de pouvoir rechercher efficacement une valeur spécifique à partir d'une clé connue. L'implémentation interne de tout dictionnaire ou table de hachage devrait fournir cette efficacité de recherche mais ne doit pas fournir de comportement spécifique en ce qui concerne les énumérations ou les & Quot; tapez des itérations sur les valeurs ou les clés.

En bref, la structure de données interne peut stocker et énumérer ces valeurs comme bon lui semble, y compris l'ordre dans lequel elles ont été insérées.