什么是4/16的哈希？

Question

if (%hash){
     print "That was a true value!\n";
}

如果(并且仅当)散列具有至少一个键值对,那将是真实的.

实际结果是一个内部调试字符串,对维护Perl的人有用.它看起来像"4/16",但是当散列是非空时,该值保证为真,而当它为空时,该值保证为假. - 小马书

这4/16是什么？谁能告诉我一个小程序,我可以看到结果是4/16？

Answer 1

来自perldoc perldata:

如果在标量上下文中计算哈希值,则在哈希值为空时返回false.如果有任何键/值对,则返回true; 更准确地说,返回的值是一个字符串,由使用的桶数和分配的桶数组成,用斜杠分隔.这非常有用,只是为了找出Perl的内部哈希算法是否在您的数据集上表现不佳.例如,你在哈希中粘贴10,000个东西,但是在标量上下文中评估%HASH显示"1/16",这意味着只触摸了16个桶中的一个,并且可能包含所有10,000个项目.

所以,4/16将使用/分配计数的桶,以及类似下面的内容将显示此值:

%hash = (1, 2);
print scalar(%hash); #prints 1/8 here

Answer 2

哈希是链表的数组.散列函数将密钥转换为一个数字,该数字用作存储值的数组元素("bucket")的索引.多个密钥可以散列到相同的索引("冲突"),这是由链表处理的情况.

分数的分母是桶的总数.

分数的分子是具有一个或多个元素的桶的数量.

对于具有相同元素数量的哈希值,数字越大越好.返回6/8的碰撞比返回4/8的碰撞少.

Answer 3

这是我发送到Perl Beginners邮件列表的电子邮件的略微修改版本,回答了同样的问题.

话

my $hash_info = %hash;

会得到你0(如果哈希是空的)或者用于总桶数的比率.这些信息对您来说几乎是无用的,但并非完全无用.要理解这意味着什么,您必须首先了解散列是如何工作的.

让我们使用Perl 5实现一个哈希.我们需要的第一件事是哈希函数.散列函数将字符串转换为有希望的唯一数字.实际强散列函数的示例是 MD5或SHA1,但它们往往对于常见用途来说太慢,因此人们倾向于使用较弱的(即产生较少唯一输出的函数)函数用于散列表.Perl 5使用Bob Jenkins [一次一个]算法,该算法对速度的唯一性进行了很好的权衡.对于我们的示例,我将使用非常弱的散列函数:

#!/usr/bin/perl

use strict;
use warnings;

sub weak_hash {
       my $key  = shift;
       my $hash = 1;
       #multiply every character in the string's ASCII/Unicode value together
       for my $character (split //, $key) {
               $hash *= ord $character;
       }
       return $hash;
}

for my $string (qw/cat dog hat/) {
       print "$string hashes to ", weak_hash($string), "\n";
}

因为散列函数倾向于返回大于我们想要的范围的数字,所以通常使用modulo来减少它返回的数字范围:

#!/usr/bin/perl

use strict;
use warnings;

sub weak_hash {
       my $key  = shift;
       my $hash = 1;
       #multiply every character in the string's ASCII/Unicode value together
       for my $character (split //, $key) {
               $hash *= ord $character;
       }
       return $hash;
}

for my $string (qw/cat dog hat/) {
       # the % operator is constraining the number
       # weak_hash returns to 0 - 10
       print "$string hashes to ", weak_hash($string) % 11, "\n";
}

既然我们有一个散列函数,我们需要一个地方来保存键和值.这称为哈希表.哈希表通常是一个数组,其元素称为桶(这些是比率所讨论的桶).存储桶将保存散列到相同数字的所有键/值对:

#!/usr/bin/perl

use strict;
use warnings;

sub weak_hash {
       my $key  = shift;
       my $hash = 1;
       for my $character (split //, $key) {
               $hash *= ord $character;
       }
       return $hash;
}

sub create {
       my ($size) = @_;

       my @hash_table;

       #set the size of the array
       $#hash_table = $size - 1;

       return \@hash_table;
}


sub store {
       my ($hash_table, $key, $value) = @_;

       #create an index into $hash_table
       #constrain it to the size of the hash_table
       my $hash_table_size = @$hash_table;
       my $index           = weak_hash($key) % $hash_table_size;

       #push the key/value pair onto the bucket at the index
       push @{$hash_table->[$index]}, {
               key   => $key,
               value => $value
       };

       return $value;
}

sub retrieve {
       my ($hash_table, $key) = @_;

       #create an index into $hash_table
       #constrain it to the size of the hash_table
       my $hash_table_size = @$hash_table;
       my $index           = weak_hash($key) % $hash_table_size;

       #get the bucket for this key/value pair
       my $bucket = $hash_table->[$index];

       #find the key/value pair in the bucket
       for my $pair (@$bucket) {
               return $pair->{value} if $pair->{key} eq $key;
       }

       #if key isn't in the bucket:
       return undef;
}

sub list_keys {
       my ($hash_table) = @_;

       my @keys;

       for my $bucket (@$hash_table) {
               for my $pair (@$bucket) {
                       push @keys, $pair->{key};
               }
       }

       return @keys;
}

sub print_hash_table {
       my ($hash_table) = @_;

       for my $i (0 .. $#$hash_table) {
               print "in bucket $i:\n";
               for my $pair (@{$hash_table->[$i]}) {
                       print "$pair->{key} => $pair->{value}\n";
               }
       }
}

my $hash_table = create(3);

my $i = 0;
for my $key (qw/a b c d g j/) {
       store($hash_table, $key, $i++);
}
print_hash_table($hash_table);

print "the a key holds: ", retrieve($hash_table, "a"), "\n";

从这个例子可以看出,一个桶可能比其他桶具有更多的键/值对.这是一个糟糕的情况.它导致该桶的哈希缓慢.这是在标量上下文中哈希返回的已用于总桶数的比率之一.如果哈希表示只使用了几个桶,但它们在哈希中有很多键,那么你知道你有问题.

要了解有关哈希的更多信息,请在此处提出有关我所说的内容的问题,或阅读有关它们的内容.