Как определить хеш-таблицы в Bash?

557

Что эквивалентно словарям Python, но в Bash (должно работать в OS X и Linux).

Шридхар Ратнакумар
источник
4
Пусть bash запустит скрипт на python / perl ... Это так гибко!
e2-e4
Попробуйте использовать xonsh (это на github).
Оливер

Ответы:

939

Баш 4

Bash 4 изначально поддерживает эту функцию. Убедитесь, что ваш скрипт имеет хэшбэнг, #!/usr/bin/env bashили #!/bin/bashвы его не используете sh. Убедитесь, что вы выполняете сценарий напрямую или выполняете scriptс помощью bash script. (Не на самом деле выполнение сценарий Bash с Bash действительно произойдет, и будет очень запутанные!)

Вы объявляете ассоциативный массив, выполняя:

declare -A animals

Вы можете заполнить его элементами, используя обычный оператор присваивания массива. Например, если вы хотите иметь карту animal[sound(key)] = animal(value):

animals=( ["moo"]="cow" ["woof"]="dog")

Или объединить их:

declare -A animals=( ["moo"]="cow" ["woof"]="dog")

Затем используйте их как обычные массивы. использование

  • animals['key']='value' установить значение

  • "${animals[@]}" расширить значения

  • "${!animals[@]}"(обратите внимание !), чтобы расширить ключи

Не забудьте процитировать их:

echo "${animals[moo]}"
for sound in "${!animals[@]}"; do echo "$sound - ${animals[$sound]}"; done

Баш 3

До bash 4 у вас не было ассоциативных массивов. Не используйте, evalчтобы подражать им . Избегайте , evalкак чумы, потому что это чума сценариев оболочки. Наиболее важной причиной является то, что evalваши данные обрабатываются как исполняемый код (есть и много других причин).

Прежде всего : рассмотрите возможность обновления до bash 4. Это значительно облегчит вам весь процесс.

Если есть причина, по которой вы не можете выполнить обновление, declareэто гораздо более безопасный вариант. Он не оценивает данные так, как это evalделает bash-код , и поэтому не позволяет легко вводить произвольный код.

Давайте подготовим ответ, введя понятия:

Во-первых, косвенность.

$ animals_moo=cow; sound=moo; i="animals_$sound"; echo "${!i}"
cow

Во- вторых, declare:

$ sound=moo; animal=cow; declare "animals_$sound=$animal"; echo "$animals_moo"
cow

Соберите их вместе:

# Set a value:
declare "array_$index=$value"

# Get a value:
arrayGet() { 
    local array=$1 index=$2
    local i="${array}_$index"
    printf '%s' "${!i}"
}

Давайте использовать это:

$ sound=moo
$ animal=cow
$ declare "animals_$sound=$animal"
$ arrayGet animals "$sound"
cow

Примечание: declareнельзя вставить в функцию. Любое использование declareвнутри функции Баша превращает переменную она создает локальную в рамки этой функции, то есть мы не можем получить доступ или изменить глобальные массивы с ним. (В bash 4 вы можете использовать объявление -g для объявления глобальных переменных - но в bash 4 вы можете использовать ассоциативные массивы в первую очередь, избегая этого обходного пути.)

Резюме:

  • Обновите до bash 4 и используйте declare -Aдля ассоциативных массивов.
  • Используйте declareопцию, если вы не можете обновить.
  • Попробуйте использовать awkвместо этого и избежать проблемы в целом.
lhunath
источник
1
@Richard: Предположительно, вы не используете bash. Является ли ваш хэшбанг sh вместо bash, или вы по-другому вызываете свой код с помощью sh? Попробуйте поставить это прямо перед объявлением: echo "$ BASH_VERSION $ POSIXLY_CORRECT", должно получиться, 4.xа не так y.
lhunath
5
Невозможно обновить: единственная причина, по которой я пишу скрипты на Bash, заключается в переносимости «запускай куда угодно». Так что опора на неуниверсальную особенность Bash исключает этот подход. Который является позором, потому что иначе это было бы отличным решением для меня!
Стив Питчерс
3
Обидно, что по умолчанию OSX по-прежнему использует Bash 3, поскольку для многих это «по умолчанию». Я думал, что пугающий ShellShock мог быть толчком, в котором они нуждались, но, очевидно, нет.
Кен
13
@ken это проблема лицензирования. Bash на OSX застрял в последней сборке без лицензии GPLv3.
января
2
... или sudo port install bashдля тех (мудро, IMHO), которые не хотят делать каталоги в PATH для всех пользователей, доступных для записи без явного повышения привилегий для каждого процесса.
Чарльз Даффи
125

