По какому принципу определяется порядок элементов в ассоциативном массиве BASH?

Question

[dummyman]

Есть скрипт

declare -A AA
AA=()
for idx in $(seq 1 10)
do num=$(bc <<<"10^$idx")
AA+=( [$num]=$idx )
done

Вывожу результаты:

echo ${AA[@]}
# => 4 1 5 6 3 9 7 8 2 10
echo ${!AA[@]}
# => 10000 10 100000 1000000 1000 1000000000 10000000 100000000 100 10000000000

Кто-нибудь может объяснить такой порядок элементов? Откуда оно берется? Почему на разных компьютерах одинаковый результат? И дело не в необходимости сохранения порядка. Хочется выяснить по какому принципу такой порядок определяется.

Answer 1

[Андрей Мывреник]

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

К примеру, есть некая хеш-функция foo(), которая возвращает хеш в виде числа. Результаты этой функции могут быть следующими:

foo('1') = 123
foo('2') = 321
foo('3') = 12
foo('4') = 500
...

И ассоциативный массив
{'1' => a, '2' => b, '3' => c, '4' => d}
под капотом выглядит как
{12 => c, 123 => a, 321 => b, 500 => d}.
И на всех компьютерах эти результаты будут всегда одни (условно), т.к. хеш-функция, определяющая этот результат, едина. Ну и порядок ключей зависит от этого численного результата и в примере выше он будет 3 1 2 4, т.е. отсортировано по значению хеша.

См. Хеш-таблица

Answer 2

[Максим Мосейчук]

Обычная хеш-таблица не сохраняет порядок вставки элементов.

Comments

[dummyman]

А почему результат на разных компьютерах одинаковый?

[dummyman]

Тут даже дело не в том, что нужно сохранить порядок. Хочется выяснить по какому принципу определяется.

[Максим Мосейчук]

dummyman: На разных компьютерах скорее всего отличающиеся версии ПО, в которых используются различные хеш-функции.