前言

  • 数组中判断元素是否存在的时间复杂度一般为O（n），是因为大家一般的做法都是遍历一遍数组看看所要找的数据是否存在。

  • 这里介绍一种利用key的唯一性来实现的时间复杂度为O（1）的判断元素是否存在的方法

  • 在c语言里这种方法经常使用，这里介绍在shell的语法中我们如何利用关联数组和key值唯一性来提高脚本的执行效率


需求和解决方法

构建关键字数组和查找数组

  1. for num in `seq 1 10`  

  2. do  

  3.    element[$num]="user_"$num  

  4. done  

  5. #构建被搜索数组  

  6. for num in `seq 1 100`  

  7. do  

  8.    search[$num]="user_"$num  

  9. done  


O（n2）的普通搜索

  1. #普通的搜索方式,时间复杂度O(N2)  

  2. for e in ${element[*]}  

  3. do  

  4.    for s in ${search[*]}  

  5.    do  

  6.        if [ $e = $s ]; then  

  7.            echo "找到$e"  

  8.            break  

  9.        fi  

  10.    done  

  11. done  



O（1）的关联数组搜索

  1. #关联数组方式  

  2. declare -A newsearch  

  3. for s in ${search[*]}  

  4. do  

  5.    newsearch[$s]=1  

  6. done  

  7. #KEY值唯一性，时间复杂度O(1)  

  8. for e in ${element[*]}  

  9. do  

  10.    if [ ${newsearch[$e]} -eq 1 ]; then  

  11.        echo "找到$e"  

  12.    fi  

  13. done  


shell关联数组

Shell Associative Array
  bashi没有原生的对于类似hash table的支持，不像perl或python.
下标数组元素是通过数组下标（数组下标可以是算术表达式，其结果必须是一个整数）来访问的，但是这种访问方式在表达某些关联性很强的数据时会存在限制。
shell 提供了另外一种数组，其可以使用任意的字符串作为下标（不必是整数）来访问数组元素。这种数组叫做关联数组（associative array）。
关联数组的下标和值称为键值对，它们是一一对应的关系。在关联数组中，键是唯一的，值可以不唯一。
shell 的关联数组和 perl 的关联数组在实现功能上是一样的。在 perl 中，关联数组有时候称为哈希（hash）。

定义关联数组
shell 的关联数组和 shell 的下标数组在定义和使用上完全一样，只是在索引上有区别。
需要注意的是，在使用关联数组之前，需要使用命令 declare -A array 进行显示声明。

下标数组元素是通过数组下标（数组下标可以是算数表达式，其结果必须是一个整数）来访问的，但是这种访问方式在表达某些关联性很强的数据时会存在限制

类似于php，shell也提供了一种数组，其可以使用任意的字符串作为下标来访问数组元素，这种数组叫关联数组，关联数组也是php的精髓所在

注意，shell中定义关联数组需要声明，声明语法：

  1. declare -A array_name  


示例 1
test.sh 文件的内容如下
name=(jim tom lucy)

declare -A phone
phone=([jim]=135 [tom]=136 [lucy]=158)

for i in `eval echo {0..$((${#name[*]}-1))}`
do

echo ${name[i]} phone number is ${phone["${name[i]}"]}
done

在命令提示符下输入 ./test.sh，执行结果如下：
jim phone number is 135
tom phone number is 136
lucy phone number is 158

操作关联数组的语法
关联数组的操作语法和数组的操作语法完全一致，如下列出常见的操作。

语法 描述
${!array[*]} 取关联数组所有键
${!array[@]} 取关联数组所有键
${array[*]} 取关联数组所有值
${array[@]} 取关联数组所有值
${#array[*]}
 关联数组的长度
${#array[@]} 关联数组的长度

示例 2
test.sh 文件的内容如下
declare -A phone
phone=([jim]=135 [tom]=136 [lucy]=158)

for key in ${!phone[*]}
do
echo "$key -> ${phone[$key]}"
done

在命令提示符下输入 ./test.sh，执行结果如下：
tom -> 136
jim -> 135
lucy -> 158



数组：

定义方式


下标数组

直接赋值

  1. #!/bin/bash  

  2. arr[0]="one"  

  3. arr[1]="two"  

  4. arr[2]="three"  

  5. for num in ${arr[*]}  

  6. do  

  7.    echo $num  

  8. done  


圆括号顺序赋值

  1. arr=("four" "five" "six")  

  2. for num in ${arr[*]}  

  3. do  

  4.    echo $num  

  5. don  

shell关联数组提高查找效率

关联数组

前提：关联数组需要进行语法声明

  1. declare -A array_name  


赋值

  1. #!/bin/bash  

  2. declare -A arr  

  3. arr["name"]="wangzhengyi"  

  4. arr["sex"]="boy"  

  5. arr["age"]="25"  

  6. for param in ${arr[*]}  

  7. do  

  8.    echo $param  

  9. done  

shell关联数组提高查找效率

数组的长度和读取


数组长度

命令

  1. 用${#数组名[*或@]}可以获得数组长度  

shell关联数组提高查找效率

数组value读取

命令

  1. 用${下标数组名[下标]} 或 ${关联数组[key]}  


注：下标是*或者@可以得到整个数组的内容

shell关联数组提高查找效率


数组键值(key)读取

命令

  1. 用${!数组名[*或@]}  

shell关联数组提高查找效率