注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

FY

Johnson 's Blog

 
 
 

日志

 
 

PerlGuts Illustrated (4 HV)  

2012-08-06 22:00:11|  分类: perl |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

HV

hash table是最复杂的数据结构,HV使用HE struct表示key/value结构,使用HEK表示key。


GvSTASH 当这个hash表示一个命名空间(模块),STASH指向Perl 语法树的一个节点,用来实现reset。(略过,未搞明白)

ARRAY 数组用于分配储存hash值,它的大小必须是2的n次方,当hash为空情况下,ARRAY为NULL。定位hash值在ARRAY中的位置只使用hash code的最后几位,ARRAY[HASH & MAX],稍后用一个例子说明。

FILL 表示ARRAY数组中有多少个不为NULL的节点。多个hash code可能共享ARRAY数组的一个节点,如上图所示。

MAX 表示ARRAY数组分配的空间减1,最小值为7,即使hash为空。

HE 包含三个指针,分别指向下一个节点,key和value。

HEK 包含hash code,key长度和key值。

RITER, EITER 这两个字段用来实现遍历hash 元素,RITER指向ARRAY的index,EITER指向HE的指针。当循环的时候,查找EITER->next值,为空的情况下RITER增1,直到ARRAY[RITER]不为空。初始情况RITER为-1,EITER 为空。

  1. C:\>perl -MDevel::Peek -e "%a=0..5000; Dump \%a"  
  2. SV = RV(0x299120) at 0x299114  
  3.   REFCNT = 1  
  4.   FLAGS = (TEMP,ROK)  
  5.   RV = 0x182a9cc  
  6.   SV = PVHV(0x29e7bc) at 0x182a9cc  
  7.     REFCNT = 2  
  8.     FLAGS = (SHAREKEYS)  
  9.     ARRAY = 0x18d12c4  (0:2236, 1:1341, 2:417, 3:85, 4:14, 5:3)  
  10.         (ARRAY中有2236个位置未占用,  
  11.          有1341个位置包含1个元素,  
  12.          有417个位置包含2个元素,  
  13.          有85个位置包含3个元素,  
  14.          有14个位置包含4个元素,  
  15.          有3个位置包含5个元素,  
  16.          1341+417+85+14+3=1860,正好是FILL的值  
  17.         )  
  18.     hash quality = 98.9%  
  19.     KEYS = 2501 (hash包含的元素个数)  
  20.     FILL = 1860 (hash code占用多少ARRAY位置,说明有多个值占用一个坑)  
  21.     MAX = 4095  (ARRAY分配了4096)  
  22.     RITER = -1  
  23.     EITER = 0x0  
  24.     Elt "1648" HASH = 0x2bb13004  
  25.     SV = IV(0x185a840) at 0x185a844  
  26.       REFCNT = 1  
  27.       FLAGS = (IOK,pIOK)  
  28.       IV = 1649  
  29.     Elt "3596" HASH = 0x4b03006  
  30.     SV = IV(0x18a4e38) at 0x18a4e3c  
  31.       REFCNT = 1  
  32.       FLAGS = (IOK,pIOK)  
  33.       IV = 3597  
  34.     Elt "3074" HASH = 0x1256006  
  35.     SV = IV(0x18beff0) at 0x18beff4  
  36.       REFCNT = 1  
  37.       FLAGS = (IOK,pIOK)  
  38.       IV = 3075  
下边用一个例子说明RITER, EITER的变化过程。

取上边3个元素的hash code并与MAX 4095做& 运算,求得前三个元素在数组ARRAY中位置为4 6 6。

  1. printf "%d\n",  0x2bb13004 & 4095;  
  2. printf "%d\n",  0x4b03006 & 4095;  
  3. printf "%d\n",  0x1256006 & 4095;  
  4.   
  5. output:  
  6. 4  
  7. 6  
  8. 6  
依次取hash 值并观察RITER, EITER的变化。
  1. use Devel::Peek;  
  2.   
  3. %a = 0..5000;  
  4. #~ Dump \%a;  
  5.   
  6. $i = 0;  
  7. while( my($a,$b) =each %a){  
  8.     last if $i++ > 4;  
  9.     print "$a $b\n";  
  10.     Dump \%a;  
  11. }  
