为什么 Bash 关联数组不保持索引顺序？

Question

我正在创建关联数组以在 for 循环中进行处理，但我在索引顺序中得到了一些奇怪的结果。请看一下这个示例脚本：

#!/bin/bash
declare -A test1=(
    [d]=1w45
    [e]=2dfg
    [m]=3df
    [o]=4df
)

declare -A test2=(
    [d1]=1w45
    [e2]=2dfg
    [m3]=3df
    [o4]=4df
)

declare -A test3=(
    [1d]=1w45
    [2e]=2dfg
    [3m]=3df
    [4o]=4df
)

echo ${!test1[@]}
echo ${!test2[@]}
echo ${!test3[@]}

输出将是

$ ./test 
d e m o
o4 m3 e2 d1
3m 4o 1d 2e

为什么项目的顺序会改变？以及如何绕过这种行为？提前致谢！

Answer 1

为什么 bash 关联数组不保持索引顺序？

因为它们的设计目的不是这样做。

为什么项目的顺序会改变？

Bash关联数组实现使用哈希库并存储索引的哈希值。这些哈希值存储在默认数量为 128 个桶的桶中。哈希值是通过使用简单乘法和按位异或的函数来计算的。关联数组的键按照存储桶出现的顺序列出。桶数是通过key的哈希值与桶数减1进行按位与运算得到的。hash_string()

我编译了bash commit 6c6454cb18d7cd30b3b26d5ba6479431e599f3ed，对我来说你的脚本输出：

$ ./test 
o m e d
d1 e2 m3 o4
1d 3m 2e 4o

因此，我复制了该hash_string()函数并编写了一个小型 C 程序，该程序将输出键的存储桶编号并编译并执行：

#include <stdio.h>

#define FNV_OFFSET 2166136261
#define FNV_PRIME 16777619

unsigned int
hash_string (s)
     const char *s;
{
  register unsigned int i;

  for (i = FNV_OFFSET; *s; s++)
    {
      i *= FNV_PRIME;
      i ^= *s;
    }

  return i;
}

int main() {
    const char *s[] = {
        "o", "m", "e", "d",
        "d1", "e2", "m3", "o4",
        "1d", "3m", "2e", "4",
    };
    for (int i = 0;  i < sizeof(s)/sizeof(*s); ++i) {
        printf("%3s %3d\n",
            s[i], 
            hash_string(s[i]) & (128 - 1));
    }
}

程序输出两列，键和键的桶号（添加了额外的空行）：

  o 112
  m 114
  e 122
  d 123

 d1  16
 e2  60
 m3  69
 o4 100

 1d  14
 3m  41
 2e  50
 4o  94

输出的键的顺序是使用它们所在的哈希表中的桶的顺序进行排序的，因此它们按照该顺序输出。这就是项目顺序发生变化的原因。

也就是说，您不应该依赖这种行为，因为如果 bash 的作者决定更改哈希函数或进行任何其他更改，则键的输出顺序可能会更改。

以及如何绕过这种行为？

没有办法绕过这个。Bash 数组使用哈希表来存储哈希值。键的插入顺序不存储在任何地方。

当然，您可以通过修补bash来实现您请求的此类功能来绕过此行为。

也就是说，我只会使用两个数组：

keys=(d1 e2 m3 o4)
elements=(1w45 2dfg 3df 4df)
declare -A test2
for ((i=0;i<${#keys[@]};++i)); do
    test2[${keys[$i]}]="${elements[$i]}"
done
# or maybe something along:
declare -A test2=($(paste -zd <(printf "[%s]=\0" "${keys[@]}") <(printf "%q \0" "${elements[@]}"))

这样您就可以按照将键插入单独keys数组的顺序对其进行迭代。