精华内容
下载资源
问答
  • 又称为哈希表(hash table),是一种很好用的数据结构。 在程序中。我们可能会遇到须要消重的问题,举一个最简单的模型: 有一份username列表。存储了 10000 个username,没有反复项; 另一份黑名单列表,...
    PHP有数据的一个非常重要的一类,就是关联数组。又称为哈希表(hash table),是一种很好用的数据结构。

    在程序中。我们可能会遇到须要消重的问题,举一个最简单的模型:

    有一份username列表。存储了 10000 个username,没有反复项;
    另一份黑名单列表,存储了 2000 个username,格式与username列表同样。
    如今须要从username列表中删除处在黑名单里的username,要求用尽量快的时间处理。

    这个问题是一个小规模的处理量,假设实际一点,2 个表都可能非常大,比方有 2 亿条记录。



    我最開始想到的方法,就是做一个嵌套的循环。设username表有 M 条记录,黑名单列表有 N 条记录,那么,循环的次数是 M * N 次。
    PHP 版代码:


    01 <?php  
    02 foreach($arrayM as $keyM => $nameM) {  
    03 foreach($arrayN as $nameN) {  
    04 if ($nameM == $nameN) {  
    05 // 本行运行了 M * N 次!  
    06 unset($arrayM[$keyM]);  
    07 }  
    08 }  
    09 }  
    10 return $arrayM;  
    11 ?

    >


    还有一种方式,利用数组索引。

    PHP 是一种弱类型的语言,不像 C 语言那样有严格的变量类型限制。C 语言的数组。每个元素的类型必须一致。并且索引都是从 0 開始。
    PHP 的数组,能够用字符串作为索引,也称为关联数组。
    数组索引,有一个天然的限制就是不会反复。并且訪问的时候不须要查找,能够直接定位。



    还是刚才的那个问题,我们採用还有一种办法。

    把黑名单列表的username组织到一个数组里,数组的索引就是username。

    然后,遍历用户列表的时候,仅仅需直接用 isset 查询那个username是否存在就可以。

    PHP 版代码:


    01 <?php  
    02 $arrayHash = array();  
    03 foreach($arrayN as $nameN) {  
    04 // 本行运行了 N 次。  
    05 $arrayHash[$nameN] = 1;  
    06 }  
    07  
    08 foreach($arrayM as $keyM => $nameM) {  
    09 if (isset($arrayHash[$nameM])) {  
    10 // 本行运行了 M 次!

      
    11 unset($arrayM[$keyM]);  
    12 }  
    13 }  
    14 return $arrayM;  
    15 ?

    >


    能够看到,优化过的代码,循环次数是 M + N 次。

    假如 M 和 N 都是 10000,优化前,循环了 1 亿次;优化后。仅仅循环了 20000 次。差了 5000 倍。
    假设第二个程序耗时 1 秒。则第一个程序须要将近一个半小时!



    =========================================================================
    hash一个貌似比較复杂的东西,实际上理解起来并不那么夸张。这里做个笔记。

    hash,中文翻译成杂乱的东西。有人也叫它杂凑 ,或者翻译成什么都不是的音译“哈希”。

    简单说来。hash就是为了把一个复杂的字串,通过一定的转换,得到一个简单的数字(一般是数字)。
    如"abcd" 用各个字符的值直接相加。再取对10的余数,既(a+b+c+d)。来得到一个数字。例如说结果为5,那么这个5就能在一定意义上代表这个字串 abcd了。或者说这个5也能够说是这个字串的一个标记性的东西,并且是简化了的标记,所以又有人叫这个5为字串的摘要,或指纹。
    这个5,有一个好的用处就是能够作为一个数组的下标来用,如我自己构造一个指针数组void* hash_array[10]。那么我就能够把5那个位置上填上一个指针,如指向abcd字串。
    这种话。我假设要去查询一个字串是否存在,就不须要对一个数组使用字符串循环对照这种慢操作,而直接先得到某个字串的hash值,再用这个hash值,在数组下标里 直接找。这样速度要快上非常多,特别是数据比較多的时候。

    能够看到上面计算hash值时,出来的结果,可能并非从0開始的,如我们算出的就是5。也就是说,这个5是在数组中的某个不确定的位置,或者能够叫做是一个杂凑出来的位置。其它位置可能一直就空着在。这就是这个数组或表格叫hash表的原因了。



    但有个问题,上面的转换方法,直接相加,再取个余数,在字符串变为abdc时。结果得到的还是数字5。

    这个就是上面这个算法的一个问题了。即它不能保证一个唯一性。所以就出现了非常多hash算法的研究,如MD4,MD5,SHA-1等,来保证唯一性。


    但上面这个算法还是能够使用的,做法就是在abdc经过hash得到5后,去检查5是否被占用。假设占用了,那么就把数字加1。即为6,假设6没被占用,就填上值。假设后面某个字串算出一个值是6,但6已经被占用了,那么就再加1。再存。
    取数据的时候,能够先算出hash值后,再看里面的内容是不是你想要的,假设不是,就加1去看,最后得到一个。

    所以这里hash表的内容并非象一般的数组最開始就组织好了的,而是兴许慢慢往里添加的。


    hash表里存的内容一般能够是一个指针,这个 指针能够指向一个大的结构也是能够的。这个结构里能够有key, value信息
    h ash表也能够不是数组,你能够把它组织成一个链表,链表里的node的结构中能够有一个參数就是那个数字的hash_value。用来高速查找用。



    尽管在非常多时候hash被用在加密等场合,但在一般的应用程序代码中,也能够用它来存简单的数据存储,代码的这样的高效率将是非常。

    版权声明:本文博主原创文章,博客,未经同意不得转载。

    展开全文
  • 数组 链表 哈希表

    千次阅读 2017-12-13 15:04:31
    数组 链表 哈希表

    数组
    这里写图片描述

    数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。
    数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数,造成数组越界;当数据减少时,造成内存浪费。

    特点

    1.数组是相同数据类型的元素的集合
    2.数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起
    3.数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如,a[0]表示名字为a的数组中的第一个元素,a[1]代表数组a的第二个元素,以此类推。

    链表
    这里写图片描述
    链表有很多种不同的类型:单向链表,双向链表以及循环链表。

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

    使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。

    区别
    链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。因为数组中插入、删除数据项时,需要移动其它数据项,而链表的插入与删除时,只需要改变个别元素之间的关系即可,这大大提高了链表的删除与插入的速度。
    链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费

    哈希表

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    这里写图片描述
    左边是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表优缺点

    优点:不论哈希表中有多少数据,查找、插入、删除(有时包括删除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。
    哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。
    如果不需要有序遍历数据,并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

    缺点:它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序员必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

    java集合的主要分为三种类型:
    Set(集)
    List(列表)
    Map(映射)
    几乎有有的集合都是基于数组来实现的.
    因为集合是对数组做的封装,所以,数组永远比任何一个集合要快

    List特点:元素有放入顺序,元素可重复 ,Set特点:元素无放入顺序,元素不可重复(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的)

    Set是最简单的一种集合。集合中的对象不按特定的方式排序,并且没有重复对象。 Set接口主要实现了两个实现类:
    HashSet: HashSet类按照哈希算法来存取集合中的对象,存取速度比较快
    TreeSet :TreeSet类实现了SortedSet接口,能够对集合中的对象进行排序。
    Set 的用法:存放的是对象的引用,没有重复对象

    List的特征是其元素以线性方式存储,集合中可以存放重复对象。

    List接口主要实现类包括:
    ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问,向ArrayList()中插入与删除元素的速度慢。
    LinkedList(): 在实现中采用链表数据结构。插入和删除速度快,访问速度慢。

    展开全文
  • PHP中有一种数据类型非常重要,它就是关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。 在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型: 有一份用户名列表,存储了 10000 个...
    PHP中有一种数据类型非常重要,它就是关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。

    在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型:

    有一份用户名列表,存储了 10000 个用户名,没有重复项;
    还有一份黑名单列表,存储了 2000 个用户名,格式与用户名列表相同;
    现在需要从用户名列表中删除处在黑名单里的用户名,要求用尽量快的时间处理。

    这个问题是一个小规模的处理量,如果实际一点,2 个表都可能很大,比如有 2 亿条记录。

    我最开始想到的方法,就是做一个嵌套的循环,设用户名表有 M 条记录,黑名单列表有 N 条记录,那么,循环的次数是 M * N 次!
    PHP 版代码:


    01 <?php  
    02 foreach($arrayM as $keyM => $nameM) {  
    03 foreach($arrayN as $nameN) {  
    04 if ($nameM == $nameN) {  
    05 // 本行执行了 M * N 次!  
    06 unset($arrayM[$keyM]);  
    07 }  
    08 }  
    09 }  
    10 return $arrayM;  
    11 ?>

    另一种方式,利用数组索引。

    PHP 是一种弱类型的语言,不像 C 语言那样有严格的变量类型限制。C 语言的数组,每一个元素的类型必须一致,而且索引都是从 0 开始。
    PHP 的数组,可以用字符串作为索引,也称为关联数组。
    数组索引,有一个天然的限制就是不会重复,而且访问的时候不需要查找,可以直接定位。

    还是刚才的那个问题,我们采用另一种办法。

    把黑名单列表的用户名组织到一个数组里,数组的索引就是用户名。

    然后,遍历用户列表的时候,只需直接用 isset 查询那个用户名是否存在即可。

    PHP 版代码:


    01 <?php  
    02 $arrayHash = array();  
    03 foreach($arrayN as $nameN) {  
    04 // 本行执行了 N 次。  
    05 $arrayHash[$nameN] = 1;  
    06 }  
    07  
    08 foreach($arrayM as $keyM => $nameM) {  
    09 if (isset($arrayHash[$nameM])) {  
    10 // 本行执行了 M 次!  
    11 unset($arrayM[$keyM]);  
    12 }  
    13 }  
    14 return $arrayM;  
    15 ?>

    可以看到,优化过的代码,循环次数是 M + N 次。

    假如 M 和 N 都是 10000,优化前,循环了 1 亿次;优化后,只循环了 20000 次,差了 5000 倍!
    如果第二个程序耗时 1 秒,则第一个程序需要将近一个半小时!

    =========================================================================
    hash一个貌似比较复杂的东西,实际上理解起来并不那么夸张,这里做个笔记。

    hash,中文翻译成杂乱的东西,有人也叫它杂凑,或者翻译成什么都不是的音译“哈希”。

    简单说来,hash就是为了把一个复杂的字串,通过一定的转换,得到一个简单的数字(通常是数字)。
    如"abcd" 用各个字符的值直接相加,再取对10的余数,既(a+b+c+d),来得到一个数字,比方说结果为5,那么这个5就能在一定意义上代表这个字串 abcd了。或者说这个5也可以说是这个字串的一个标记性的东西,而且是简化了的标记,所以又有人叫这个5为字串的摘要,或指纹。
    这个5,有一个好的用处就是可以作为一个数组的下标来用,如我自己构造一个指针数组void* hash_array[10],那么我就可以把5那个位置上填上一个指针,如指向abcd字串。
    这样的话,我如果要去查询一个字串是否存在,就不需要对一个数组使用字符串循环对比这样的慢操作,而直接先得到某个字串的hash值,再用这个hash值,在数组下标里直接找,这样速度要快上很多,特别是数据比较多的时候。

    可以看到上面计算hash值时,出来的结果,可能并不是从0开始的,如我们算出的就是5。也就是说,这个5是在数组中的某个不确定的位置,或者可以叫做是一个杂凑出来的位置。其他位置可能一直就空着在。这就是这个数组或表格叫hash表的原因了。

    但有个问题,上面的转换方法,直接相加,再取个余数,在字符串变为abdc时,结果得到的还是数字5。这个就是上面这个算法的一个问题了,即它不能保证一个唯一性。所以就出现了很多hash算法的研究,如MD4,MD5,SHA-1等,来保证唯一性。
    但上面这个算法还是可以使用的,做法就是在abdc经过hash得到5后,去检查5是否被占用,如果占用了,那么就把数字加1,即为6,如果6没被占用,就填上值。如果后面某个字串算出一个值是6,但6已经被占用了,那么就再加1,再存。
    取数据的时候,可以先算出hash值后,再看里面的内容是不是你想要的,如果不是,就加1去看,最后得到一个。

    所以这里hash表的内容并不是象一般的数组最开始就组织好了的,而是后续慢慢往里增加的。
    hash表里存的内容一般可以是一个指针,这个指针可以指向一个大的结构也是可以的。这个结构里可以有key, value信息
    hash表也可以不是数组,你可以把它组织成一个链表,链表里的node的结构中可以有一个参数就是那个数字的hash_value,用来快速查找用。

    虽然在很多时候hash被用在加密等场合,但在一般的应用程序代码中,也可以用它来存贮简单的数据,这样代码的效率会高很多。

    展开全文
  • perl关联数组/哈希表

    千次阅读 2012-08-31 17:45:05
    perl关联数组/哈希表 一、数组变量的限制 二、定义 三、访问关联数组的元素 四、增加元素 五、创建关联数组 六、从数组变量复制到关联数组 七、元素的增删 八、列出数组的索引值 九、用关联数组循环 ...

    perl关联数组/哈希表

    一、数组变量的限制
    二、定义
    三、访问关联数组的元素
    四、增加元素
    五、创建关联数组
    六、从数组变量复制到关联数组
    七、元素的增删
    八、列出数组的索引和值
    九、用关联数组循环
    十、用关联数组创建数据结构
    1、(单)链表
    2、结构
    3、树

    一、数组变量的限制
         在前面讲的数组变量中,可以通过下标访问其中的元素。例如,下列语句访问数组@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行后,输出次序为左子树、右子树、节点,则为“右序遍历”。
         可以用同样的方法,即连接字符串构成下标,来创建其它的数据结构,如数据库等。
    展开全文
  • 经过一上午的学习,对数据结构有了新的认识理解 数组 数组是由有限个相同类型的变量所组成的有序集合,它可以进行元素的插入、删除、查找等操作,它的物理存储方式是顺序存储,访问方式是随机访问,利用下标查找...
  • 示例: 你可以使用一个变量来存放一个数组,通过这个数组对变量分配多个值,在值之间,值需要用分隔号隔开,下面来创建一个示例: ... 创建一个空的哈希表,可以使用如下语法:  $hashtable = @{}  
  • LeetCode 1.两数之数组哈希表

    千次阅读 多人点赞 2020-06-15 13:39:52
    给定一个整数数组 nums 一个目标值 target,请你在该数组中找出为目标值的那 两个 整数,并返回他们的数组下标。  ...
  • 第九章 关联数组/哈希表by flamephoenix一、数组变量的限制二、定义三、访问关联数组的元素四、增加元素五、创建关联数组六、从数组变量复制到关联数组七、元素的增删八、列出数组的索引值九、用关联数组循环十、...
  • 全部翻译内容pdf文档下载地址: ... 本书目前在github上由laruence(http://www.laruence.com)walu(http://www.walu.cc)两位大牛组织翻译. 该翻译项目地址为: https://github.com/walu/phpbook 本书在gith
  • 关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。 在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型: 有一份用户名列表,存储了 10000 个用户名,没有重复项; 还有一份黑名单...
  • 数组、链表、字典、哈希表学习

    千次阅读 2017-08-25 10:08:01
     特将三者基础概念异同点总结如下,望各位同道开发者不吝赐教,共同学习。数组——对象数量较少且数量固定时优先考虑;字典——需要进行频繁的搜索时优先考虑;链表——对象数量是动态的且搜索不是优先选...
  • 哈希表理解

    2020-04-03 16:12:57
    哈希表什么是哈希表哈希表怎么存储数据的?哈希冲突处理哈希冲突哈希表的扩容哈希表怎么读取数据 什么是哈希表? 百度百科: 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据...
  • UVM学习之路(4)— SystemVerilog的动态数组、队列和关联数组 一、前言 SystemVerilog提供的动态数组类型,可以在仿真时分配空间或者调整宽度,这样在仿真中就可以使用最小的存储量。 SystemVerilog引进了一种新的...
  • 关联数组

    2019-08-03 16:35:07
    通常的数组在填充时会隐式或者显示指定数组下标,但JS中数组可以以名字的形式为元素赋值,这就形成了关联数组,如: var arr=new Array(); arr["china"]="beijing,niaoling,hulan"; arr["usa...
  • 通过学习官方APIcookbook,我总结了如下原因: 1.从API中我们了解到,ArrayObject都是动态类,也就是我们可以给他们动态添加属性。 var obj:Object = new Object(); obj.prop1 = "value1"; obj....
  • 1.题目 LeetCode: 217. 存在重复元素 【easy】 给定一个整数数组,判断是否存在重复元素。 如果存在一值在数组中出现至少两次,函数返回 true 。...遍历数组,每遍历一个元素就判断是否在哈希表中,如
  • 哈希表JS简化 在计算中,哈希表哈希表)是一种实现关联数组抽象数据类型的数据结构,该结构可以将键映射到值。 哈希表使用哈希函数来计算存储桶或插槽数组的索引,从中可以找到所需的值。
  • 算法有高效的,也有拙劣的,好的算法能够达到四两拨千斤的效果,但差的算法会消耗大量的内存运行时间。效果相差甚远。 算法可以应用在以下场景: 1、运算 2、查找 3、排序 4、最优决策 二、数据结构 数据结构是...
  • linux shell中的数组和关联数组

    千次阅读 2016-02-24 11:46:37
    数组的定义以及赋值 http://blog.chinaunix.net/uid-23886490-id-3631943.html 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 # 定义数组的方式1 array_var=(1 2 3 4 5) # 定义数组的方式2 array_var...
  • Perl教学 第九篇 关联数组(哈希表)

    千次阅读 2006-06-16 04:26:00
    一、数组变量的限制在前面讲的数组变量中,可以通过下标访问其中的元素。例如,下列语句访问数组@array的第三个元素:$scalar = $array[2];虽然数组很有用,但它们有一个显著缺陷,即很难记住哪个元素存贮的什么内容...
  • shell关联数组

    2019-01-21 09:26:00
    下标数组元素是通过数组下标(数组下标可以是算术表达式,其结果必须是一个整数)来访问的,但是这种访问方式在表达某些关联性很强的数据时会存在限制。shell 提供了另外一种数组,其可以使用任意的字符串作为下标...
  • 单独的链哈希表 一个集合,其元素为键值对,并通过单独的链接哈希表存储。 SeparateChainingHashTable共享Swift Dictionary的相同功能。
  • 关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。 在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型: 有一份用户名列表,存储了 10000 个用户名,没有重复项; 还有一份黑名单...
  • 哈希表 hash table Note:本篇内容总结自《漫画算法》 时间复杂度 把程序的相对执行时间函数 T(n) 简化为一个数量级,用大写的O表示,T(n)=O(f(n))。 时间复杂度的推导原则: 如果运行时间是常数量级,则用...
  • shell的 关联数组 普通数组

    千次阅读 2016-06-12 00:07:34
    前言 普通数组中判断元素是否存在的时间复杂度一般为O(n),是因为大家一般的做法都是遍历一...在c语言里这种方法经常使用,这里介绍在shell的语法中我们如何利用关联数组和key值唯一性来提高脚本的执行效率
  • 轻松学习C#的哈希表

    2021-01-20 06:39:48
    在C#语言中,还有一种用于快速搜索而组织的键/值组合的数组,这种数组叫做关联数组,也叫做哈希表(Hashtable)。  哈希表也在System.Collection命名空间下,用于处理表现类似key/value的键值对,其中key通常用来...
  • c#哈希表和字典的区别

    千次阅读 2018-10-24 11:22:52
    Hashtable  Dictionary &lt;K, V&gt; 类型  1):单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分. 2):多线程程序中推荐使用 Hashtable, 默认的 Hashtable ...
  • shell 的关联数组 Shell Associative Array  bashi没有原生的对于类似hash table的支持,不像perl或python. 下标数组元素是通过数组下标(数组下标可以是算术表达式,其结果必须是一个整数)来访问的,但是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,624
精华内容 16,649
关键字:

关联数组和哈希表