Ir: ¿qué determina el orden de iteración para las claves del mapa?

Question

El Go Programming Language Specification dice:

3. El orden de iteración sobre los mapas no se especifica. [...]

Eso es de esperar ya que un tipo de mapa se puede implementar como una tabla hash, o como un árbol de búsqueda, o como alguna otra estructura de datos. ¿Pero cómo se implementa realmente map en Go?

Dicho de otra manera, lo que determina el orden de iteración de las claves en

for k, _ := range m { fmt.Println(k) } 

me empezaron a preguntarse sobre esto después de que vi que un mapa con string llaves aparentemente hacer tienen un cierto orden de iteración. Un programa como

package main 
import ("fmt"; "time"; "rand") 

func main() { 
    rand.Seed(time.Seconds()) 
    words := [...]string{"foo", "bar", "a", "b", "c", "hello", "world", 
     "0", "1", "10", "100", "123"} 
    stringMap := make(map[string]byte) 
    for i := range rand.Perm(len(words)) { 
     stringMap[words[i]] = byte(rand.Int()) 
    } 
    fmt.Print("stringMap keys:") 
    for k, _ := range stringMap { fmt.Print(" ", k) } 
    fmt.Println() 
} 

imprime el siguiente en mi máquina:

stringMap keys: a c b 100 hello foo bar 10 world 123 1 0 

independientemente del orden de inserción.

El programa equivalente con un mapa map[byte]byte también imprime las teclas en orden aleatorio, pero aquí el orden de las teclas depende de en el orden de inserción.

¿Cómo se implementa todo esto? ¿Es el map especializado para enteros y para cadenas?

Answer 1

El mapa se implementa en Ir como hashmap.

El tiempo de ejecución de Go utiliza una implementación de hashmap común que se implementa en C. Las únicas diferencias de implementación entre map[string]T y map[byte]T son: función hash, función de equivalencia y función de copia.

A diferencia de (algunos) mapas C++, los mapas Go no están completamente especializados para enteros y cadenas.

En Vaya release.r60, el orden de iteración es independiente del orden de inserción, siempre que no haya colisiones de teclas. Si hay colisiones, el orden de iteración se ve afectado por el orden de inserción. Esto es cierto independientemente del tipo de clave.No hay ninguna diferencia entre las claves del tipo string y las claves del tipo byte en este sentido, por lo que es solo una coincidencia que su programa siempre imprima las claves de cadena en el mismo orden. El orden de iteración es siempre el mismo a menos que se modifique el mapa.

Sin embargo, en el más reciente Ir liberación semanal (y en Go1 que puede esperarse para ser lanzado este mes), el orden de iteración es al azar (que comienza en una clave pseudo-aleatoriamente elegido, y el código hash el cálculo se siembra con un número pseudoaleatorio). Si compila su programa con la publicación semanal (y con Go1), el orden de iteración será diferente cada vez que ejecute su programa. Dicho esto, ejecutar su programa un número infinito de veces probablemente no imprima todas las permutaciones posibles del conjunto de claves. Ejemplo de salidas:

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 
... 

Answer 2

Si las especificaciones indican que el orden de iteración no se especifica, no se descarta un orden específico en casos específicos.

El punto es que uno no puede confiar en ese orden en ningún caso, ni siquiera en algún caso especial. La implementación es libre de cambiar este comportamiento en cualquier momento dado, incluido el tiempo de ejecución.

Answer 3

Tenga en cuenta que no es extraño que la orden sea estable independientemente del orden de inserción si hay un pedido total sobre las teclas (como suele ser si son de tipo homogéneo); si nada más, puede permitir una búsqueda eficiente sobre las claves que generan el mismo hash.

Esto también puede reflejar una implementación subyacente diferente, en particular, esto es algo que la gente podría desear para las cadenas, pero en el caso de los enteros, podría usar una matriz dispersa.