第九章　關聯數組/哈希表

■【數組變量的限製】

在前面講的數組變量中，可以通過下標訪問其中的元素。例如，下列語句訪問數組@array的第三個元素︰
$scalar = $array[2];
雖然數組很有用，但它們有一個顯著缺陷，即很難記住哪個元素存貯的什么內容。假如我們來寫一個程序計算某文件中首字母大寫的單詞出現的次數，用數組來實現就比較困難，程序代碼如下︰
1 : #!/usr/local/bin/perl
2 :
3 : while ($inputline = <STDIN>) {
4 : while ($inputline =~ /\b[A-Z]\S+/g) {
5 : $word = $&;
6 : $word =~ s/[;.,:-]$//; # remove punctuation
7 : for ($count = 1; $count <= @wordlist;
8 : $count++) {
9 : $found = 0;
10: if ($wordlist[$count-1] eq $word) {
11: $found = 1;
12: $wordcount[$count-1] += 1;
13: last;
14: }
15: }
16: if ($found == 0) {
17: $oldlength = @wordlist;
18: $wordlist[$oldlength] = $word;
19: $wordcount[$oldlength] = 1;
20: }
21: }
22: }
23: print ("Capitalized words and number of occurrences:\n");
24: for ($count = 1; $count <= @wordlist; $count++) {
25: print ("$wordlist[$count-1]: $wordcount[$count-1]\n");
26: }
運行結果如下︰

Here is a line of Input.
This Input contains some Capitalized words.
^D
Capitalized words and number of occurrences:
Here: 1
Input: 2
This: 1
Capitalized: 1
這個程序每次從標準輸入文件讀一行文字，第四行起的循環匹配每行中首字母大寫的單詞，每找到一個循環一次，賦給簡單變量$word。在第六行中去掉標點後，查看該單詞是否曾出現過，7~15行中在@wordlist中挨個元素做此檢查，如果某個元素與$word相等，@wordcount中相應的元素就增加一個數。如果沒有出現過，即@wordlist中沒有元素與$word相等，16~20行給@wordlist和@wordcount增加一個新元素。

■【定義】

正如你所看到的，使用數組元素產生了一些問題。首先，@wordlist中哪個元素對應著哪個單詞並不明顯；更糟的是，每讀進一個新單詞，程序必須檢查整個列表才能知道該單詞是否曾經出現過，當列表變得較大時，這是很耗費時間的。
這些問題產生的原因是數組元素通過數字下標訪問，為了解決這類問題，Perl定義了另一種數組，可以用任意簡單變量值來訪問其元素，這種數組叫做關聯數組，也叫哈希表。
為了區分關聯數組變量與普通的數組變量，Perl使用%作為其首字符，而數組變量以@打頭。與其它變量名一樣，%後的第一個字符必須為字母，後續字符可以為字母、數字或下劃線。

■【訪問關聯數組的元素】

關聯數組的下標可以為任何簡單/標量值，訪問單個元素時以$符號打頭，下標用大括號圍起來。例如︰

$fruit{"bananas"}
$number{3.14159}
$integer{-7}

簡單變量也可作為下標，如︰
$fruit{$my_fruit}

■【增加元素】

創建一個關聯數組元素最簡單的方法是賦值，如語句$fruit{"bananas"} = 1；把1賦給關聯數組%fruit下標為bananas的元素，如果該元素不存在，則被創建，如果數組%fruit從未使用過，也被創建。
這一特性使得關聯數組很容易用於計數。下面我們用關聯數組改寫上面的程序，注意實現同樣的功能此程序簡化了許多。

1 : #!/usr/local/bin/perl
2 :
3 : while ($inputline = ) {
4 :   while ($inputline =~ /\b[A-Z]\S+/g) {
5 :     $word = $&;
6 :     $word =~ s/[;.,:-]$//; # remove punctuation
7 :     $wordlist{$word} += 1;
8 :   }
9 : }
10: print ("Capitalized words and number of occurrences:\n");
11: foreach $capword (keys(%wordlist)) {
12:   print ("$capword: $wordlist{$capword}\n");
13: }

運行結果如下︰

