Forum Programmation.perl Equivalent en Perl de Hashcode en Java

Posté par .
Tags : aucun
1
29
avr.
2010
Bonjour,

Je dispose de code Java que je voudrais réécrire en Perl, et j'ai toutes les peines du monde sur la fonction longHashcode(String str) que voici :

    public static long longHashCode(String str) {
long h = 0;
byte val[] = str.getBytes();
int len = str.length();
for (int i = 0; i < len; i++)
h = 31 * h + val[i];
return h;
}


Voici deux exemples de ce que me renvoie ce code pour deux entrées :
short_string => 3010251491749729588
rather_longer_longer_string => -3822599824667020448

En cherchant sur le Web, j'ai trouvé une piste (http://poeticcode.wordpress.com/2008/03/10/perl-string-hashc(...) ), que j'ai adaptée avec Math::BigInt pour avoir des entiers longs :

use Math::BigInt;
sub hashCode {
my $hash = Math::BigInt->new();
foreach(split //,shift) {
$hash = 31*$hash+ord($_);
}
return $hash->bstr();
}


Ce qui est un début, mais pas le résultat final, loin s'en faut : pour les chaînes de caractères courtes ("short_string" par exemple), tout va bien et j'ai le même résultat en Perl et Java, mais quand la chaîne s'allonge, Perl continue d'incrémenter la valeur de $hash là où Java ne dépasse jamais la longueur max d'un long. Comment dire à Perl de se comporter autrement?

J'ai essayé toutes sortes des trucs tordus et inefficaces, en vain ! Pourtant, j'ai l'impression que c'est pas si compliqué, mais les compétences me manquent... quelqu'un saurait-il m'aider ?

