Почему ассоциативные массивы Bash не поддерживают порядок индексов?

Question

Я создаю ассоциативные массивы для обработки в течение l oop, но я получаю некоторые странные результаты в порядке индекса. Пожалуйста, посмотрите на этот пример сценария:

#!/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 Реализация ассоциативного массива использует библиотеку ha sh и хранит хэши индексов. Эти хэши хранятся в сегментах с 128 числом по умолчанию в сегментах . Га sh рассчитывается с помощью функции hash_string() с использованием простого умножения и побитового XOR. Ключи ассоциативного массива перечислены в порядке следования появляются . Номер корзины вычисляется с помощью побитовой операции И между значением ключа ha sh и числом блоков, уменьшенным на 1.

Я скомпилировал 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

Порядок выводимых ключей сортируется с использованием порядка корзины в таблице ha sh, в которую они входят, поэтому они выводятся в таком порядке. Вот почему порядок элементов изменился.

Тем не менее, не следует полагаться на это поведение, поскольку порядок вывода ключей может измениться, если автор bash решит изменить функцию хеширования или внесите любое другое изменение.

А как обойти это поведение?

Нет способа обойти это. Массивы Bash используют таблицу ha sh для хранения хэшей. Порядок вставки ключей нигде не сохраняется.

Конечно, вы можете обойти это поведение, добавив 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.

Answer 2

Почему меняется порядок элементов?

Поскольку обычно ассоциативные массивы не естественно поддерживают порядок вставки: основанные на дереве используют естественный (отсортированный) порядок и хеш-карты используют везде, где их функция ha sh записывает ключи (которые могут быть рандомизированы для каждого процесса или даже для карты по соображениям безопасности).

Последнее также объясняет, почему порядок элементов может даже изменяться как Вы добавляете новые элементы: новые элементы могут быть вставлены не только между существующими, но когда размер хеш-карты должен быть изменен, вся последовательность будет «перетасована», поскольку записи переразмечаются и перемещаются на новую позицию.

Там являются языками, которые либо явно добавляют упорядочение в качестве функции (обычно с использованием двусвязного списка), либо используют естественно упорядоченный hashmap, в этом случае порядок вставки сохраняется, но вы не можете предполагать, что это свойство выполняется, если только язык гарантирует это. Который bash не делает.

Answer 3

Согласно комментариям это можно сделать, чтобы обойти это поведение.

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

Есть ли лучший способ?

Обновите, согласно для принятого ответа ассоциативный массив не является правильным выбором, если вам нужен строгий порядок для l oop, лучше использовать что-то вроде этого:

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}
}