Here is a line of Input.
This Input contains some Capitalized words.
^D
Capitalized words and number of occurrences:
This: 1
Input: 2
Here: 1
Capitalized: 1

    你可以看到，這次程序簡單多了，讀取輸入並存貯各單詞數目從20行減少到了7行。
    本程序用關聯數組%wordlist跟蹤首字母大寫的單詞，下標就用單詞本身，元素值為該單詞出現的次數。第11行使用了內嵌函數keys()。這個函數返回關聯數組的下標列表，foreach語句就用此列表循環。
    注︰關聯數組總是隨機存貯的，因此當你用keys()訪問其所有元素時，不保証元素以任何順序出現，特別值得一提的是，它們不會以被創建的順序出現。
    要想控製關聯數組元素出現的次序，可以用sort()函數對keys()返回值進行排列，如︰

foreach $capword (sort keys(%wordlist)) {
print ("$capword: $wordlist{$capword}\n");
}

■【創建關聯數組】

    可以用單個賦值語句創建關聯數組，如︰
    %fruit = ("apples",17,"bananas",9,"oranges","none");
    此語句創建的關聯數組含有下面三個元素︰

下標為apples的元素，值為17
下標為bananas的元素，值為9
下標為oranges的元素，值為none

注︰用列表給關聯數組賦值時，Perl5允許使用"=>"或","來分隔下標與值，用"=>"可讀性更好些，上面語句等效於︰
%fruit = ("apples"=>17,"bananas"=>9,"oranges"=>"none");

■【從數組變量複製到關聯數組】

    與列表一樣，也可以通過數組變量創建關聯數組，當然，其元素數目應該為偶數，如︰
    @fruit = ("apples",17,"bananas",9,"oranges","none");
    %fruit = @fruit;
    反之，可以把關聯數組賦給數組變量，如︰
    %fruit = ("grapes",11,"lemons",27);
    @fruit = %fruit;
    注意，此語句中元素次序未定義，那么數組變量@fruit可能為("grapes",11,"lemons",27)或("lemons",27,"grapes",11)。
    關聯數組變量之間可以直接賦值，如︰%fruit2 = %fruit1; 還可以把數組變量同時賦給一些簡單變量和一個關聯數組變量，如︰
    ($var1, $var2, %myarray) = @list;
    此語句把@list的第一個元素賦給$var1，第二個賦給$var2，其余的賦給%myarray。
    最後，關聯數組可以通過返回值為列表的內嵌函數或用戶定義的子程序來創建，下例中把split()函數的返回值--一個列表--賦給一個關聯數組變量。

1: #!/usr/local/bin/perl
2:
3: $inputline = <STDIN>;
4: $inputline =~ s/^\s+|\s+\n$//g;
5: %fruit = split(/\s+/, $inputline);
6: print ("Number of bananas: $fruit{\"bananas\"}\n");

運行結果如下︰

oranges 5 apples 7 bananas 11 cherries 6
Number of bananas: 11

■【元素的增刪】

    增加元素已經講過，可以通過給一個未出現過的元素賦值來向關聯數組中增加新元素，如$fruit{"lime"} = 1;創建下標為lime、值為1的新元素。
    刪除元素的方法是用內嵌函數delete，如欲刪除上述元素，則︰
    delete ($fruit{"lime"});
注意︰

1、一定要使用delete函數來刪除關聯數組的元素，這是唯一的方法。
2、一定不要對關聯數組使用內嵌函數push、pop、shift及splice，因為其元素位置是隨機的。

■【列出數組的索引和值】

上面已經提到，keys()函數返回關聯數組下標的列表，如︰

%fruit = ("apples", 9,
"bananas", 23,
"cherries", 11);
@fruitsubs = keys(%fruits);

這裡，@fruitsubs被賦給apples、bananas、cherries構成的列表，再次提請注意，此列表沒有次序，若想按字母順序排列，可使用sort()函數。
@fruitindexes = sort keys(%fruits);
這樣結果為("apples","bananas","cherries")。類似的，內嵌函數values()返回關聯數組值的列表，如︰

%fruit = ("apples", 9,
"bananas", 23,
"cherries", 11);
@fruitvalues = values(%fruits);

這裡，@fruitvalues可能的結果為(9,23.11)，次序可能不同。

■【用關聯數組循環】

前面已經出現過利用keys()函數的foreach循環語句，這種循環效率比較低，因為每返回一個下標，還得再去尋找其值，如︰

foreach $holder (keys(%records)){
$record = $records{$holder};
}
Perl提供一種更有效的循環方式，使用內嵌函數each()，如︰

