Como definir tabelas de hash no Bash?

556

Qual é o equivalente dos dicionários Python, exceto no Bash (deve funcionar no OS X e Linux).

Sridhar Ratnakumar
fonte
4
O bash executou um script python / perl ... Isso é muito flexível!
e2-e4
Considere usar xonsh (está no github).
Oliver

Respostas:

938

Bash 4

O Bash 4 suporta nativamente esse recurso. Verifique se o hashbang do seu script é #!/usr/bin/env bashou #!/bin/bashnão você acaba usando sh. Verifique se você está executando seu script diretamente ou execute scriptcom bash script. (Não realmente executar um script Bash com Bash não acontecer, e vai ser realmente confuso!)

Você declara uma matriz associativa fazendo:

declare -A animals

Você pode preenchê-lo com elementos usando o operador de atribuição de matriz normal. Por exemplo, se você deseja ter um mapa de animal[sound(key)] = animal(value):

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

Ou mescle-os:

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

Em seguida, use-os como matrizes normais. Usar

  • animals['key']='value' definir valor

  • "${animals[@]}" expandir os valores

  • "${!animals[@]}"(observe o !) para expandir as chaves

Não se esqueça de citá-los:

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

Bash 3

Antes do bash 4, você não tinha matrizes associativas. Não use evalpara emulá-los . Evite evalcomo a praga, porque é a praga do script de shell. O motivo mais importante é que evaltrata seus dados como código executável (também existem muitos outros).

Primeiro e mais importante : considere atualizar para o bash 4. Isso facilitará todo o processo para você.

Se houver um motivo para não atualizar, declareé uma opção muito mais segura. Ele não avalia os dados como o código do bash, como evalfaz e, como tal, não permite a injeção de código arbitrário com tanta facilidade.

Vamos preparar a resposta, introduzindo os conceitos:

Primeiro, indireção.

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

Em segundo lugar declare:

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

Junte-os:

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

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

Vamos usá-lo:

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

Nota: declarenão pode ser colocado em uma função. Qualquer uso de declaredentro de uma função bash transforma a variável criada localmente no escopo dessa função, o que significa que não podemos acessar ou modificar matrizes globais com ela. (No bash 4, você pode usar declare -g para declarar variáveis ​​globais - mas no bash 4, você pode usar matrizes associativas em primeiro lugar, evitando esta solução alternativa.)

Resumo:

  • Atualize para o bash 4 e use declare -Apara matrizes associativas.
  • Use a declareopção se você não pode atualizar.
  • Considere o uso awke evite o problema completamente.
lhunath
fonte
1
@ Richard: Presumivelmente, você não está realmente usando o bash. Seu hashbang é sh em vez de bash, ou você está invocando seu código com sh? Tente colocar isso antes de declarar: echo "$ BASH_VERSION $ POSIXLY_CORRECT", ele deve ser exibido 4.xe não y.
Lhunath 9/08/2012
5
Não é possível atualizar: a única razão pela qual escrevo scripts no Bash é a portabilidade "executar em qualquer lugar". Portanto, contar com um recurso não universal do Bash descarta essa abordagem. O que é uma pena, porque, caso contrário, teria sido uma excelente solução para mim!
Steve jarros
3
É uma pena que o OSX tenha como padrão o Bash 3 ainda, pois isso representa o "padrão" para muitas pessoas. Eu pensei que o susto do ShellShock poderia ter sido o impulso que eles precisavam, mas aparentemente não.
ken
13
@ken é uma questão de licenciamento. O Bash no OSX está paralisado na versão mais recente não licenciada pela GPLv3.
Lhunath 23/10/14
2
... ou sudo port install bash, para aqueles (sabiamente, IMHO) que não desejam criar diretórios no PATH para todos os usuários graváveis ​​sem escalação explícita de privilégios por processo.
Charles Duffy
125

Há substituição de parâmetro, embora também possa ser não-PC ... como indireto.

#!/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]##*:}"

