Perl中的快速字符串校验和函数,生成0..2 ^ 32-1范围内的值

Question

我正在寻找具有以下属性的Perl字符串校验和函数:

• 输入:未定义长度的Unicode字符串($string)
• 输出:无符号整数($hash),0 <= $hash <= 2^32-1保持(0到4294967295,匹配4字节MySQL unsigned int的大小)

伪代码:

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个字节并转换为数字即可.好的哈希函数具有随机分布,无论您在哪里截断字符串,此分布都将是常量.

我建议使用Digest :: MD5,因为它是Perl标配的最快哈希实现.字符串:: 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

从perldoc -f unpack：

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

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