bash - Do keys ${!a[@]} and values ${a[@]} of associative arrays expand in the same order?

Question

In bash, associative arrays (also known as dictionaries or hash maps) are unordered. For the associative array a we can list all keys (also known as indices) with ${!a[@]} and all values with ${a[@]}. I know that these constructs do not expand in a fixed order. I wondered if there are at least some guarantees. I couldn't find any. However, it seems unrealistic that [ "${a[*]}" = ${a[*]} ] will fail in any implementation. Likewise, it seems that ${!a[@]} expands in the same order as ${a[@]}. If we find key x at position n in ${!a[@]} then we will find value ${a[x]} at position n in ${a[@]} too. Of course we assume that a is not modified between the expansions of ${!a[@]} and ${a[@]}.

Example:

declare -A a=([x]=1 [y]=2 [z]=3)
printf %s\n "${!a[*]}" "${a[*]}"

# As output I would expect one of the following blocks ...
# (corresponding keys and values are in the same column)
x y z    x z y    y x z    y z x    z x y    z y x
1 2 3    1 3 2    2 1 3    2 3 1    3 1 2    3 2 1

# ... but never something like ...
# (at least one key doesn't share a column with its value)
x y z    x y z    y x z
1 3 2    2 3 1    2 3 1    ...

Question

• For any existing bash version and associative array a, could ${!a[@]} and ${a[@]} expand in such a way that keys and and their corresponding values have a different order? In other words:

# Are there values for a and i
# such that this script could print "different order"
declare -A a=(...)
declare -i i=...
keys=("${!a[@]}")
values=("${a[@]}")
[ "${a[keys[i]]}" != "${values[i]}" ] && echo "different order"

Bonus Questions

• Are there any guarantees on the expansion orders of ${!a[*]} and ${a[@]} in bash's manual or some other official document?
• Can we assume further/other guarantees from the implementation itself? Did some of these guarantees change with different versions of bash? Are some of these guarantees likely to change in upcoming versions of bash?

Answer 1

I'm not seeing any mention of associative array's key ordering in the bash manpage (I'm using 4.3.48). Seeing the source code of bash 5.0 (hashlib.c) also shows that bash uses the simplest hashing XOR-based algorithm without any randomization, so the order should not be randomized between processes or machines, unlike some other more sophisticated algorithms you'd find in, say, Perl.

That being said, it's still unwise to depend on particular key ordering or on the order being constant, as the experience in Perl-land taught us. Moreover, since the bash manpage doesn't say about ordering, there's no guarantee. The hash implementation could be replaced or rewritten anytime.