long - if golang

Orden de asignación de Google Go Lang

Question

En un ejemplo de Go si pongo lo siguiente:

package main

import "fmt"

type Vertex struct {
    Lat, Long float64
}

var m map[string]Vertex

func main() {
    m = make(map[string]Vertex)
    m["Bell Labs"] = Vertex{
        40.68433, 74.39967,
    }
    m["test"] = Vertex{
        12.0, 100,
    }
    fmt.Println(m["Bell Labs"])
    fmt.Println(m)
}

Escupe:

{40.68433 74.39967}

mapa [Bell Labs: {40.68433 74.39967} prueba: {12 100}]

Sin embargo, si cambio UNA parte menor de la declaración Vertex de prueba de la siguiente manera:

m["test"] = Vertex{
    12.0, 100,
}

produce lo siguiente:
{40.68433 74.39967}

mapa [test: {12 100} Bell Labs: {40.68433 74.39967}]

¿¿El cambio?? Me mudé a la derecha "}" 4 espacios. ¿Por qué diablos afecta el orden de mi mapa?

Gracias por cualquier respuesta / ideas

Answer 1

El "orden" del mapa depende de la función hash utilizada. La función hash se aleatoriza para evitar ataques de denegación de servicio que usan colisiones hash. Consulte el rastreador de problemas para obtener más detalles:

http://code.google.com/p/go/issues/detail?id=2630

El orden del mapa no está garantizado de acuerdo con la especificación. Aunque no se haya realizado en las implementaciones de go actual, una implementación futura podría compactarse durante el GC u otra operación que cambie el orden de un mapa sin que el código lo modifique. No es prudente suponer una propiedad no definida en la especificación.

Un mapa es un grupo desordenado de elementos de un tipo, llamado tipo de elemento, indexado por un conjunto de claves únicas de otro tipo, llamado tipo de clave.

Answer 2

Un mapa no siempre debe imprimir su elemento clave en un orden fijo:
Consulte " Ir: ¿qué determina el orden de iteración para las claves del mapa? "

Sin embargo, en la versión semanal más reciente de Go (y en Go1, que se espera que se lance este mes), el orden de iteración se aleatoriza (comienza en una clave pseudoaleatoriamente elegida, y el cómputo de código hash se inocula con un pseudoaleatorio número).
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.

Sin embargo, no está exactamente escrito así en la especificación ( Tipo de mapa de referencia ):

Un mapa es un grupo desordenado de elementos de un tipo, llamado tipo de elemento, indexado por un conjunto de claves únicas de otro tipo, llamado tipo de clave.

En realidad, las especificaciones sí lo deletrean, pero en la sección de enunciado For :

El orden de iteración sobre los mapas no se especifica y no se garantiza que sea el mismo de una iteración a la siguiente .

• Si las entradas del mapa que aún no se han alcanzado se eliminan durante la iteración, los valores de iteración correspondientes no se producirán.
• Si las entradas del mapa se insertan durante la iteración, el comportamiento depende de la implementación, pero los valores de iteración para cada entrada se producirán como máximo una vez.
• Si el mapa es nulo, el número de iteraciones es 0.

Esto ha sido introducido por el código de revisión 5285042 en octubre de 2011:

tiempo de ejecución: desplazamiento aleatorio para la iteración del mapa

El hilo de las nueces indica:

La razón por la cual "está ahí para evitar que la gente haga cosas malas" parecía particularmente débil.
Evitar colisiones de hash malintencionadas tiene mucho más sentido .
Además, el puntero al código permite, en el desarrollo, revertir ese comportamiento en el caso de que haya un error intermitente que sea difícil de resolver.

A lo que Patrick Mylund Nielsen responde:

La nota de Dan fue en realidad el principal argumento de por qué los desarrolladores de Python se mostraron reacios a adoptar la asignación al azar de hash IV: ¡rompió sus pruebas unitarias! Finalmente, PHP optó por no hacerlo y, en su lugar, limitó el tamaño del encabezado http.Request , y Oracle y otros no pensaron que se http.Request un problema de idioma.
Perl vio el problema y aplicó una solución similar a la de Go, que se incluyó en Perl 5.8.1 en 2003.
Podría estar equivocado, pero creo que fueron los únicos a los que realmente les importó cuando se presentó este documento: " Denegación de servicio mediante ataques de complejidad algorítmica ", atacando las tablas hash.

(Peores colisiones de tablas hash)

Para otros, esto, que se hizo muy popular hace un año, fue un buen motivador:
" 28c3: ataques efectivos de denegación de servicio contra plataformas de aplicaciones web (video de YouTube, diciembre de 2011) ", que muestra cómo un error común en la implementación de la mayoría de los lenguajes y plataformas de programación web populares (incluidos PHP, ASP.NET, Java, etc.) se puede (ab) utilizar para obligar a los servidores de aplicaciones web a usar el 99% de la CPU durante varios minutos u horas para una sola solicitud HTTP.
Este ataque es en su mayoría independiente de la aplicación web subyacente y solo se basa en un hecho común de cómo funcionan normalmente los servidores de aplicaciones web.