Un rapide de chaîne de somme de contrôle de la fonction en Perl générer des valeurs dans l'0..2^32-1 gamme

Je suis à la recherche d'un Perl chaîne de somme de contrôle de la fonction avec les propriétés suivantes:

  • D'entrée: chaîne Unicode de longueur indéfinie ($string)
  • De sortie: entier non signé ($hash), pour qui 0 <= $hash <= 2^32-1 détient (0 à 4294967295, correspondant à la taille de 4 octets MySQL unsigned int)

Pseudo-code:

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

Idéalement, la fonction de la somme de contrôle devrait être rapide à exécuter et devrait générer des valeurs un peu de manière uniforme dans l'espace cible (0 .. 2^32-1) pour éviter les collisions. Dans cette application aléatoire des collisions sont totalement non-mortels, mais, évidemment, je veux éviter, dans la mesure où c'est possible.

compte tenu de ces exigences, quelle est la meilleure façon de résoudre ce problème?

Vous voulez éviter les collisions de toutes les chaînes, mais seulement de 4 milliards d'possible digère? Pourquoi utiliser un entier important? Que diriez-vous simplement en utilisant quelque chose comme MD5, même si vous devez stocker le recueil comme une chaîne de caractères?
"Vous voulez éviter les collisions avec tous les possible des chaînes" - Non, comme indiqué dans la question, j'ai simplement "vous voulez les éviter dans la mesure où c'est possible".
"Pourquoi est-utilisation d'un nombre entier d'important?" - Comme indiqué dans la question de la somme de contrôle seront stockées dans un "4 octets MySQL unsigned int".

OriginalL'auteur knorv | 2009-12-22

  1. 12

    Toute fonction de hachage suffira simplement de le tronquer à 4 octets et le convertir en un nombre. Bon les fonctions de hachage ont une distribution aléatoire, et cette distribution sera constante, peu importe où vous tronquez la chaîne.

    Je suggère Digest::MD5 parce qu'il est le plus rapide de hachage de mise en œuvre qui vient avec Perl standard. String::CRC, comme Pim mentionne, est également mise en œuvre en C et devrait être plus rapide.

    Voici comment calculer le hash et le convertir en un nombre entier:

    use Digest::MD5 qw(md5);
my $str = substr( md5("String-to-hash"), 0, 4 );
print unpack('L', $str);  # Convert to 4-byte integer (long)
    B::hash est également livré avec un core de perl, utilise le noyau interne fonction de hachage, est plus rapide que MD5 et renvoie un hexified entier de 32 bits. Mais pas aussi sûr que MD5.

    OriginalL'auteur rjh

  2. 4

    Ne sais pas comment c'est rapide, mais vous pouvez essayer de String::CRC.

    OriginalL'auteur Pim

  3. 3

    De perldoc -f unpack:

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

            $checksum = do {
                local $/;  # slurp!
                unpack("%32W*",<>) % 65535;
            };
    Cette 32bit somme de tous les bits est une très mauvaise valeur de hachage pour les distributions aléatoires. Toute fonction de hachage est mieux, même les plus simples.
    Bien sûr, mais c'est le même problème que le Système V sum programme. Voir le paragraphe. Ou êtes-vous en soutenant que sum est sans doute cassé? Dans ce cas, il n'est pas question de Perl.
    sum est à peu près aussi rapide que vous aurez, bien que, comme mentionné ci-dessus, il n'est pas très robuste. Vous pouvez l'améliorer légèrement en utilisant la taille, par exemple $_ = <>; unpack("%32W*",$_)%65535 . length($_). Tout ce qui doit être plus robustes devraient utiliser Digest::MD5 ou Digest::SHA, etc.

    OriginalL'auteur Randal Schwartz