Есть подстановка параметров, хотя это может быть и без ПК ... как косвенное обращение.

#!/bin/bash

# Array pretending to be a Pythonic dictionary
ARRAY=( "cow:moo"
        "dinosaur:roar"
        "bird:chirp"
        "bash:rock" )

for animal in "${ARRAY[@]}" ; do
    KEY="${animal%%:*}"
    VALUE="${animal##*:}"
    printf "%s likes to %s.\n" "$KEY" "$VALUE"
done

printf "%s is an extinct animal which likes to %s\n" "${ARRAY[1]%%:*}" "${ARRAY[1]##*:}"

BASH 4, конечно, лучше, но если вам нужен взлом ... подойдет только взлом. Вы можете искать массив / хэш с подобными методами.

Bubnoff
источник
5
Я хотел бы изменить это, чтобы VALUE=${animal#*:}защитить случай, когдаARRAY[$x]="caesar:come:see:conquer"
Гленн Джекман
2
Также полезно помещать двойные кавычки вокруг $ {ARRAY [@]} в случае, если в ключах или значениях есть пробелы, как вfor animal in "${ARRAY[@]}"; do
devguydavid
1
Но разве эффективность не очень низкая? Я думаю O (n * m), если вы хотите сравнить с другим списком ключей, вместо O (n) с правильными хэш-картами (поиск с постоянным временем, O (1) для одного ключа).
CodeManX
1
Идея заключается не столько в эффективности, сколько в понимании / чтении для тех, кто имеет опыт работы с perl, python или даже bash 4. Позволяет писать аналогичным образом.
Бубнофф
1
@CoDEmanX: это взлом , умный и элегантный, но все еще рудиментарный обходной путь, чтобы помочь бедным душам, которые все еще застряли в 2007 году с Bash 3.x. Вы не можете ожидать «правильных хэш-карт» или соображений эффективности в таком простом коде.
MestreLion
85

Вот что я искал здесь:

declare -A hashmap
hashmap["key"]="value"
hashmap["key2"]="value2"
echo "${hashmap["key"]}"
for key in ${!hashmap[@]}; do echo $key; done
for value in ${hashmap[@]}; do echo $value; done
echo hashmap has ${#hashmap[@]} elements

Это не работает для меня с Bash 4.1.5:

animals=( ["moo"]="cow" )
aktivb
источник
2
Обратите внимание, что значение может не содержать пробелов, в противном случае вы добавляете больше элементов одновременно
rubo77
6
Upvote для синтаксиса hashmap ["key"] = "value", который я тоже нашел отсутствующим в другом фантастически принятом ответе.
Томанский
@ rubo77 ключ ни один, он добавляет несколько ключей. Есть ли способ обойти это?
Xeverous
25

Вы можете дополнительно изменить интерфейс hput () / hget (), чтобы хэши назывались следующим образом:

hput() {
    eval "$1""$2"='$3'
}

hget() {
    eval echo '${'"$1$2"'#hash}'
}

а потом

hput capitals France Paris
hput capitals Netherlands Amsterdam
hput capitals Spain Madrid
echo `hget capitals France` and `hget capitals Netherlands` and `hget capitals Spain`

Это позволяет вам определять другие карты, которые не конфликтуют (например, «rcapitals», которая выполняет поиск страны по столице). Но, так или иначе, я думаю, вы обнаружите, что все это довольно ужасно с точки зрения производительности.

Если вы действительно хотите быстрый поиск хеша, есть ужасный, ужасный хак, который действительно работает очень хорошо. Это так: запишите ваш ключ / значения во временный файл, по одному на строку, а затем используйте 'grep "^ $ key"', чтобы получить их, используя каналы с cut или awk или sed или что-то еще для получения значений.

Как я уже сказал, это звучит ужасно, и звучит так, как будто оно должно быть медленным и выполнять все виды ненужных операций ввода-вывода, но на практике это очень быстро (кеш диска - это круто, не правда ли?), Даже для очень большого хэша столы. Вы должны сами установить уникальность ключа и т. Д. Даже если у вас всего несколько сотен записей, комбинация выходного файла / grep будет немного быстрее - по моему опыту, в несколько раз быстрее. Это также ест меньше памяти.

Вот один из способов сделать это:

hinit() {
    rm -f /tmp/hashmap.$1
}

hput() {
    echo "$2 $3" >> /tmp/hashmap.$1
}

hget() {
    grep "^$2 " /tmp/hashmap.$1 | awk '{ print $2 };'
}

hinit capitals
hput capitals France Paris
hput capitals Netherlands Amsterdam
hput capitals Spain Madrid

echo `hget capitals France` and `hget capitals Netherlands` and `hget capitals Spain`
Аль П.
источник
1
Большой! Вы можете даже повторить это: для i в $ (compgen -A переменная capitols); сделать hget "$ i" "" сделано
zhaorufei
22

Просто используйте файловую систему

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

Создание хэш-таблицы

hashtable=$(mktemp -d)

Добавить элемент

echo $value > $hashtable/$key

Читать элемент

value=$(< $hashtable/$key)

Представление

Конечно, его медленно, но не , что медленно. Я протестировал его на своей машине, с SSD и btrfs , и он делает около 3000 элементов чтения / записи в секунду .

lovasoa
источник
1
Какая версия Bash поддерживает mkdir -d? (Не 4.3, на Ubuntu 14. Я бы прибегнул mkdir /run/shm/fooили, если бы это заполнило ОЗУ mkdir /tmp/foo.)
Камиль Гудесюн
1
Возможно, mktemp -dимелось ввиду вместо этого?
Рейд Эллис
2
Любопытно, в чем разница между $value=$(< $hashtable/$key)и value=$(< $hashtable/$key)? Спасибо!
Хелин Ван
1
"проверил это на моей машине". Это звучит как отличный способ прожечь дыру в вашем SSD. Не все дистрибутивы Linux используют tmpfs по умолчанию.
kirbyfan64sos
Я обрабатываю около 50000 хешей. Perl и PHP делают это за пол секунды. Узел за 1 секунду и что-то. Опция FS звучит медленно. Однако можем ли мы как-то убедиться, что файлы существуют только в оперативной памяти?
Rolf
14
hput () {
  eval hash"$1"='$2'
}

hget () {
  eval echo '${hash'"$1"'#hash}'
}
hput France Paris
hput Netherlands Amsterdam
hput Spain Madrid
echo `hget France` and `hget Netherlands` and `hget Spain`

$ sh hash.sh
Paris and Amsterdam and Madrid
DigitalRoss
источник
31
Вздох, это кажется излишне оскорбительным и в любом случае неточным. Никто не помещал бы проверку ввода, экранирование или кодирование (см. Я действительно знаю) в кишки хэш-таблицы, а скорее в обертку и как можно скорее после ввода.
DigitalRoss
@DigitalRoss вы можете объяснить, что такое использование #hash в eval echo '$ {hash' "$ 1" '# hash}' . для меня это кажется мне комментарием не более того. здесь #hash имеет какое-то особое значение?
Санджай
@Sanjay ${var#start}удаляет текст старт с начала значения , хранящегося в переменной Var .
jpaugh
11

Рассмотрим решение с использованием встроенного чтения bash, как показано во фрагменте кода из сценария брандмауэра ufw, который следует ниже. Этот подход имеет то преимущество, что использует столько разделенных наборов полей (а не только 2), сколько необходимо. Мы использовали | разделитель, потому что спецификаторам диапазона портов может потребоваться двоеточие, то есть 6001: 6010 .

#!/usr/bin/env bash

readonly connections=(       
                            '192.168.1.4/24|tcp|22'
                            '192.168.1.4/24|tcp|53'
                            '192.168.1.4/24|tcp|80'
                            '192.168.1.4/24|tcp|139'
                            '192.168.1.4/24|tcp|443'
                            '192.168.1.4/24|tcp|445'
                            '192.168.1.4/24|tcp|631'
                            '192.168.1.4/24|tcp|5901'
                            '192.168.1.4/24|tcp|6566'
)

function set_connections(){
    local range proto port
    for fields in ${connections[@]}
    do
            IFS=$'|' read -r range proto port <<< "$fields"
            ufw allow from "$range" proto "$proto" to any port "$port"
    done
}

set_connections
AsymLabs
источник
2
@CharlieMartin: чтение - очень мощная функция, которая используется многими программистами bash недостаточно. Это позволяет выполнять компактные формы обработки списков, похожих на шрифты. Например, в приведенном выше примере мы можем удалить только первый элемент и сохранить остальные (т. IFS=$'|' read -r first rest <<< "$fields"
Е.
6

Я согласен с @lhunath и другими, что ассоциативный массив - это путь к Bash 4. Если вы застряли в Bash 3 (OSX, старые дистрибутивы, которые вы не можете обновить), вы можете использовать также expr, который должен быть везде, строку и регулярные выражения. Мне особенно нравится, когда словарь не слишком большой.

  1. Выберите 2 разделителя, которые вы не будете использовать в ключах и значениях (например, ',' и ':')
  2. Напишите вашу карту в виде строки (обратите внимание на разделитель ',' также в начале и в конце)

    animals=",moo:cow,woof:dog,"
  3. Используйте регулярное выражение для извлечения значений

    get_animal {
        echo "$(expr "$animals" : ".*,$1:\([^,]*\),.*")"
    }
  4. Разделить строку, чтобы перечислить элементы

    get_animal_items {
        arr=$(echo "${animals:1:${#animals}-2}" | tr "," "\n")
        for i in $arr
        do
            value="${i##*:}"
            key="${i%%:*}"
            echo "${value} likes to $key"
        done
    }

Теперь вы можете использовать его:

$ animal = get_animal "moo"
cow
$ get_animal_items
cow likes to moo
dog likes to woof
марко
источник
5

Мне очень понравился ответ Аль П, но я хотел, чтобы уникальность была обеспечена дешево, поэтому я сделал еще один шаг вперед - использовал каталог. Существуют некоторые очевидные ограничения (ограничения файлов каталога, недопустимые имена файлов), но это должно работать в большинстве случаев.

hinit() {
    rm -rf /tmp/hashmap.$1
    mkdir -p /tmp/hashmap.$1
}

hput() {
    printf "$3" > /tmp/hashmap.$1/$2
}

hget() {
    cat /tmp/hashmap.$1/$2
}

hkeys() {
    ls -1 /tmp/hashmap.$1
}

hdestroy() {
    rm -rf /tmp/hashmap.$1
}

hinit ids

for (( i = 0; i < 10000; i++ )); do
    hput ids "key$i" "value$i"
done

for (( i = 0; i < 10000; i++ )); do
    printf '%s\n' $(hget ids "key$i") > /dev/null
done

hdestroy ids

Он также работает немного лучше в моих тестах.

$ time bash hash.sh 
real    0m46.500s
user    0m16.767s
sys     0m51.473s

$ time bash dirhash.sh 
real    0m35.875s
user    0m8.002s
sys     0m24.666s

Просто подумал, что я смогу участвовать. Ура!

Редактировать: Добавление hdestroy ()

Коул Стэнфилд
источник
3

Две вещи: вы можете использовать память вместо / tmp в любом ядре 2.6, используя / dev / shm (Redhat), другие дистрибутивы могут отличаться. Также hget может быть переопределён следующим образом:

function hget {

  while read key idx
  do
    if [ $key = $2 ]
    then
      echo $idx
      return
    fi
  done < /dev/shm/hashmap.$1
}

Кроме того, предполагая, что все ключи уникальны, возврат замыкает цикл чтения и предотвращает необходимость чтения всех записей. Если ваша реализация может иметь дубликаты ключей, просто опустите возврат. Это экономит расходы на чтение и разветвление как grep, так и awk. Использование / dev / shm для обеих реализаций дало следующее использование time hget для хеша с 3 записями, ищущего последнюю запись:

Grep / Awk:

hget() {
    grep "^$2 " /dev/shm/hashmap.$1 | awk '{ print $2 };'
}

$ time echo $(hget FD oracle)
3

real    0m0.011s
user    0m0.002s
sys     0m0.013s

Чтение / эхо:

$ time echo $(hget FD oracle)
3

real    0m0.004s
user    0m0.000s
sys     0m0.004s

при многократных вызовах я никогда не видел улучшения менее чем на 50%. Это все можно отнести к форк над головой, из-за использования /dev/shm.

jrichard
источник
3

Коллега только что упомянул эту тему. Я независимо реализовал хеш-таблицы в bash, и это не зависит от версии 4. Из моего поста в блоге в марте 2010 года (до некоторых ответов здесь ...), озаглавленного Хеш-таблицы в bash :

Ранее я использовал cksumдля хэширования, но с тех пор перевел строковый хэш-код Java в нативный bash / zsh.

# Here's the hashing function
ht() {
  local h=0 i
  for (( i=0; i < ${#1}; i++ )); do
    let "h=( (h<<5) - h ) + $(printf %d \'${1:$i:1})"
    let "h |= h"
  done
  printf "$h"
}

# Example:

myhash[`ht foo bar`]="a value"
myhash[`ht baz baf`]="b value"

echo ${myhash[`ht baz baf`]} # "b value"
echo ${myhash[@]} # "a value b value" though perhaps reversed
echo ${#myhash[@]} # "2" - there are two values (note, zsh doesn't count right)

Он не двунаправленный, а встроенный способ намного лучше, но в любом случае его не следует использовать. Bash предназначен для быстрой разовой игры, и такие вещи довольно редко должны включать сложность, которая может потребовать хэшей, за исключением, возможно, ваших ~/.bashrcи ваших друзей.

Адам Кац
источник
Ссылка в ответе страшна! Если вы нажмете на нее, вы застряли в петле перенаправления. Пожалуйста обновите.
Ракиб
1
@MohammadRakibAmin - Да, мой веб-сайт не работает, и я сомневаюсь, что возродю свой блог. Я обновил приведенную выше ссылку на архивную версию. Спасибо за интерес!
Адам Кац
2

До bash 4 не было хорошего способа использовать ассоциативные массивы в bash. Лучше всего использовать интерпретированный язык, который действительно поддерживает такие вещи, как awk. С другой стороны, Баш 4 делает их поддержки.

Что касается менее хороших способов в bash 3, вот ссылка, которая может помочь: http://mywiki.wooledge.org/BashFAQ/006

Кодзиро
источник
2

Решение Bash 3:

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

# Define a hash like this
MYHASH=("firstName:Milan"
        "lastName:Adamovsky")

# Function to get value by key
getHashKey()
 {
  declare -a hash=("${!1}")
  local key
  local lookup=$2

  for key in "${hash[@]}" ; do
   KEY=${key%%:*}
   VALUE=${key#*:}
   if [[ $KEY == $lookup ]]
   then
    echo $VALUE
   fi
  done
 }

# Function to get a list of all keys
getHashKeys()
 {
  declare -a hash=("${!1}")
  local KEY
  local VALUE
  local key
  local lookup=$2

  for key in "${hash[@]}" ; do
   KEY=${key%%:*}
   VALUE=${key#*:}
   keys+="${KEY} "
  done

  echo $keys
 }

# Here we want to get the value of 'lastName'
echo $(getHashKey MYHASH[@] "lastName")


# Here we want to get all keys
echo $(getHashKeys MYHASH[@])
Милан Адамовский
источник
Я думаю, что это довольно аккуратный фрагмент. Это могло бы использовать небольшую очистку (не много, хотя). В моей версии я переименовал «ключ» в «пару» и сделал KEY и VALUE строчными (потому что я использую прописные буквы при экспорте переменных). Я также переименовал getHashKey в getHashValue и сделал ключ и значение локальными (хотя иногда вы бы хотели, чтобы они не были локальными). В getHashKeys я не присваиваю значение значению. Я использую точку с запятой для разделения, так как мои значения - это URL.
0

Я также использовал способ bash4, но я нахожу и раздражает ошибку.

Мне нужно было динамически обновлять содержимое ассоциативного массива, поэтому я использовал этот способ:

for instanceId in $instanceList
do
   aws cloudwatch describe-alarms --output json --alarm-name-prefix $instanceId| jq '.["MetricAlarms"][].StateValue'| xargs | grep -E 'ALARM|INSUFFICIENT_DATA'
   [ $? -eq 0 ] && statusCheck+=([$instanceId]="checkKO") || statusCheck+=([$instanceId]="allCheckOk"
done

Я обнаружил, что с bash 4.3.11 добавление существующего ключа в dict привело к добавлению значения, если оно уже присутствует. Так, например, после некоторого повторения содержание значения было «checkKOcheckKOallCheckOK», и это не было хорошо.

Нет проблем с bash 4.3.39, где добавление существующего ключа означает замещение действительного значения, если оно уже присутствует.

Я решил это просто очистив / объявив ассоциативный массив statusCheck перед циклом:

unset statusCheck; declare -A statusCheck
Alex
источник
-1

Я создаю HashMaps в Bash 3, используя динамические переменные. Я объяснил, как это работает в моем ответе на: Ассоциативные массивы в скриптах Shell

Также вы можете взглянуть на shell_map , который является реализацией HashMap, сделанной в bash 3.

Бруно Неграо Зика
источник