logo标签列表

如何在Bash中定义哈希表？

bashdictionaryhashtableassociative-array
825

在Bash中，Python字典的等效物是什么（应该适用于OS X和Linux）。

6
让Bash运行Python/Perl脚本...这样非常灵活！ - Déjà vu
1
参见：Shell脚本中的关联数组 - Gabriel Staples
15个回答
1376

Bash 4

Bash 4本地支持此功能。请确保您的脚本的hashbang是#!/usr/bin/env bash或#!/bin/bash，以免使用sh。确保您要么直接执行脚本，要么使用bash script执行script。（实际上没有使用Bash运行Bash脚本会非常困惑！）

你可以通过以下方式声明关联数组：

declare -A animals
你可以使用普通的数组赋值运算符填充元素。例如，如果你想要一个映射 animal[sound(key)] = animal(value)：

你可以使用普通的数组分配操作符来填充它。例如，如果你想要一个包含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

Bash 3

在Bash 4之前，您没有关联数组。 不要使用eval来模拟它们。 避免使用 eval，因为它是shell脚本的瘟疫。 最重要的原因是，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` 不能放在函数中。在 bash 函数中使用 `declare` 命令创建的变量作用域是该函数，这意味着我们不能使用它来访问或修改全局数组。(在 bash 4 中，可以使用 `declare -g` 来声明全局变量，但在 bash 4 中，可以直接使用关联数组避免此问题。)
总结：
  • 升级到 bash 4 并使用 `declare -A` 声明关联数组。
  • 如果无法升级，则使用 `declare` 选项。
  • 考虑使用 `awk` 替代并避免此问题。
6
无法升级：我之所以使用Bash编写脚本，是为了实现“随处运行”的可移植性。因此，依赖于Bash中非通用的功能会排除这种方法。这很遗憾，因为否则它对我来说将是一个绝佳的解决方案！ - Steve Pitchers
8
很遗憾，OSX默认仍然使用Bash 3作为"默认" Shell，这对许多人来说是一个问题。我认为ShellShock漏洞的恐慌可能会促使他们改变，但显然并没有。 - ken
19
这段话的意思是：“@ken，这个问题涉及到许可证问题。在OSX上运行Bash命令时，只能使用最新非GPLv3许可证的版本。”我会尽力使翻译更加通俗易懂，但不会改变原意或添加解释。 - lhunath
4
由于对GPLv3产生的不良影响，苹果不会将GNU bash更新到版本3之上，但这并不应该成为阻碍。你可以通过brew install bash来安装bash。http://brew.sh/ - lhunath
4
对于那些（在我看来很明智的）不愿意使所有用户的目录在没有明确的进程特权升级的情况下可写的人，可以使用sudo port install bash。 - Charles Duffy
显示剩余21条评论
160

有参数替换，尽管它可能也不太“政治正确”……像间接引用。

#!/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的方式当然更好，但如果你需要一种hack... 那就只能用hack了。你可以使用类似的技术在数组/哈希表中进行搜索。

6
我会把它改成VALUE=${animal#*:}，以保护ARRAY[$x]="caesar:come:see:conquer"这种情况。 - glenn jackman
4
如果键或值中有空格，将${ARRAY[@]}放在双引号中也很有用，例如for animal in "${ARRAY[@]}"; do。请注意，不要改变原文的意思。 - devguydavid
1
但效率不是很差吗？如果您想将其与另一个键列表进行比较，我认为它的时间复杂度是O(n*m)，而使用适当的哈希映射只需要O(n)（常数时间查找，对于单个键是O(1)）。 - CodeManX
1
这个想法并不是为了追求效率，而是为了让那些有Perl、Python甚至Bash 4背景的人更容易理解和阅读。它允许你以类似的方式编写代码。 - Bubnoff
2
@CoDEmanX：这是一个“hack”，一种聪明而优雅但仍然基本的“workaround”，旨在帮助那些仍然被困在Bash 3.x中的可怜人。在这样简单的代码中，您不能期望“proper hashmaps”或效率考虑。 - MestreLion
显示剩余2条评论
132

这就是我在这里寻找的东西：

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" )
2
请注意，变量的值可能不包含空格，否则您将一次添加多个元素。 - rubo77
16
点赞 hashmap["key"]="value" 语法，我也认为这是一个非常好的想法，可惜在其他出色的被接受答案中没有提到。 - thomanski
1
@rubo77 关键字不是单个，它添加了多个关键字。有什么解决方法吗？ - Xeverous
1
能否详细解释一下 ${!hashmap[@]} 这部分的含义？我认为 @ 是用来获取所有值的。但是感叹号如何区分键和值呢？ - lucidbrot
Shellcheck 警告 for key in ... 部分：SC2068: 双引号数组扩展以避免重新拆分元素。 - lucidbrot
1
@lucidbrot 我相信你已经找到了这个，但只是为了参考：${!name[@]} |${!name[*]} => 如果name是一个数组变量，则扩展为在name中分配的数组索引（键）列表。如果name不是数组，则扩展为0（如果name被设置）或null（否则）。当使用“@”并且扩展出现在双引号内时，每个键都会扩展为单独的单词。 3.5.3 Shell Parameter Expansion - Jim
44

只需使用文件系统：文件系统是一种树状结构，可以用作哈希映射表。 你的哈希表将是一个临时目录，你的键将是文件名，你的值将是文件内容。它的优点是可以处理巨大的哈希映射表，并且不需要特定的 shell。

创建哈希表

hashtable=$(mktemp -d)

添加一个元素

echo $value > "$hashtable/$key"

读取一个元素

value=$(< "$hashtable/$key")

性能

当然，它很慢，但并不那么慢。 我在我的机器上进行了测试，使用了SSD和btrfs，它每秒大约可以读/写3000个元素。

1
哪个版本的bash支持mkdir -d？（不是4.3，在Ubuntu 14上。我会使用mkdir /run/shm/foo，或者如果内存已满，则使用mkdir /tmp/foo。） - Camille Goudeseune
3
也许应该使用 mktemp -d 命令？ - Reid Ellis
2
好奇 $value=$(< $hashtable/$key) 和 value=$(< $hashtable/$key) 有什么区别？谢谢！ - Helin Wang
2
“在我的机器上测试过了”听起来像是在SSD上开个洞的好方法。并不是所有的Linux发行版都默认使用tmpfs。” - kirbyfan64sos
1
这将无法处理其中包含“/”斜杠的值。 - zomars
显示剩余4条评论
30

您可以进一步修改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”，它通过首都进行国家查找）。但是，无论如何，我认为你会发现这在性能方面非常糟糕。

编辑：上述版本的修改版支持具有非字母数字字符的键

hashKey() {
  # replace non-alphanumeric characters with underscore to make keys valid BASH identifiers
  echo "$1_$2" | sed -E "s/[^a-zA-Z0-9]+/_/g" | sed -E "s/^[^a-zA-Z0-9]+|[^a-zA-Z0-9]+\$//g"
}

hashPut() {
  local KEY=`hashKey $1 $2`
  eval "$KEY"="$3"
}

hashGet() {
  local KEY=`hashKey $1 $2`
  echo "${!KEY}"
}

编辑结束

如果您真的想要快速哈希查找，有一个非常糟糕的、可怕的方法实际上效果非常好。那就是：将键/值写入到一个临时文件中，每行一个，然后使用“grep“^$key””来获取它们，使用管道与cut或awk或sed或其他工具来检索值。

就像我说的，这听起来很糟糕，似乎应该很慢，并且会执行所有种类的不必要的IO，但实际上它非常快（磁盘缓存太棒了，不是吗？），即使对于非常大的哈希表也是如此。您必须自己强制执行键的唯一性等。即使只有几百个条目，输出文件/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`
2
太棒了！你甚至可以迭代它： for i in $(compgen -A variable capitols); do hget "$i" "" done - zhaorufei
24
考虑使用bash内置命令read的解决方案，如下所示的代码片段中的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
4
“read”是Bash中一个非常强大的特性，但很多Bash程序员都没有充分利用它。它允许使用类似_Lisp_列表处理的紧凑形式。例如，在上面的例子中，我们可以只剥离第一个元素并保留剩余部分（即与Lisp中的_first_和_rest_概念类似），方法是：IFS=$'|' read -r first rest <<< "$fields"。 - AsymLabs
20
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
32
叹息，那似乎是毫无必要的侮辱，而且不准确。人们不会在哈希表的核心部分放置输入验证、转义或编码（我确实知道），而是放在包装器中，并尽快在输入之后进行处理。 - DigitalRoss
@DigitalRoss，你能解释一下在 eval echo '${hash'"$1"'#hash}' 中 #hash 的用途吗？对我来说它似乎只是一个注释而已。这里的 #hash 有什么特殊含义吗？ - Sanjay
@Sanjay ${var#start} 从变量 var 存储的值的开头删除文本 start。 - jpaugh
8

我同意@lhunath和其他人的观点，关联数组是使用Bash 4的方式。如果您困于Bash 3（OSX，旧发行版无法更新），您也可以使用expr，在任何地方都应该有它，这是一个字符串和正则表达式。当字典不太大时，我特别喜欢使用它。

  1. Choose 2 separators that you will not use in keys and values (e.g. ',' and ':' )

  2. Write your map as a string (note the separator ',' also at beginning and end)

    animals=",moo:cow,woof:dog,"

  3. Use a regex to extract the values

    get_animal {
    echo "$(expr "$animals" : ".*,$1:\([^,]*\),.*")"
}

  4. Split the string to list the items

    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
6

我非常喜欢Al P的回答，但希望以更便宜的方式实现唯一性，所以我进一步使用了目录。虽然存在一些明显的限制（目录文件限制、无效文件名），但大多数情况下应该可以工作。

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（）函数

5

一位同事刚提到了这个帖子。我已经在bash中独立实现了哈希表，它不依赖于版本4。以下是我在2010年3月发布的博客文章（早于这里的某些答案...）《在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和相关文件中。

答案中的链接很可怕！如果你点击它，你会陷入一个重定向循环中。请更新。 - user2453382
1
@MohammadRakibAmin - 是的，我的网站挂了，我怀疑我不会再恢复我的博客了。我已经更新了上面的链接到一个存档版本。感谢您的关注！ - Adam Katz
看起来这个程序似乎无法处理哈希冲突。 - neuralmer
@neuralmer - 是的。这是一个实际的哈希结构的哈希实现。如果你想处理哈希冲突，我建议使用真正的哈希实现，而不是像这样的hack。将其适应于管理冲突将会消除它所有的优雅。 - Adam Katz
这里有一个版本，它使用了你的ht()函数并处理了碰撞：https://gist.github.com/chr15m/fb257ae8bb9774245b0ec67d9c7d388b - Chris McCormick
1
@ChrisMcCormick - 起步不错，但你的版本缺少哈希查找的速度（它循环遍历所有值），并且实际上没有实现任何碰撞避免。我已经在你的gist上发表了更详细的评论。 （https://gist.github.com/chr15m/fb257ae8bb9774245b0ec67d9c7d388b？permalink_comment_id=4533677＃gistcomment-4533677） - Adam Katz
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接