Perl 内部结构详解 -- PerlGuts Illustrated (4 HV)
HVhash 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 为空。
C:&;perl -MDevel::Peek -e "%a=0..5000; Dump %a" SV = RV(0x299120) at 0x299114 REFCNT = 1 FLAGS = (TEMP,ROK) RV = 0x182a9cc SV = PVHV(0x29e7bc) at 0x182a9cc REFCNT = 2 FLAGS = (SHAREKEYS) ARRAY = 0x18d12c4 (0:2236,1:1341,2:417,3:85,4:14,5:3) (ARRAY中有2236个位置未占用, 有1341个位置包含1个元素, 有417个位置包含2个元素, 有85个位置包含3个元素, 有14个位置包含4个元素, 有3个位置包含5个元素, 1341+417+85+14+3=1860,正好是FILL的值 ) hash quality = 98.9% KEYS = 2501 (hash包含的元素个数) FILL = 1860 (hash code占用多少ARRAY位置,说明有多个值占用一个坑) MAX = 4095 (ARRAY分配了4096) RITER = -1 EITER = 0x0 Elt "1648" HASH = 0x2bb13004 SV = IV(0x185a840) at 0x185a844 REFCNT = 1 FLAGS = (IOK,pIOK) IV = 1649 Elt "3596" HASH = 0x4b03006 SV = IV(0x18a4e38) at 0x18a4e3c REFCNT = 1 FLAGS = (IOK,pIOK) IV = 3597 Elt "3074" HASH = 0x1256006 SV = IV(0x18beff0) at 0x18beff4 REFCNT = 1 FLAGS = (IOK,pIOK) IV = 3075下边用一个例子说明RITER,EITER的变化过程。 取上边3个元素的hash code并与MAX 4095做& 运算,求得前三个元素在数组ARRAY中位置为4 6 6。
printf "%dn",0x2bb13004 & 4095; printf "%dn",0x4b03006 & 4095; printf "%dn",0x1256006 & 4095; output: 4 6 6依次取hash 值并观察 RITER,EITER的变化。 use Devel::Peek; %a = 0..5000; #~ Dump %a; $i = 0; while( my($a,$b) =each %a){ last if $i++ > 4; print "$a $bn"; Dump %a; }值输出,同上边相同:
1648 1649 3596 3597 3074 3075 2266 2267 1178 1179RITER EITER在循环过程中ARRAY位置4 6 6与预计相同。
SV = RV(0x298f98) at 0x298f8c REFCNT = 1 FLAGS = (TEMP,ROK) RV = 0x182a8cc SV = PVHV(0x29e59c) at 0x182a8cc REFCNT = 2 FLAGS = (OOK,SHAREKEYS) ARRAY = 0x18d1164 (0:2236,5:3) hash quality = 98.9% KEYS = 2501 FILL = 1860 MAX = 4095 RITER = 4 EITER = 0x18a3c50 SV = RV(0x298f98) at 0x298f8c REFCNT = 1 FLAGS = (TEMP,5:3) hash quality = 98.9% KEYS = 2501 FILL = 1860 MAX = 4095 RITER = 6 EITER = 0x18c3f48 SV = RV(0x298f98) at 0x298f8c REFCNT = 1 FLAGS = (TEMP,5:3) hash quality = 98.9% KEYS = 2501 FILL = 1860 MAX = 4095 RITER = 6 EITER = 0x18ba91c SV = RV(0x298f98) at 0x298f8c REFCNT = 1 FLAGS = (TEMP,5:3) hash quality = 98.9% KEYS = 2501 FILL = 1860 MAX = 4095 RITER = 9 EITER = 0x18b1c4c SV = RV(0x298f98) at 0x298f8c REFCNT = 1 FLAGS = (TEMP,5:3) hash quality = 98.9% KEYS = 2501 FILL = 1860 MAX = 4095 RITER = 11 EITER = 0x1899dcc (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |