Le Go Programmation Language Specification dit:
3. L'ordre d'itération sur les cartes n'est pas spécifiée. [...] p> Blockquote>
C'est à prévoir car un type de carte peut être mis en œuvre comme une table de hachage, ou comme un arbre de recherche, ou une autre structure de données. Mais comment est
carte code> effectivement mis en œuvre Go? P>En d'autres termes, ce qui détermine l'ordre d'itération des clés dans p>
stringMap keys: a c b 100 hello foo bar 10 world 123 1 0
4 Réponses :
Si les spécifications disent que l'ordre d'itération n'est pas spécifié, un ordre spécifique dans des cas spécifiques n'est pas exclu.
Le point est que l'on ne peut pas compter sur cet ordre dans aucun cas, pas même dans un cas particulier. La mise en œuvre est libre de changer ce comportement à un moment donné, le temps d'exécution inclus.
Je sais que l'ordre ne peut pas être invoqué et que c'est bon qu'il y a une commande, même si la spécification ne le définisse pas.
Notez qu'il n'est pas si étrange pour pouvoir être stable, quelle que soit la commande d'insertion s'il y a une commande totale sur les touches (comme il peut être fréquemment possible si elles sont de type homogène); Si rien d'autre, il peut permettre une recherche efficace sur les touches qui génèrent le même hachage.
Ceci pourrait également refléter également une implémentation sous-jacente différente - en particulier, il s'agit de quelque chose que les gens peuvent vouloir pour des chaînes, mais pour des entiers, vous pouvez utiliser un tableau rare à la place.
Oui, je ne suis pas vraiment surpris qu'il y ait un ordre stable. Je suis plus surpris que la commande soit indépendante de l'insertion pour les chaînes et non pour les entiers.
@Martinsisler Ceci pourrait bien refléter une implémentation sous-jacente différente; En particulier, c'est quelque chose que les gens peuvent vouloir pour les chaînes, mais pour les entiers, vous pouvez utiliser un tableau de race.
la carte est implémentée dans Go sous forme de hashmap.
Le temps d'exécution Go utilise une implémentation commune de HASHMAP qui est implémentée dans C. Les seules différences de mise en œuvre entre Contrairement à (certains) C ++ cartes, go Les cartes ne sont pas entièrement spécialisées pour les entiers et pour les chaînes. dans Toutefois, dans la dernière MAP [String] t code> et Carte [Byte] T Code> sont: Fonction de hachage, fonction d'équivalence et fonction de copie. P> chaîne code> et des touches de type octet code> à cet égard, ce n'est donc qu'une coïncidence que votre programme imprimait toujours les clés de chaîne dans le même ordre . L'ordre d'itération est toujours le même si la carte n'est modifiée que si la carte n'est modifiée. P> stringMap keys: b 0 hello c world 10 1 123 bar foo 100 a
stringMap keys: hello world c 1 10 bar foo 123 100 a b 0
stringMap keys: bar foo 123 100 world c 1 10 b 0 hello a
...
Merci pour les idées! Il est agréable de savoir que Go 1 va randomiser cela car il est beaucoup plus facile de trouver des cas où vous vous trouvez sur l'ordre clé par erreur.
@dystoy Les codes source C: code.google.com/p/go/source/browse/src/pkg/runtime/... code.google.com/p/go/source/browse/src/pkg/Runtime/ ...
Merci, c'est un code intéressant. Pas le genre de code hashmap que je suis utilisé aussi, celui-ci a besoin de plus de quelques minutes à analyser:
@Dystroy Oui, le code est un peu atypique. Un autre problème intéressant serait de vérifier que la mise en œuvre de HASHMAP est sûre: Go est une langue sûre, mais elle permet également de lire / écrit simultanément sur la même carte. Parce que Go est en sécurité, le programmeur ne devrait pas être en mesure d'inventer un pointeur arbitraire en raison de laquelle le programme pourrait se bloquer ou être vulnérable du point de vue de la sécurité. Il serait faux du code qui insère des paires de clés à utiliser pour utiliser memcpy () .
Pour prolonger @ user811773 réponse. Une gamme code> semi-aléatoire code> L'itération ne signifie pas que les chances de renvoyer chaque élément dans une carte code> est également égale. Voir https://medium.com/I0Exception/map-itération-in-go -275ABB76F721 et https://play.golang.org/p/gpsd8i7xzog .
package main
import "fmt"
type intSet map[int]struct{}
func (s intSet) put(v int) { s[v] = struct{}{} }
func (s intSet) get() (int, bool) {
for k := range s {
return k, true
}
return 0, false
}
func main() {
s := make(intSet)
for i := 0; i < 4; i++ {
s.put(i)
}
counts := make(map[int]int)
for i := 0; i < 1024*1024; i++ {
v, ok := s.get()
if !ok {return}
counts[v]++
}
for k, v := range counts {
fmt.Printf("Value: %v, Count: %v\n", k, v)
}
}
/*
Value: 1, Count: 130752
Value: 2, Count: 130833
Value: 0, Count: 655840
Value: 3, Count: 131151
*/