Bash連想配列がインデックスの順序を維持しないのはなぜですか？

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

アイテムの順序が変わるのはなぜですか？そして、この動作をバイパスする方法は？前もって感謝します！

bash連想配列がインデックスの順序を維持しないのはなぜですか？

彼らはこれをしないように設計されているからです。

なぜアイテムの順序が変わっているのですか？

Bash連想配列の実装では、ハッシュライブラリを使用し、インデックスのハッシュを格納します。これらのハッシュは、デフォルトのバケット数が128のバケットに格納されます。ハッシュはhash_string()、単純な乗算とビット単位のXORを使用した関数で計算されます。連想配列のキーは、バケットが表示される順序で一覧表示されます。バケット数は、キーのハッシュ値とバケット数を1つ減らしたビット単位のAND演算によって計算されます。

私はbashcommit 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));
    }
}

プログラムは、キーとキーのバケット番号の2つの列を出力します（空の行を追加）。

  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を適用して要求した機能を実装することで、この動作を回避できます。

そうは言っても、私は2つの配列を使用します。

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配列に挿入した順序でキーを繰り返すことができます。

なぜアイテムの順序が変わっているのですか？

一般に連想配列は挿入順序を自然に維持しないため、ツリーベースの配列は自然な（ソートされた）順序を使用し、ハッシュマップはハッシュ関数がキーを配置する場所で使用します（セキュリティ上の理由から、プロセスごと、またはマップごとにランダム化できます）。

後者は、新しいアイテムを追加するときにアイテムの順序が変わる可能性がある理由も説明しています。新しいアイテムが既存のアイテムの間に挿入されるだけでなく、ハッシュマップのサイズを変更する必要がある場合、エントリが再ハッシュされるとシーケンス全体が「再シャッフル」されます。新しい位置に移動しました。

順序を機能として明示的に追加する（通常は二重リンクリストを使用する）か、自然に順序付けられたハッシュマップを使用する言語があります。この場合、挿入順序は維持されますが、言語で保証されていない限り、このプロパティが保持されるとは限りません。どのbashがそうではありません。

コメントによると、これはこの動作をバイパスするために行うことができます。

order=(d1 e2 m3 o4)
declare -A test2=(
    [d1]=1w45
    [e2]=2dfg
    [m3]=3df
    [o4]=4df
)
for key in ${order[@]}; { echo $key ${test2[$key]}; }

d1 1w45
e2 2dfg
m3 3df
o4 4df

またはその

declare -A test3=(
    [order]="1d 2e 3m 4o"
    [1d]=1w45
    [2e]=2dfg
    [3m]=3df
    [4o]=4df
)
for key in ${test3[order]}; { echo $key ${test3[$key]}; }

1d 1w45
2e 2dfg
3m 3df
4o 4df

もっと良い方法はありますか？

受け入れられた回答によると、更新、forループで厳密な順序が必要な場合、連想配列は正しい選択ではありません。次のようなものを使用することをお勧めします。

key=(d1   e2   m3  o4 ) 
val=(1w45 2dfg 3df 4df)

for i in ${!key[@]}; { echo ${key[$i]} ${val[$i]}
}

またはこれ

key_val=(
    "d1 1w45"
    "e2 2dfg"
    "m3 3df"
    "o4 4df")  

for item in "${key_val[@]}"; {
    sub=($item) echo ${sub[0]} ${sub[1]}
}

またはその

keys=(d1      e2      m3     o4    )
      d1=1w45 e2=2dfg m3=3df o4=4df

for key in ${keys[@]}; {
    echo $key ${!key}
}