Pourquoi le tableau de Ruby de 1000 paires de clés et de valeurs de hachages est toujours dans un ordre particulier?

Question

Say s'il y a un tableau de 1000 hash, avec des paires comme {:id => 1, :name => 'something', :created_at => '2010-08-18'}

lorsque j'utilise une boucle pour imprimer ces 1000 dossiers, soi-disant, la paire de clés de hachage/valeur de l'ordre n'est pas garantie, mais l'impression de la table, elle apparaît toujours dans le même ordre. Pourquoi est-ce et peut-il être compté? Sinon, quelle est la bonne méthode pour trier les paires clé/valeur?

(je pensais à la cartographie :id to 10, and :name to 20, and :create_at to 30, puis trier les clés de ces valeurs mappées, de sorte que: id est avant: nom, et est avant: created_at)

(le hachage est imprimé par a_hash.each_pair do |k, v| ...)

Answer 1

La mise en page du hachage est déterministe. Donc, pour une version particulière de ruby, si vous ajoutez/supprimez toujours les clés d'un hachage dans le même ordre, la disposition du hachage sera la même. Cela signifie que l'itération sur les hachages de votre tableau aura toutes les clés dans le même ordre.

Answer 2

Ruby hashmaps (et hashmaps en général) ne sont pas ordonnés implicite de clés. Ils sont cependant implémentés de manière à ce que la récupération d'une valeur donnée à une clé soit une opération efficace (temps O (1) amorti).

Ainsi, dans la mise en œuvre sous-jacente, les clés sont toujours structurées de la même manière, ce qui les rend semblent avoir un ordre.

Answer 3

Ruby ne garantit pas l'ordre des clés de hachage, bien que Ruby 1.9 ne conserve l'ordre d'insertion.

Si vous voulez traiter une des clés de hachage dans un ordre spécifique, mais arbitraire, la meilleure façon est de créer un tableau spécifiant l'ordre. Donc, vous pourriez avoir un tableau comme [:id, :name, :create_at]. Si vous voulez traiter un Hash dans, disons, l'ordre alphabétique, vous pouvez simplement utiliser sort et il vous donnera un tableau des paires clé-valeur dans l'ordre.

Answer 4

Pourquoi est-ce et peut-on compter?

Tout hachage va avoir un "tri naturel".

A « tri naturel » est soit maintenu soit en tant que chaque élément est inséré ou est réalisée avant la première recherche.

S'il n'y a pas de tri naturel renvoyé, une valeur correspondant à une clé particulière nécessiterait une recherche exhaustive.

Une recherche exhaustive, bien sûr, prendrait n comparaisons où n est le nombre d'éléments dans le hachage. (Par exemple 65536 éléments fouillés 65536 comparaisons.)

D'autre part, si un hachage est trié Dans l'ordre alphabétique, une recherche binaire peut trouver une correspondance dans les comparaisons LOG2 (n). (Par exemple 65536 éléments recherchés dans 16 comparaisons.)

Il existe d'autres méthodes de tri, mais elles nécessitent toutes un tri initial. Ce type peut être un système avec un index caché qui laisse les éléments de paire clé/valeur non triés.

par exemple. Dans l'implémentation partielle suivante, les paires clé/valeur sont stockées en tant qu'objets dans un tableau sous-jacent.

myArray[0] = {"b", "Skies"} 
myArray[1] = {"c", "dog"} 
myArray[2] = {"a", "Jax"} 
myArray[3] = {"d", "gone"} 
myArray[4] = {"r", "run"} 
myArray[5] = {"q", "quit"} 

un second réseau, auquel le développeur Ruby n'a pas accès, détient le genre.

sortArray[0] = 2 
sortArray[1] = 0 
sortArray[2] = 1 
sortArray[3] = 3 
sortArray[4] = 4 
sortArray[5] = 5 

Ainsi, en interne à l'objet de hachage

for(i=0 to 5) 
    print myArray[sortArray[i]] 

imprimerait le tableau trié.

La spécification de Ruby ne spécifie apparemment pas la méthode à utiliser, le tri par clé, un tri caché, ou une autre méthode, donc, non, vous ne pouvez pas compter sur le tri naturel.

Answer 5

Le documentation à ruby-doc.org pour Ruby 1.9 (pas sûr si elle est 1.9.0 ou 1.9.1) dit de façon incorrecte

L'ordre dans lequel vous traversez un hachage soit par clé ou une valeur peut sembler arbitraire, et ne sera généralement pas dans l'ordre d'insertion.

Mais 1.9.1 nouvelles says

Hash préserve l'ordre. Il énumère ses éléments dans l'ordre dans lequel les clés sont insérées.

J'ai eu un regard sur le tronc de rubis (ce qui est en cours d'élaboration), et il dit

Hashes énumèrent leurs valeurs dans l'ordre que les clés ont été insérées correspondantes.

Le changement à la documentation était dans un September 25, 2009 commit qui réparait la documentation incorrecte.

Je ne suis pas sûr à 100% qu'une énumération ordonnée fait partie de la spécification de ruby ​​1.9.1. Rubyspec serait une façon de vérifier. Mais si la mise en œuvre principale donne un contrat, alors vous vous attendez à ce que toute autre implémentation honore ce contrat à moins qu'il ne le dise explicitement.