Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

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

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?
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...