O caminho do BASH 4 é melhor, é claro, mas se você precisar de um hack ... apenas um hack será suficiente. Você pode pesquisar o array / hash com técnicas semelhantes.

Bubnoff
fonte
5
Gostaria de mudar isso para VALUE=${animal#*:}proteger o casoARRAY[$x]="caesar:come:see:conquer"
Glenn Jackman
2
Também é útil colocar aspas duplas em torno de $ {ARRAY [@]}, caso haja espaços nas chaves ou valores, como emfor animal in "${ARRAY[@]}"; do
devguydavid
1
Mas a eficiência não é muito ruim? Estou pensando em O (n * m) se você quiser comparar com outra lista de chaves, em vez de O (n) com hashmaps adequados (pesquisa de tempo constante, O (1) para uma única chave).
CodeManX 23/08
1
A idéia é menos sobre eficiência, mais sobre compreensão / capacidade de leitura para pessoas com experiência em perl, python ou até bash 4. Permite que você escreva de maneira semelhante.
Bubnoff
1
@CoDEmanX: este é um hack , um inteligente e elegante, mas ainda rudimentar solução para ajudar as pobres almas ainda presas em 2007 com o Bash 3.x. Você não pode esperar "hashmaps adequados" ou considerações de eficiência em um código tão simples.
MestreLion 15/05
85

Isto é o que eu estava procurando aqui:

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

Isso não funcionou para mim com o bash 4.1.5:

animals=( ["moo"]="cow" )
aktivb
fonte
2
Note, que o valor não pode conter espaços, caso contrário você adde mais elementos de uma só vez
rubo77
6
Voto positivo para a sintaxe hashmap ["key"] = "value" que eu também achei ausente da fantástica resposta aceita.
Thomanski # 25/16
@ rubo77 key também não adiciona várias chaves. Alguma maneira de contornar isso?
Xeverous 31/05
25

Você pode modificar ainda mais a interface hput () / hget () para nomear hashes da seguinte maneira:

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

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

e depois

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

Isso permite que você defina outros mapas que não conflitem (por exemplo, 'rcapitals', que pesquisam o país pela capital). Mas, de qualquer forma, acho que você descobrirá que tudo isso é terrível, em termos de desempenho.

Se você realmente deseja uma pesquisa rápida por hash, há um hack terrível que realmente funciona muito bem. É isso: escreva seus valores-chave em um arquivo temporário, um por linha, e use 'grep "^ $ key"' para obtê-los, usando tubos com cut ou awk ou sed ou o que quer que seja para recuperar os valores.

Como eu disse, parece terrível, e parece que deve ser lento e fazer todo tipo de IO desnecessário, mas na prática é muito rápido (o cache do disco é incrível, não é?), Mesmo para hash muito grande tabelas. Você mesmo deve aplicar a exclusividade da chave, etc. Mesmo se você tiver apenas algumas centenas de entradas, o arquivo de saída / combinação grep será um pouco mais rápido - na minha experiência, várias vezes mais rápido. Também consome menos memória.

Aqui está uma maneira de fazer isso:

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`
Al P.
fonte
1
Ótimo! você pode até iterá-lo: para i em $ (compgen -A capitols variáveis); não hget "$ i" "" feito
zhaorufei
22

Basta usar o sistema de arquivos

O sistema de arquivos é uma estrutura em árvore que pode ser usada como um mapa de hash. Sua tabela de hash será um diretório temporário, suas chaves serão nomes de arquivos e seus valores serão o conteúdo do arquivo. A vantagem é que ele pode lidar com enormes hashmaps e não requer um shell específico.

Criação de Hashtable

hashtable=$(mktemp -d)

Adicione um elemento

echo $value > $hashtable/$key

Leia um elemento

value=$(< $hashtable/$key)

atuação

Claro, é lento, mas não tão lento. Eu testei na minha máquina, com um SSD e btrfs , e faz cerca de 3000 elementos de leitura / gravação por segundo .

lovasoa
fonte
1
Qual versão do bash suporta mkdir -d? (Não 4.3, no Ubuntu 14. Eu recorrer a mkdir /run/shm/foo, ou se que encheu RAM, mkdir /tmp/foo.)
Camille Goudeseune
1
Talvez mktemp -dfosse para isso?
Reid Ellis
2
Curioso, qual é a diferença entre $value=$(< $hashtable/$key)e value=$(< $hashtable/$key)? Obrigado!
Helin Wang
1
"testei na minha máquina" Isso parece uma ótima maneira de fazer um buraco no seu SSD. Nem todas as distribuições Linux usam tmpfs por padrão.
Kirbyfan64sos
Estou processando cerca de 50000 hashes. Perl e PHP fazem isso com menos de 1/2 segundo. Nó em 1 segundo e algo assim. A opção FS parece lenta. No entanto, podemos garantir que os arquivos existam apenas na RAM, de alguma forma?
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
fonte
31
Suspiro, isso parece desnecessariamente ofensivo e é impreciso de qualquer maneira. Não se poderia colocar validação de entrada, escape ou codificação (veja, eu realmente sei) nas entranhas da tabela de hash, mas em um invólucro e o mais rápido possível após a entrada.
DigitalRoss
@DigitalRoss, você pode explicar qual é o uso de #hash em eval echo '$ {hash' "$ 1" '# hash}' . para mim, parece-me um comentário não mais do que isso. #hash tem algum significado especial aqui?
Sanjay
@Sanjay ${var#start}remove o início do texto do início do valor armazenado na variável var .
jpaugh
11

Considere uma solução utilizando a festa builtin leitura como ilustrado dentro do trecho de código a partir de um script de firewall UFW que se segue. Essa abordagem tem a vantagem de usar quantos conjuntos de campos delimitados (não apenas 2) forem desejados. Nós usamos o | delimitador porque os especificadores de intervalo de portas podem exigir dois pontos, ou seja, 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
fonte
2
@CharlieMartin: read é um recurso muito poderoso e é subutilizado por muitos programadores do bash. Permite formas compactas de processamento de listas semelhantes a lisp . Por exemplo, no exemplo acima, podemos retirar apenas o primeiro elemento e reter o restante (ou seja, um conceito semelhante ao primeiro e repousar no lisp) fazendo o seguinte:IFS=$'|' read -r first rest <<< "$fields"
AsymLabs
6

Concordo com @lhunath e outros que a matriz associativa é o caminho a seguir com o Bash 4. Se você está preso ao Bash 3 (OSX, distros antigos que você não pode atualizar), também pode usar o expr, que deve estar em toda parte, uma string e expressões regulares. Eu gosto especialmente quando o dicionário não é muito grande.

  1. Escolha 2 separadores que você não usará em chaves e valores (por exemplo, ',' e ':')
  2. Escreva seu mapa como uma string (observe o separador ',' também no início e no final)

    animals=",moo:cow,woof:dog,"
  3. Use uma regex para extrair os valores

    get_animal {
        echo "$(expr "$animals" : ".*,$1:\([^,]*\),.*")"
    }
  4. Divida a sequência para listar os itens

    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
    }

Agora você pode usá-lo:

$ animal = get_animal "moo"
cow
$ get_animal_items
cow likes to moo
dog likes to woof
marco
fonte
5

Eu realmente gostei da resposta de Al P, mas queria que a exclusividade fosse aplicada de forma barata, então dei um passo adiante - use um diretório. Existem algumas limitações óbvias (limites de arquivo de diretório, nomes de arquivo inválidos), mas ele deve funcionar na maioria dos casos.

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

Ele também tem um desempenho um pouco melhor nos meus testes.

$ 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

Só pensei em dar um lance. Saúde!

Edit: Adicionando hdestroy ()

Cole Stanfield
fonte
3

Duas coisas, você pode usar memória em vez de / tmp em qualquer kernel 2.6 usando / dev / shm (Redhat). Outras distribuições podem variar. Também o hget pode ser reimplementado usando a leitura da seguinte maneira:

function hget {

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

Além disso, assumindo que todas as teclas são únicas, o retorno causa um curto-circuito no loop de leitura e evita a leitura de todas as entradas. Se sua implementação puder ter chaves duplicadas, simplesmente deixe de fora o retorno. Isso economiza as despesas de leitura e bifurcação de grep e awk. O uso de / dev / shm para ambas as implementações produziu o seguinte usando o time hget em um hash de 3 entradas procurando a última entrada:

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

Leitura / eco:

$ time echo $(hget FD oracle)
3

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

em várias invocações, nunca vi menos de 50% de melhoria. Tudo isso pode ser atribuído à sobrecarga, devido ao uso de /dev/shm.

jrichard
fonte
3

Um colega de trabalho acabou de mencionar esse tópico. Eu implementei tabelas de hash de maneira independente no bash e não depende da versão 4. De uma publicação minha em março de 2010 (antes de algumas das respostas aqui ...) intitulada Tabelas de hash no bash :

I anteriormente usado cksumpara haxixe, mas desde então traduzido hashCode corda de Java para bater nativa / 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)

Não é bidirecional, e a maneira integrada é muito melhor, mas também não deve ser usada. O Bash é único, e essas coisas raramente envolvem complexidade que pode exigir hashes, exceto talvez em você ~/.bashrce em seus amigos.

Adam Katz
fonte
O link na resposta é assustador! Se você clicar nele, ficará preso em um loop de redirecionamento. Por favor atualize.
Rakib 26/04/19
1
@MohammadRakibAmin - Sim, meu site está fora do ar e duvido que vou ressuscitar meu blog. Atualizei o link acima para uma versão arquivada. Obrigado pelo seu interesse!
23619 Adam
2

Antes do bash 4, não havia uma boa maneira de usar matrizes associativas no bash. Sua melhor aposta é usar uma linguagem interpretada que realmente suporte essas coisas, como o awk. Por outro lado, o bash 4 não apoiá-los.

Quanto às maneiras menos boas no bash 3, aqui está uma referência que pode ajudar: http://mywiki.wooledge.org/BashFAQ/006

kojiro
fonte
2

Solução Bash 3:

Ao ler algumas das respostas, reuni uma pequena função que gostaria de contribuir de volta para ajudar outras pessoas.

# 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[@])
Milan Adamovsky
fonte
Eu acho que esse é um trecho bem legal. Poderia usar um pouco de limpeza (embora não muito). Na minha versão, renomei 'key' para 'pair' e coloquei KEY e VALUE em minúsculas (porque uso maiúsculas quando as variáveis ​​são exportadas). Também renomei o método getHashKey para getHashValue e tornei a chave e o valor locais (às vezes você deseja que eles não sejam locais). Em getHashKeys, não atribuo nada ao valor. Uso ponto-e-vírgula para a separação, pois meus valores são URLs.
0

Eu também usei o caminho bash4, mas acho um bug irritante.

Eu precisava atualizar dinamicamente o conteúdo do array associativo, então usei desta maneira:

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

Descobri que, com o bash 4.3.11 anexado a uma chave existente no dict, o resultado foi acrescentado, se já estiver presente. Por exemplo, após algumas repetições, o conteúdo do valor era "checkKOcheckKOallCheckOK" e isso não era bom.

Não há problema com o bash 4.3.39, onde aplicar uma chave existente significa subestimar o valor atual, se já estiver presente.

Eu resolvi isso apenas limpando / declarando a matriz associativa statusCheck antes do ciclo:

unset statusCheck; declare -A statusCheck
Alex
fonte
-1

Eu crio HashMaps no bash 3 usando variáveis ​​dinâmicas. Expliquei como isso funciona na minha resposta a: Matrizes associativas em scripts Shell

Além disso, você pode dar uma olhada no shell_map , que é uma implementação do HashMap feita no bash 3.

Bruno Negrão Zica
fonte