Быстрая строковая контрольная сумма функционирует в генерирующихся значениях Perl в 0.. 2^32-1 диапазон
Я ищу строковую функцию контрольной суммы 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) избегать коллизий. В этом приложении случайные коллизии являются полностью нефатальными, но очевидно я хочу избежать их до такой степени, что это возможно.
Учитывая эти требования, что лучший способ состоит в том, чтобы решить это?
3 ответа
Достаточно любой хеш-функции - просто обрежьте ее до 4 байтов и преобразуйте в число. Хорошие хеш-функции имеют случайное распределение, и это распределение будет постоянным независимо от того, где вы усекаете строку.
Я предлагаю Digest :: MD5 , потому что это самая быстрая реализация хеширования, которая входит в стандартную комплектацию Perl. . String :: CRC, как упоминает Пим, также реализован в 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)
Не знаю, как быстро, но вы можете попробовать Строка::CRC.
Из perldoc -f распаковать:
For example, the following computes the same number as the
System V sum program:
$checksum = do {
local $/; # slurp!
unpack("%32W*",<>) % 65535;
};