What is the order of elements in a BASH associative array?

Question

bash

There is a script

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

I output the results:

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

Can anyone explain this order of elements? Where does it come from? Why on different computers the same result? And it's not about the need to maintain order. I would like to find out on what basis such an order is determined.

Answer 1

Hash tables do not have an insertion order, and although the apparent order is not random, you should never rely on it during development. The reason why the order is the same on different computers is because the hash function is the same.
For example, there is a hash function foo()that returns a hash as a number. The results of this function may be as follows:

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

And the associative array
under the hood looks like
{12 => c, 123 => a, 321 => b, 500 => d}.
And on all computers, these results will always be the same (conditionally), because the hash function that determines this result is the same. Well, the order of the keys depends on this numerical result, and in the example above it will be 3 1 2 4, i.e. sorted by hash value.
See hash table

Answer 2

A regular hash table does not preserve the insertion order of elements.