Merci d'avance de votre aide !
  • # pb encodage sur la fonction java

    Posté par . Évalué à 2.

    Je peux me tromper mais je pense que ta fonction java est incorrecte car la taille d'une chaîne n'est pas nécessairement égale à la taille du tableau renvoyé par getBytes() et du coup ta fonction java ne prend en compte qu'une partie de la chaîne initiale.
  • # Commentaire supprimé

    Posté par . Évalué à 4.

    Ce commentaire a été supprimé par l'équipe de modération.

    • [^] # Re: Quel est ton but ?

      Posté par . Évalué à 1.

      Mon but est de reproduire en Perl exactement le même comportement que celui de la méthode Java, pour substituer mon code Perl au code Java existant.
      Le code existant, en l'occurrence, crée des clés numériques à partir d'urls, qui servent de clé primaire dans une BDD ensuite ; j'ai donc besoin de reproduire cette fonction de transformation à l'identique.
      J'avais aussi regardé les modules Digest, mais aucun ne semblait reproduire le comportement du HashCode java que je dois cloner...
  • # Hash ?

    Posté par (page perso) . Évalué à 2.

    Ce qui est un début, mais pas le résultat final, loin s'en faut : pour les chaînes de caractères courtes ("short_string" par exemple), tout va bien et j'ai le même résultat en Perl et Java, mais quand la chaîne s'allonge, Perl continue d'incrémenter la valeur de $hash là où Java ne dépasse jamais la longueur max d'un long. Comment dire à Perl de se comporter autrement?

    Faudrait savoir, tu veux un hash modulo 2^(sizeof long) ou une sorte de polynôme dont les coefficients sont les valeurs des octets de la chaîne ?

    Si c'est le premier, à vue de nez il faudrait ajouter un $hash = $hash % (2 ** 64); à la fin du calcul (à vérifier, je me trompe peut-être de puissance de deux).
    • [^] # Re: Hash ?

      Posté par . Évalué à 2.

      Le problème, c'est que je ne comprends pas comment se comporte Java une fois qu'il atteint la valeur max de son long.
      J'ai fait un test idiot comme ceci :

      public static void testlongHashCode() {
      long h = Long.MAX_VALUE;
      System.out.println( " h vaut : "+h);
      h++ ;
      System.out.println("h vaut : "+h);
      }

      qui me renvoie :
      h vaut : 9223372036854775807
      h vaut : -9223372036854775808
      Ca me laisse penser qu'il passe du MAX au MIN, mais je n'ai pas les compétences pour interpréter ce comportement et le reproduire en Perl.
      • [^] # Re: Hash ?

        Posté par . Évalué à 3.

        Ben suffit de rajouter un test dans la boucle, et retrancher MIN+MAX pour repartir du MIN :


        my $MAX_VALUE = Math::BigInt->new("9223372036854775808");

        foreach(split //,shift) {

        $hash = 31*$hash+ord($_);

        if ($hash >= $MAX_VALUE) {
        $hash = $hash - 2*MAX_VALUE;
        }
        }


        En fait Java doit coder les longs sur 64bits, dont un bit de signe. Quand il dépasse 2^63-1, la retenue tombe sur le bit de signe, et on repart à -2^63. Classique des langages de soit-disant haut niveau, qui devraient être indépendants des détails d'implémentations, mais qui gère mal (cad pas du tout) ce genre de cas...
        • [^] # Re: Hash ?

          Posté par . Évalué à 3.

          Ce n'est pas un détail d'implémentation, mais bien dans la spécification du langage lui-même :

          http://java.sun.com/docs/books/jls/third_edition/html/lexica(...)

          Les long sont des entiers codés sur 64 bits quelle que soit l'architecture.



          Concernant l'overflow :

          http://java.sun.com/docs/books/jls/third_edition/html/conver(...)

          En gros ils ne gardent que les bits de poids faible en cas d'overflow. Je n'ai pas testé sur d'autres archis pour savoir si c'est vraiment portable par contre...
        • [^] # Re: Hash ?

          Posté par . Évalué à 1.

          Ah, ça me plait d'autant plus comme solution que c'est ce que j'avais essayé de mettre en place... mais sans succès.
          Outre le fait qu'avec les objets BigInt, il faut passer par les méthodes ad-hoc pour les opérations arithmétiques ($x->badd($y), $x->bmul($y)...), même en décomposant, je n'y arrive pas.

          Dans la fonction, il y a deux opérations : une multiplication par 31 et une addition.
          Pour la multiplication, j'essaye pourtant de gérer les deux bornes inférieure et supérieure, mais même en la décomposant en une série de 30 additions, et en vérifiant qu'on est bien dans les bornes et en corrigeant par (2*MAX - 1), je ne retrouve pas la sortie attendue, même pour le cas d'une chaîne courte.

          Je me demande sur le fond comment, dans un cas de multiplication, un langage qui code sur 64 bits opère : est-ce qu'il décompose en une série d'additions ou de soustractions (qui devrait être gérable) ou fait-il une seule transformation qui nécessiterait de travailler en Perl non plus avec BigInt mais plutôt au niveau des bits ?
      • [^] # Re: Hash ?

        Posté par (page perso) . Évalué à 2.

        http://fr.wikipedia.org/wiki/Complément_à_deux

        Par contre, je n'avais pas compris que tu *voulais* des clefs négatives... Comme dit plus haut, fais les calculs en précision arbitraire avec Math::BigInt, puis tu te remets à la main dans le domaine -2^63; 2^63-1.
  • # La solution

    Posté par . Évalué à 1.

    Merci à tous pour vos remarques et très bonnes suggestions, qui m'ont permis de trouver une solution ! Ca m'enlève une énorme épine du pied, et comme j'avais séché sur le pb un petit bout de temps, j'en suis tout content.

    Je partage donc cette solution avec vous ; elle reprend les idées de Fred, jigso et TortuXm consistant à ''remettre dans le domaine'' toute addition/soustraction qui sorte du min et du max d'un entier codé sur 64 bits.

    Comme il faut utiliser Math::BigInt, il faut bien prendre soin de passer par les méthodes idoines pour l'arithmétique et les comparaisons de ce type d'objets (cf http://search.cpan.org/~tels/Math-BigInt-1.89/lib/Math/BigIn(...) ), d'où un code un peu verbeux, et pas forcément optimisé, mais la performance est secondaire pour le problème qui m'occupe ici.
    Voici, donc :

    sub hashCode {
     my $hash = Math::BigInt->new();
      my $MAX_VALUE = Math::BigInt->new('9223372036854775808');
      my $MIN_VALUE = Math::BigInt->new('-9223372036854775807');
      foreach(split //,shift) {
       my $tmp = Math::BigInt->new();
       $tmp=$hash->copy();
       for ($i=1 ; $i<=30 ; $i++) {
        $hash->badd($tmp);
        if ($hash->bcmp($MAX_VALUE)>0) {
         $hash->bsub($MAX_VALUE);
         $hash->bsub($MAX_VALUE);
        }
        if ($hash->bcmp($MIN_VALUE)<0) {
         $hash->badd($MAX_VALUE);
         $hash->badd($MAX_VALUE);
        }
       }
       $hash->badd(ord($_));
       if ($hash->bcmp($MAX_VALUE)>0) {
        $hash->bsub($MAX_VALUE);
        $hash->bsub($MAX_VALUE);
       }
      }
      return $hash->bstr();
    }
    • [^] # Re: La solution

      Posté par . Évalué à 1.

      Ou pareil en plus court, parce que quand même, décomposer des multiplications en additions, pour ensuite faire des soustractions, c'est un peu fastidieux...
      J'étais tellement content d'avoir un truc qui marche, que je me suis empressé de le couler dans le marbre !

      sub hashCode {
        my $hash = Math::BigInt->new();
        my $MAX_VALUE = Math::BigInt->new('9223372036854775808');
        my $MIN_VALUE = Math::BigInt->new('-9223372036854775807');

        foreach(split //,shift) {
         $hash->bmul(31);
         $hash->badd(ord($_));
         while ($hash->bcmp($MAX_VALUE)>0) {
          $hash->bsub($MAX_VALUE);
          $hash->bsub($MAX_VALUE);
         }
         while ($hash->bcmp($MIN_VALUE)<0) {
          $hash->badd($MAX_VALUE);
          $hash->badd($MAX_VALUE);
         }

        }
        return $hash->bstr();
      }
      • [^] # Re: La solution

        Posté par . Évalué à 2.

        Tu pouvais aussi arriver au même résultat avec un modulo et une soustraction.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.