Это слегка измененная версия электронного письма, которое я отправил в список рассылки Perl Beginners, отвечая на этот же вопрос.
Высказывание
my $hash_info = %hash;
Вы получите либо 0 (если хеш пуст), либо соотношение используемых к
общее количество ведер Эта информация почти, но не полностью,
бесполезен для тебя. Чтобы понять, что это значит, вы должны сначала
понять, как работает хеширование.
Давайте реализуем хеш с помощью Perl 5. Первое, что нам нужно, это
функция хеширования. Надеемся, что хэширующие функции превращают строки в
уникальные номера. Примеры реальных сильных хеш-функций:
MD5 или SHA1 , но они имеют тенденцию быть слишком медленными для общего использования, поэтому
люди, как правило, используют слабее (то есть те, которые производят менее уникальный результат)
функции для хеш-таблиц. Perl 5 использует Боба Дженкинса [по одному]
алгоритм, который имеет хороший компромисс между уникальностью и скоростью. За наших
Например, я буду использовать очень слабую функцию хеширования:
#!/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";
}
Поскольку функции хеширования имеют тенденцию возвращать числа из диапазона, большего, чем мы хотим, обычно вы используете по модулю , чтобы уменьшить диапазон чисел, который он дает
назад:
#!/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";
Как видно из этого примера, возможно, что одно ведро имеет
больше пар ключ / значение, чем остальные. Это плохая ситуация, чтобы быть
в. Это заставляет хеш быть медленным для этого ведра. Это один из
использует отношение используемых к общему количеству сегментов, которые возвращают хэши в
скалярный контекст. Если хеш говорит, что только несколько ведер
используется, но они имеют много ключей в хэше, то вы знаете, у вас есть
проблема.
Чтобы узнать больше о хэшах, задайте здесь вопросы о том, что я сказал,
или читайте о них .