HASH GAME - Online Skill Game GET 300

　　第六章 哈希（Hash）结构 Lecture by Gong 08/03 哈希 哈希是Perl中的第三种基本数据类型。 第一种数据类型是标量，它是一种简单的数据类型，用于存放一个数据。 第二种数据类型是数组，它是标量的集合。 哈希是另一种集合型数据类型，与数组一样，可容纳许多个标量。 与数组的差别是：哈希是按照”名字”来访问它们的标量的，而不是使用数字索引号进行访问。 哈希元素包含两个部分，即一个键和一个值。键用于标识哈希的每个值，而值则是与该键相关的数据。即组成了键值对。 这些键可以是任何字符串，但必须是唯一的。 图6.1 哈希的建与值 图6.2 哈希像一桶数据 在Perl中，哈希变量的命名与其他变量相似，但前面是以百分比符号（%）来标识的，与数组和标量不使用相同的名字。 它与数组和标量可以使用相同的变量名，但之间毫不相关。 例如，你可以拥有一个名字叫%a的哈希变量，也可以有一个名字叫@a的数组，还可以有一个名字叫$ a的标量。这些名字指的是3个互不相关的变量。 在本学时中，你将要学习如何进行下面的操作： 创建哈希结构。 将元素插入哈希结构和从哈希结构中删除元素。 使用哈希结构对数组进行操作。 一、将数据填入哈希结构 与创建数组的元素相似，若要创建哈希元素，只需要将值赋予这些元素即可。例如，创建各个哈希元素： 为什么这个例子使用的是$ A u t h o r s { }，而不是% A u t h o r s { }呢？ 与数组一样，当哈希结构作为一个整体来展示时，其变量名的前面为 %。 当你访问哈希结构的单个元素，即一个标量值时，要在变量名的前面加上一个$，表示它引用的是单个值，同时使用花括号来指明该值的健。 $ A u t h o r s {‘D u n e’}代表单个标量值，可以像其他标量一样进行处理。 若要将若干个值放入一个哈希结构，可以使用一系列的赋值语句，如下面的代码所示： 哈希结构进行初始化时，大型列表中关键字与值是很容易搞混的。 Perl有一个特殊的运算符，称为胖箭头运算符，即=。 使用=运算符，同时利用Perl忽略白空间的特性，就能够编写下面这样的哈希结构的初始化代码： 花括号中的单个单词的哈希键会自动加上引号。 =运算符的左边将是个简单的字符串，不需要用引号括起来。 二、从哈希结构中取出数据 若要从哈希结构中取出单个元素，只需要使用一个$ 、 哈希结构的名字 、花括号括住你想要检索的键，即$hash{$some_key}。 例如： 如何查看哈希结构中的所有元素？如果所有关键字都是已知的，按照关键字来访问它们。 若果不知，该怎么办？ 可以使用keys函数来检索作为列表返回的哈希结构的所有键，然后可以查看该列表，找出哈希结构的所有元素。 Perl还提供了另一个函数values，用于检索哈希结构中存放的所有值。返回的哈希结构的值的顺序与keys函数返回的关键字的顺序是相同的,例如： 有时，需按值从哈希结构中检索各个元素。最好方法是对哈希结构进行切换，也就是说，所有键变成值，所有值变成新哈希结构的键。 然后Perl对该列表中的元素顺序进行倒序，得到下面这个输出： 三、列表与哈希结构 当哈希结构用于列表环境中时， Perl会将哈希结构重新变为由键和值组成的列表，每对键值的顺序在列表中无法预测，但键和值的相对位置不变。 该列表可以被赋予数组，这与其他任何列表的情况是一样的，如下所示： 也可以对该数组（eg. @Data）进行任何常规的操作，然后将数组赋予%Movies，如下所示： 上面代码中的第2行将两个哈希结构%First和%Second组合成第三个哈希结构% Both。如果%First的有些键也出现在%Second中，那么第二次出现的键值对就取代%Both中的第一个键值对。 在第3行代码中，%Both显示为一个放在括号中的键值对的列表，另外两个键值对也放在括号中。然后整个列表用于对%Additional进行初始化。 四、关于哈希结构的补充说明 对于Perl的初学者，对哈希结构进行某些操作时可能会遇到困难。 由于哈希结构的特殊性质，有两个常用操作需要一些专门的函数，而这些函数对于标量和数组来说是不必要的。 4.1 测试哈希结构中的关键字 若要测试哈希结构中是否存在某个键，Perl有一个专门用于这个目的的函数，称为exists。 下面显示的exists函数可以用于测试哈希结构中是否存在某个键Keyval，如果存在，便返回线 从哈希结构中删除键 另一个操作是从哈希结构中删除键。 若要删除单个哈希关键字，可以使用delete函数，如下所示： 五、哈希结构的典型应用 由于许多方面的原因，在Perl中使用哈希结构，其目的不仅仅是为了按关键字来存储记录，供以后检索。使用哈希结构的优点是可以迅速访问各个键，并且所有键都是惟一的。 由于数组和哈希结构非常相似，因此你用哈希结构进行的许多有趣的操作属于数组操作。 5.1 在数组中寻找唯一元素 假设已经将输入的全部单词放入一个数组而不是哈希结构，同时没有专门采取措施来保证在将一个单词放入列表之前，该列表中还没有这个单词。在这种情况下，列表中可能存在许多重复的单词。 假设有单词列表为@fishwords，如下： 若要找出列表@ fishwords的独一无二的元素，那么使用哈希结构就非常适合，如程序清单6-1所示： 5.3 寻找两个数组之间的交汇部分和不同部分 对数组经常要进行的一项操作是寻找两个数组之间的交汇部分和两个数组之间的不同部分。 假设有两个列表，一个是包含电影明星，另一个是包含政治家。你的任务是找出是电影明星里的所有政治家。下面是你的两个（非常不完整的）数组： 程序清单6- 2显示了寻找交汇部分的代码。 第5行：@ pols中的grep函数对政治家的列表进行迭代操作，依次将$_设置给每个政治家。然后，在哈希结构%seen中寻找该名字。如果该名字返回真，那么它就位于哈希结构中，表达式$seen {$_}计算的结果为真, 那么grep返回$ _的值，然后该值被放入@ intersection中。这个过程将重复进行，直到@pols被grep全部查看完毕。 当该代码段运行结束时， @intersection便包含既是@stars又是@pols的所有成员的名字。 用于寻找两个数组之间的不同部分的代码与上面这个代码几乎是相同的，可以使用程序清单6 - 3来查找不是电影明星的所有政治家。 5.4 对哈希结构进行排序 许多情况下，仅仅按照默认顺序来检索哈希结构中的关键字是不够的（默认顺序是非常随机的） 可以用两种方法来按顺序输出哈希结构，一种是按单词的字母顺序，另一种是按频率的顺序。 由于keys函数能够返回一个简单的列表，因此可以像下面这样使用sort函数对该列表进排序： 如果需要进行比较复杂的排序，可以在代码块中调用sort函数，以便设定排序顺序。 下面这个代码显示了按照值该哈希结构进行排序的情况： 六、%ENV Perl程序运行在某个环境中，需要对周围的影响有所感知，获取这些信息的方法是存取%ENV哈希，例如常从%ENV中存取PATH的值： 课时小结 哈希结构为程序员提供了许多非常有用的工具。除了简单的记录存储和检索工具外，哈希还提供了对数据进行转换和分析的有用机制。数组操作、记录存储和检索的公式将会给你带来许多好处。在后面的几个学时中，哈希结构将为你提供一个进一步学习DBM文件处理、复杂数据结构的操作，以及与你的系统环境打交道等内容的途径。 思考题 1 对于本学时中你编写的C u s t o m e r程序来说，尤其是如果客户列表非常长的话，为什么 n a m e是个不合适的搜索关键字？ a. 姓和名字的组合超出了P e r l的哈希结构允许的长度。 b. 人的名字不是独一无二的关键字。 c. 没有人想要按照名字来搜索客户数据库。 2 相关性数组与哈希结构之间的区别是什么？ a. 没有区别。 b. 相关性数组用于更加正式的数据集，比如帐单记录。 c. 在P e r l中，哈希不是真正的相关性数组，因此它们拥有不同的名字。 3 哪些种类的数据最适合哈希结构？ a. 简单的项目列表。 b. 普通常用数据。 c. 关键字值对的列表。 1: %seen = (); 2: foreach (@stars) { 3: $seen{$_} = 1; 4: } 5: @different = grep(! $seen{$_}, @pols); foreach (sort keys %Words) { print $_ $Words{$_}\n; } foreach (sort { $Words{$a} = $Words{$b} } keys %Words) { print $_ $Words{$_}\n; } print “PATH is $ENV{PATH}\n”; 根据你的操作系统和设定，可能看到如下信息(Unix or Lnix)： PATH is /usr/local/bin: /usr/bin: sbin: /usr/sbin * * 35 12.4 hello 1.72e30 “bye\n” ＊哈希里面的键和 值都可以是任意 标量，但键总是 按字符串上下文 处理。 ＊ eg.以表达式50/20 为键，会转换成字 符串“2.5”。 $Authors{‘Dune‘} = ‘Frank Herbert’’; 在这个例子中，创建了一个元素的哈希结构%Authors。该元素的关键字是单词Dune，数据是名字Frank Herbert 。 $food{apple}=fruit; $food{pear}=fruit; $food{carrot}=vegetable; 可以用一个列表对该哈希结构进行初始化。该列表应该包含成对的键与值，如下所示： %food = (apple, fruit, pear, fruit, carrot, vegetable); %food = { apple = fruit, pear = fruit, carrot = vegetable, }; $books{Dune}=Frank Herbert; %food = { apple = fruit, pear = fruit, carrot = vegetable}; %Movies=(The Shining = Kubrick, Ten Commandments‘ = DeMille, Goonies = Spieberg); print $movies{The Shining}; %movies=(‘阿凡达’=’’,’2012’=’’,’诸神之战’=’’); @filename=keys %movies; ########################################## foreach $film (keys %movies) { print $film\n; } @directors = values %movies; @films = keys %movies; 在这个例子中， @directors和@films的每个下标都包含了一个对来自%movies的相同”键和值“对的引用。 $directors = values %movies; #....? $films = keys %movies; #....? %Movies=(The Shining = Kubrick, Ten Commandments‘ = DeMille, Goonies = Spieberg); %ByDirector = reverse %Movies; 这是什么呢？当你对哈希结构使用reverse函数时，Perl就先将哈希结构转换成一个简单的列表，也许类似于下面这个列表： (The Shining, Kubrick, Ten Commandments, DeMille, Goonies, Spielberg) (Spielberg, Goonies, DeMille, Ten Commandments, Kubrick, The Shining,) 最后，将这个列表赋予%ByDirector，产生的哈希结构将与原始哈希结构相同，只不过现在所有的键和值发生了颠倒。 %Movies=(The Shining = Kubrick, Ten Commandments‘ = DeMille, Goonies = Spieberg); @Data = %Movies; 这时， @Data是个包含6个元素的数组. %Movies = @Data; 就其他方面来说，哈希结构与数组是相似的。若要拷贝一个哈希结构，只需要将这个哈希结构赋予另一个哈希结构即可： %New_Hash = %Old_Hash; %Both = (%First, %Second); %Additional = (%Both, key1 = value1, key2 = value2); if (exists $Hash{Keyval}) { #right .... } delete $Hash{keyval}; 要从哈希结构中删除所有键和值，只需将哈希结构初始化为一个空的列表即可，如下所示： %Hash = （）; @fishwords = (one, fish, two, fish, red, fish, blue, fish); 1: %seen = (); 2: foreach (@fishwords) { 3: $seen{$_} = 1; 4: } 5: @uniquewords = keys %seen; 第3行：用于创建哈希结构%seen中的键，以$_中的该单词作为键，并为该健创建一个名义上的值。 第5行：只是从哈希结构中取出所有关键字，并将它们存放在@ uniquewords中。哈希结构中的任何重复单词（例如fish）将互相改写，然后只以一个关键字出现。 @stars = (R. Reagan, C. Eastwood, M. Jackson, Cher, S. Bono); @pols = (N. Gingrich, S.Thurmon, R. Reagan, S. Bono, C. Eastwood, M. Thatcher); 1: %seen = (); 2: foreach (@stars) { 3: $seen{$_} = 1; 4: } 5: @interssection = grep($seen{$_}, @pols); 第3行：用电影明星的名字填入哈希结构% s e e n的各个关键字，并将值设置为1，这个值可以是你想要的任何真值。 * * *