On Sat, Mar 26, 2011 at 03:53, Sunita Rani Pradhan
<[email protected]> wrote:
> Thanks Alan . I had got this piece of info from google but I do not
> understand clearly what it wants to define . It would be good , if you
> can explain bit more .
snip
If you want to know how many key/value pairs are in a hash, you can say
my $count = keys %hash;
If you want a reference to %hash, you can say
my $ref = \%hash;
Saying
my $hash_info = %hash;
Will get you either 0 (if the hash is empty) or the ratio of used to
total buckets. This information is almost, but not completely,
useless to you. To understand what that means you must first
understand how hashing works.
Lets implement a hash using Perl 5. The first thing we need is a
hashing function. Hashing functions turn strings into, hopefully,
unique numbers. Examples of real strong hashing functions are
[MD5][0] or [SHA1][1], but they tend to be too slow for common use, so
people tend to use weaker (i.e. ones that produce less unique output)
functions for hash tables. Perl 5 uses Bob Jenkins [one-at-a-time]
algorithm, which has a nice tradeoff of uniqueness to speed. For our
example, I will use a very weak hashing function:
#!/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";
}
Because hashing functions tend to give back number that are far apart,
you usually use [modulo][3] to reduce the range of numbers it gives
back:
#!/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";
}
Now that we have a hashing function, we need somewhere to save the key
and value. This is called the hash table. The hash table is often an
array whose elements are called buckets (these are the buckets that
the ratio is talking about). A bucket will hold all of the key/value
pairs that hash to the same number:
#!/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";
As we can see from this example, it is possible for one bucket have
more key/value pairs than the others. This is a bad situation to be
in. It cause the hash to be slow that bucket. This is one of the
uses of the ratio of used to total buckets that hashes return in
scalar context. If the hash says that only a few buckets are being
used, but they are lots of keys in the hash, then you know you have a
problem.
To learn more about hashes, ask questions here about what I have said,
or [read about them][4].
[0]: http://en.wikipedia.org/wiki/Md5
[1]: http://en.wikipedia.org/wiki/Sha1
[2]: http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-time
[3]: http://en.wikipedia.org/wiki/Modulo_operation
[4]: http://en.wikipedia.org/wiki/Hash_table
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
--
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
http://learn.perl.org/
