Функция быстрой проверки контрольной суммы в Perl, генерирующая значения в диапазоне 0..2 ^ 32-1

Question

Я ищу функцию контрольной суммы строки Perl со следующими свойствами:

• Ввод: строка Unicode неопределенной длины ($string)
• Выходные данные: целое число без знака ($hash), для которого выполняется 0 <= $hash <= 2^32-1 (от 0 до 4294967295, что соответствует размеру 4-байтового целого числа без знака MySQL)

Псевдо-код:

sub checksum {
    my $string = shift;
    my $hash;
    ... checksum logic goes here ...
    die unless ($hash >= 0);
    die unless ($hash <= 4_294_967_295);
    return $hash;
}

В идеале функция контрольной суммы должна быть быстрой и должна генерировать значения несколько равномерно в целевом пространстве (0 .. 2^32-1), чтобы избежать столкновений. В этом приложении случайные столкновения не являются фатальными, но, очевидно, я хочу избежать их настолько, насколько это возможно.

Учитывая эти требования, как лучше всего решить эту проблему?

Answer 1

Любой хеш-функции будет достаточно - просто обрежьте ее до 4 байтов и преобразуйте в число. Хорошие хеш-функции имеют случайное распределение, и это распределение будет постоянным независимо от того, где вы усекаете строку.

Я предлагаю Дайджест :: MD5 , потому что это самая быстрая реализация хеша, которая поставляется со стандартным Perl. String :: CRC, как упоминает Pim, также реализован на C и должен быть быстрее.

Вот как вычислить хеш и преобразовать его в целое число:

use Digest::MD5 qw(md5);
my $str = substr( md5("String-to-hash"), 0, 4 );
print unpack('L', $str);  # Convert to 4-byte integer (long)

Answer 2

Не знаю, как быстро, но вы можете попробовать String :: CRC .

Answer 3

С perldoc -f unpack:

        For example, the following computes the same number as the
        System V sum program:

            $checksum = do {
                local $/;  # slurp!
                unpack("%32W*",<>) % 65535;
            };