值输出,同上边相同:

  1. 1648 1649  
  2. 3596 3597  
  3. 3074 3075  
  4. 2266 2267  
  5. 1178 1179  
RITER EITER在循环过程中ARRAY位置4 6 6与预计相同。

  1. SV = RV(0x298f98) at 0x298f8c  
  2.   REFCNT = 1  
  3.   FLAGS = (TEMP,ROK)  
  4.   RV = 0x182a8cc  
  5.   SV = PVHV(0x29e59c) at 0x182a8cc  
  6.     REFCNT = 2  
  7.     FLAGS = (OOK,SHAREKEYS)  
  8.     ARRAY = 0x18d1164  (0:2236, 1:1341, 2:417, 3:85, 4:14, 5:3)  
  9.     hash quality = 98.9%  
  10.     KEYS = 2501  
  11.     FILL = 1860  
  12.     MAX = 4095  
  13.     RITER = 4  
  14.     EITER = 0x18a3c50  
  15. SV = RV(0x298f98) at 0x298f8c  
  16.   REFCNT = 1  
  17.   FLAGS = (TEMP,ROK)  
  18.   RV = 0x182a8cc  
  19.   SV = PVHV(0x29e59c) at 0x182a8cc  
  20.     REFCNT = 2  
  21.     FLAGS = (OOK,SHAREKEYS)  
  22.     ARRAY = 0x18d1164  (0:2236, 1:1341, 2:417, 3:85, 4:14, 5:3)  
  23.     hash quality = 98.9%  
  24.     KEYS = 2501  
  25.     FILL = 1860  
  26.     MAX = 4095  
  27.     RITER = 6  
  28.     EITER = 0x18c3f48  
  29. SV = RV(0x298f98) at 0x298f8c  
  30.   REFCNT = 1  
  31.   FLAGS = (TEMP,ROK)  
  32.   RV = 0x182a8cc  
  33.   SV = PVHV(0x29e59c) at 0x182a8cc  
  34.     REFCNT = 2  
  35.     FLAGS = (OOK,SHAREKEYS)  
  36.     ARRAY = 0x18d1164  (0:2236, 1:1341, 2:417, 3:85, 4:14, 5:3)  
  37.     hash quality = 98.9%  
  38.     KEYS = 2501  
  39.     FILL = 1860  
  40.     MAX = 4095  
  41.     RITER = 6  
  42.     EITER = 0x18ba91c  
  43. SV = RV(0x298f98) at 0x298f8c  
  44.   REFCNT = 1  
  45.   FLAGS = (TEMP,ROK)  
  46.   RV = 0x182a8cc  
  47.   SV = PVHV(0x29e59c) at 0x182a8cc  
  48.     REFCNT = 2  
  49.     FLAGS = (OOK,SHAREKEYS)  
  50.     ARRAY = 0x18d1164  (0:2236, 1:1341, 2:417, 3:85, 4:14, 5:3)  
  51.     hash quality = 98.9%  
  52.     KEYS = 2501  
  53.     FILL = 1860  
  54.     MAX = 4095  
  55.     RITER = 9  
  56.     EITER = 0x18b1c4c  
  57. SV = RV(0x298f98) at 0x298f8c  
  58.   REFCNT = 1  
  59.   FLAGS = (TEMP,ROK)  
  60.   RV = 0x182a8cc  
  61.   SV = PVHV(0x29e59c) at 0x182a8cc  
  62.     REFCNT = 2  
  63.     FLAGS = (OOK,SHAREKEYS)  
  64.     ARRAY = 0x18d1164  (0:2236, 1:1341, 2:417, 3:85, 4:14, 5:3)  
  65.     hash quality = 98.9%  
  66.     KEYS = 2501  
  67.     FILL = 1860  
  68.     MAX = 4095  
  69.     RITER = 11  
  70.     EITER = 0x1899dcc  
http://blog.csdn.net/ustbhacker/article/details/7823367
  评论这张
 
阅读(118)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018