Go: что определяет порядок итераций для ключей карты? - PullRequest
Новая
       30

Go: что определяет порядок итераций для ключей карты?

8 голосов
/ 08 марта 2012

Спецификация языка программирования Go говорит:

3. Порядок итерации по картам не указан. [...]

Этого следовало ожидать, поскольку тип карты может быть реализован в виде хеш-таблицы, или в виде дерева поиска, или в качестве некоторой другой структуры данных. Но как на самом деле map реализован в Go?

Иными словами, что определяет порядок итераций ключей в 

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

Я начал задумываться об этом после того, как увидел, что карта с string ключами, очевидно, do имеет определенный порядок итераций. Программа типа 

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()
}

печатает следующее на моей машине: 

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

независимо от порядка ввода.

Эквивалентная программа с картой map[byte]byte также печатает ключи в случайном порядке, но здесь порядок ключей зависит от порядка вставки.

Как все это реализовано? map специализируется для целых чисел и для строк?

Ответы [ 3 ]

17 голосов
/ 08 марта 2012

Карта реализована в Go как хэш-карта.

Во время выполнения Go используется общая реализация хэш-карты, которая реализована на языке C. Единственными отличиями реализации между map[string]T и map[byte]T являются: хэш-функция, функция эквивалентности и функция копирования.

В отличие от (некоторых) карт C ++, карты Go не полностью специализированы для целых чисел и для строк.

В Go release.r60 порядок итераций не зависит от порядка вставки, если нет столкновений клавиш. Если есть столкновения, порядок итераций зависит от порядка вставки. Это верно независимо от типа ключа. В этом отношении нет никакой разницы между ключами типа string и ключами типа byte, поэтому это лишь совпадение, что ваша программа всегда печатает строковые ключи в одном и том же порядке. Порядок итераций всегда один и тот же, если карта не изменена.

Однако в новейшем еженедельном выпуске Go (и в Go1 , который, как ожидается, будет выпущен в этом месяце), порядок итераций рандомизирован (он начинается с псевдо- случайным образом выбранный ключ, и вычисление хеш-кода засевается псевдослучайным числом). Если вы компилируете свою программу с еженедельным выпуском (и с Go1), порядок итераций будет отличаться при каждом запуске вашей программы. Тем не менее, запуск вашей программы бесконечное число раз, вероятно, не напечатает все возможные перестановки набора ключей. Пример выходных данных: 

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
...
2 голосов
/ 08 марта 2012

Если в спецификациях говорится, что порядок итераций не указан, то конкретный порядок в конкретных случаях не исключается.

Дело в том, что нельзя полагаться на этот порядок ни в коем случае, даже в каком-то особом случае. Реализация может изменить это поведение в любой момент, включая время выполнения.

1 голос
/ 08 марта 2012

Обратите внимание, что не так уж и странно, чтобы порядок был стабильным независимо от порядка вставки, если есть общий порядок ключей (как это часто бывает, если они однородного типа); если ничего другого, это может позволить эффективный поиск по ключам, которые генерируют тот же хеш.

Это также может отражать другую базовую реализацию - в частности, это то, что люди могут хотеть для строк, но для целых чисел вы можете использовать вместо этого разреженный массив.

...