【转载】perl中获得哈希（hash）长度的办法

2009年05月09日 星期六 15:11

今天bean向我请教perl中如何知道一个hash表的长度，一时难住了我，心有不甘（“呼呼，好不容易被bean请教一回问题，怎能只回答‘不知道’三个字呢”），于是上网查。经过测试，发现如下办法可用，记在这里备忘：

 

$length = keys %hashname;

 

则$length中得到的直接是该hash的key的个数。

 

------------------------

 

呜呜，本来本篇的题目是写成“perl中获得哈希（hash）长度的三种办法”的，结果经过测试，原来写的两种方法都不可行。原来以为也可以用的两种方法分别是：

 

1、 $length = %hashname;

 

得到的返回值比较有趣，是一个复合值： A/B，其中A是实际上该hash中实际使用的单位的个数，B是事实上分配给该hash多少个单位。特别是，后面的这个B值，是呈指数增长的（8，16，32，...），应该是和perl中的hash实现方法有关。

 

例如： %hashname = (apple=>01, orange=>02, banana =>03);

 

$length = %hashname;

 

print "$length";

 

那么执行之后的输出值为 3/8。

 

2、强制类型转换一下，把hash强制成一个标量： scalar(%hashname)

 

该函数的取值同上述方法1的得到值。

 

注：如果是一个数组例（如scalar(@arrray)）而不是哈希，则该函数直接得到数组中的元素个数。

 

上述两个方法，对本任务不可用的主要原因是：这里“实际使用单位”和“分配的单位”不知道是以什么表达的。也许是某种内存分配的块数？

 

继续查找资料，感觉下面这个解释比较清晰：

 

“散列在标量上下文下返回的字符串“xxx/yyy”，实际上是斜杠分割的 xhv_fill 和 xhv_max，

至于 xhv_fill 和 xhv_max 是什么，可以阅读《Perl 高级编程》。

我 在这里简要介绍一下，众所周知，所谓“散列表”，是指采用“散列函数”将任意一个字符串（key）映射成一个“有限范围”内的整数，从而通过访问以该整数 为下标的数组元素，来访问 key 对应的 value 的一种算法。因为没有任何一种散列函数能够将无穷可能地 key 映射到有限范围的数组下标空间，因此，必然会产生多个 key 使用同一个散列值的情形。此时将产生冲突，依照惯例，解决冲突的办法就是为每个散列值准备一个 value 链表而不仅仅是单个的 value，xhv_fill 是指最多能有多少个 key 使用同一个散列值（每个散列值对应的链表的最大长度），xhv_max 则是值最多能有多少个哈希值（散列函数的值空间大小）。

按说 hash 最多能储存的 key 应该等于 xhv_fill × xhv_max，然而当 xhv_fill ÷ xhv_max 比值下降时，

hash 的性能会非常糟糕。因此，Perl 会在 xhv_fill / xhv_max 增大到一定程度时，将 xhv_max 翻倍，

从而减小 xhv_fill / xhv_max，提高 hash 的访问速度。