%records = ("Maris", 61, "Aaron", 755, "Young", 511);
while (($holder, $record) = each(%records)) {
# stuff goes here
}
each()函數每次返回一個雙元素的列表，其第一個元素為下標，第二個元素為相應的值，最後返回一個空列表。
注意︰千萬不要在each()循環中添加或刪除元素，否則會產生不可預料的後果。

■【用關聯數組創建數據結構】

    用關聯數組可以模擬在其它高級語言中常見的多種數據結構，本節講述如何用之實現︰鏈表、結構和樹。
1、(單)鏈表
    鏈表是一種比較簡單的數據結構，可以按一定的次序存貯值。每個元素含有兩個域，一個是值，一個是引用（或稱指針），指向鏈表中下一個元素。一個特殊的頭指針指向鏈表的第一個元素。
    在Perl中，鏈表很容易用關聯數組實現，因為一個元素的值可以作為下一個元素的索引。下例為按字母順序排列的單詞鏈表︰

%words = ("abel", "baker", 
          "baker", "charlie",
          "charlie", "delta",
          "delta", "");
$header = "abel";

    上例中，簡單變量$header含有鏈表中第一個單詞，它同時也是關聯數組第一個元素的下標，其值baker又是下一個元素的下標，依此類推。
    下標為delta的最後一個元素的值為空串，表示鏈表的結束。
    在將要處理的數據個數未知或其隨程序運行而增長的情況下，鏈表十分有用。下例用鏈表按字母次序輸出一個文件中的單詞。

1 : #!/usr/local/bin/perl
2 :
3 : # initialize list to empty
4 : $header = "";
5 : while ($line = <STDIN>) {
6 :   # remove leading and trailing spaces
7 :   $line =~ s/^\s+|\s+$//g;
8 :   @words = split(/\s+/, $line);
9 :   foreach $word (@words) {
10:     # remove closing punctuation, if any
11:     $word =~ s/[.,;:-]$//;
12:     # convert all words to lower case
13:     $word =~ tr/A-Z/a-z/;
14:     &add_word_to_list($word);
15:   }
16: }
17: &print_list;
18:
19: sub add_word_to_list {
20:   local($word) = @_;
21:   local($pointer);
22:
23:   # if list is empty, add first item
24:   if ($header eq "") {
25:     $header = $word;
26:     $wordlist{$word} = "";
27:     return;
28:   }
29:   # if word identical to first element in list,
30:   # do nothing
31:   return if ($header eq $word);
32:   # see whether word should be the new
33:   # first word in the list
34:   if ($header gt $word) {
35:     $wordlist{$word} = $header;
36:     $header = $word;
37:     return;
38:   }
39:   # find place where word belongs
40:   $pointer = $header;
41:   while ($wordlist{$pointer} ne "" &&
42:     $wordlist{$pointer} lt $word) {
43:     $pointer = $wordlist{$pointer};
44:   }
45:   # if word already seen, do nothing
46:   return if ($word eq $wordlist{$pointer});
47:   $wordlist{$word} = $wordlist{$pointer};
48:   $wordlist{$pointer} = $word;
49: }
50:
51: sub print_list {
52:   local ($pointer);
53:   print ("Words in this file:\n");
54:   $pointer = $header;
55:   while ($pointer ne "") {
56:     print ("$pointer\n");
57:     $pointer = $wordlist{$pointer};
58:   }
59: }

運行結果如下︰

Here are some words.
Here are more words.
Here are still more words.
^D
Words in this file:
are
here
more
some
still
words

此程序分為三個部分︰

主程序︰讀取輸入並轉換到相應的格式。
子程序︰add_word_to_list，建立排序單詞鏈表。
子程序︰print_list，輸出單詞鏈表

    第3~17行為主程序，第4行初始化鏈表，將表頭變量$header設為空串，第5行起的循環每次讀取一行輸入，第7行去掉頭、尾的空格，第8行將句子分割成單詞。9~15行的內循環每次處理一個單詞，如果該單詞的最後一個字符是標點符號，就去掉。第13行把單詞轉換成全小寫形式，第14行傳遞給子程序add_word_to_list。
    子程序add_word_to_list先在第24行處檢查鏈表是否為空。如果是，第25行將單詞賦給$header，26行創建鏈表第一個元素，存貯在關聯數組%wordlist中。如果鏈表非空，37行檢查第一個元素是否與該單詞相同，如果相同，就立刻返回。下一步檢查這一新單詞是否應該為鏈表第一個元素，即其按字母順序先於$header。如果是這樣，則︰
    1、創建一個新元素，下標為該新單詞，其值為原第一個單詞。
    2、該新單詞賦給$header。
    如果該新單詞不該為第一個元素，則40~44行利用局域變量$pointer尋找其合適的有效位置，41~44行循環到$wordlist{$pointer}大於或等於$word為止。接下來46行查看該單詞是否已在鏈表中，如果在就返回，否則47~48行將其添加到鏈表中。首先47行創建新元素$wordlist{$word}，其值為$wordlist{$pointer}，這時$wordlist{$word}和$wordlist{$pointer}指向同一個單詞。然後，48行將$wordlist{$pointer}的值賦為$word，即將$wordlist{$pointer}指向剛創建的新元素$wordlist{$word}。
    最後當處理完畢後，子程序print_list()依次輸出鏈表，局域變量$pointer含有正在輸出的值，$wordlist{$pointer}為下一個要輸出的值。
    注︰一般不需要用鏈表來做這些工作，用sort()和keys()在關聯數組中循環就足夠了，如︰

foreach $word (sort keys(%wordlist)) {
# print the sorted list, or whatever }

    但是，這裡涉及的指針的概念在其它數據結構中很有意義。
2、結構
    許多編程語言可以定義結構(structure)，即一組數據的集合。結構中的每個元素有其自己的名字，並通過該名字來訪問。
    Perl不直接提供結構這種數據結構，但可以用關聯數組來模擬。例如模擬C語言中如下的結構︰

struce{
int field1;
int field2;
int field3; }mystructvar;

我們要做的是定義一個含有三個元素的關聯數組，下標分別為field1、field2、field3，如︰

%mystructvar = ("field1" , "" ,
"field2" , "" ,
"field3" , "" ,);

    像上面C語言的定義一樣，這個關聯數組%mystrctvar有三個元素，下標分別為field1、field2、field3，各元素初始值均為空串。對各元素的訪問和賦值通過指定下標來進行，如︰
    $mystructvar{"field1"} = 17;
3、樹
    另一個經常使用的數據結構是樹。樹與鏈表類似，但每個節點指向的元素多於一個。最簡單的樹是二叉樹，每個節點指向另外兩個元素，稱為左子節點和右子節點（或稱孩子），每個子節點又指向兩個孫子節點，依此類推。
    注︰此處所說的樹像上述鏈表一樣是單向的，每個節點指向其子節點，但子節點並不指向父節點。
    樹的概念可以如下描述︰

因為每個子節點均為一個樹，所以左/右子節點也稱為左/右子樹。（有時稱左/右分支）
第一個節點（不是任何節點的子節點的節點）稱為樹的根。
沒有孩子（子節點）的節點稱為葉節點。

有多種使用關聯數組實現樹結構的方法，最好的一種應該是︰給子節點分別加上left和right以訪問之。例如，alphaleft和alpharight指向alpha的左右子節點。下面是用此方法創建二叉樹並遍歷的例程︰

1 : #!/usr/local/bin/perl
2 :
3 : $rootname = "parent";
4 : %tree = ("parentleft", "child1",
5 :          "parentright", "child2",
6 :          "child1left", "grandchild1",
7 :          "child1right", "grandchild2",
8 :          "child2left", "grandchild3",
9 :          "child2right", "grandchild4");
10: # traverse tree, printing its elements
11: &print_tree($rootname);
12:
13: sub print_tree {
14:   local ($nodename) = @_;
15:   local ($leftchildname, $rightchildname);
16:
17:   $leftchildname = $nodename . "left";
18:   $rightchildname = $nodename . "right";
19:   if ($tree{$leftchildname} ne "") {
20:     &print_tree($tree{$leftchildname});
21:   }
22:   print ("$nodename\n");
23:   if ($tree{$rightchildname} ne "") {
24:     &print_tree($tree{$rightchildname});
25:   }
26: }

結果輸出如下︰

grandchild1
child1
grandchild2
parent
grandchild3
child2
grandchild4

該程序創建的二叉樹如下圖︰

注意函數print_tree()以次序“左子樹、節點、右子樹”來輸出各節點的名字，這種遍歷次序稱為“左序遍歷”。如果把第22行移到19行前，先輸出節點明，再輸出左子樹、右子樹，則為“中序遍歷”，如果把第22行移到25行後，輸出次序為左子樹、右子樹、節點，則為“右序遍歷”。
可以用同樣的方法，即連接字符串構成下標，來創建其它的數據結構，如數據庫等。

■【操作符的次序】