HashMap.hash() ils ont pété un plomb ou quoi?

HashMap.hash() ils ont pété un plomb ou quoi? - Java - Programmation

Marsh Posté le 21-02-2003 à 16:13:30    

alors je me casse le cul à faire une bonne fonction de hashage, j'en trouve une optimale pour mes données (c'est à dire dans le cas de mon traitement, j'ai des clefs uniques et d'autres données faciles, donc j'ai presque quelque chose de parfait). je commence mes tests et vlan, y a 30% de collisions alors que j'avais prévu qu'il n'y en aurait presque pas (de l'ordre de 1 pour 1000).  
 
et puis je tombe la dessus
 

Code :
  1. /**
  2.      * Returns a hash value for the specified object.  In addition to  
  3.      * the object's own hashCode, this method applies a "supplemental
  4.      * hash function," which defends against poor quality hash functions.
  5.      * This is critical because HashMap uses power-of two length  
  6.      * hash tables.<p>
  7.      *
  8.      * The shift distances in this function were chosen as the result
  9.      * of an automated search over the entire four-dimensional search space.
  10.      */
  11.     static int hash(Object x) {
  12.         int h = x.hashCode();
  14.         h += ~(h << 9);
  15.         h ^=  (h >>> 14);
  16.         h +=  (h << 4);
  17.         h ^=  (h >>> 10);
  18.         return h;
  19.     }


 
ils sont pas bien ou quoi? ça me fout tout en l'air!

Reply

Marsh Posté le 21-02-2003 à 16:13:30   

Reply

Marsh Posté le 21-02-2003 à 16:31:33    

Normalement, si tu écris bien ton code, tu devrais pouvoir faire en sorte que la fonction standard de hachage ne soit pas appelée. Tu redéfinis le hachage comment ?

Reply

Marsh Posté le 21-02-2003 à 16:45:09    

ben je fais le truc comme il faut en redéfinissant hashCode pour ma class de donénes, mais bon, je vois pas comment passer outre ça
 

Code :
  1. public Object get(Object key) {
  2.         Object k = maskNull(key);
  4.         // la spa mon hash qui est utilisé  
  5.         int hash = hash(k);
  6.         // Grrrrrrrrr
  8.         int i = indexFor(hash, table.length);
  9.         Entry e = table[i];
  10.         while (true) {
  11.             if (e == null)
  12.                 return e;
  13.             if (e.hash == hash && eq(k, e.key))
  14.                 return e.value;
  15.             e = e.next;
  16.         }
  17.     }


Reply

Marsh Posté le 21-02-2003 à 16:53:39    

facile de t'en sortir :
 
Tu étends HashMap et tu surcharges la méthode static hash( je crois qu'on peut) en ca :  
 

Code :
  1. static int hash(Object x) {
  2.        return x.hashCode();
  3. }


 
et voilou !

Reply

Marsh Posté le 21-02-2003 à 16:56:08    

d'ailleurs a y regarder de plus pres, l'implémentation est désastreuse (pas sur le fond sur la forme). les mecs qui ont fait ça devaient pas etre tres sensibles à la réutilisabilité ou payer à la ligne, par ce que plus je lis les sources de l'API, plus je flippe: c'est pas rare de trouver dans un module 4/5 fonctions de 15 lignes ou plus qui dont le code est exactement le meme sauf le return final qui differe. n'importe quoi!

Reply

Marsh Posté le 21-02-2003 à 16:59:44    

exemple en image
 

Code :
  1. Entry getEntry(Object key) {
  2.     Object k = maskNull(key);
  3.     int hash = hash(k);
  4.     int i = indexFor(hash, table.length);
  5.     Entry e = table[i];
  6.     while (e != null && !(e.hash == hash && eq(k, e.key)))
  7.         e = e.next;
  8.     return e;
  9. }
  11. public Object get(Object key) {
  12.     Object k = maskNull(key);
  13.     int hash = hash(k);
  14.     int i = indexFor(hash, table.length);
  15.     Entry e = table[i];
  16.     while (true) {
  17.         if (e == null)
  18.             return e;
  19.         if (e.hash == hash && eq(k, e.key))
  20.             return e.value;
  21.         e = e.next;
  22.     }
  23. }

 
 
les mecs ont meme pas été foutu d'écrire la meme boucle, ils ont voulu se démarquer faut croire. bref l'une fait return e et l'autre return e.value
minable
 
 
ben je vais surcharger, mais je trouve que ça craint

Reply

Marsh Posté le 21-02-2003 à 16:59:55    

là je demande à voir : l'implémentation de ces classes là a du être tunnée à mort !!!

Reply

Marsh Posté le 21-02-2003 à 17:00:44    

benou a écrit :

là je demande à voir : l'implémentation de ces classes là a du être tunnée à mort !!!

à ton aise. t'en veux d'autres?
 
edit: l'implémentation de Stack est très discutable. héritage, :non:, c'est clair que c'etait vraiment trop compliqué de faire un adaptateur. si les mecs avaient pas ecrit 2 fois la meme chose, ils auraient peut etre eu le temps de réfléchir un peu plus.
 
je decrouvre l'API, et beaucoup de choses que j'y vois sont loin de me ravir  :o


Message édité par Taz le 21-02-2003 à 17:13:35
Reply

Marsh Posté le 21-02-2003 à 17:14:00    

Je suis d'accord avec Taz. L'implémentation de plein de classes de base du JDK seraient clairement à revoir. Souvent, il y n'y aurait pas grand chose à changer, mais on y trouve régulièrement des petites horreurs sans aucune justification (du type efficacité). Simplement, personne ne s'en est plaint, alors personne chez Sun ne les a modifiées.

Reply

Marsh Posté le 21-02-2003 à 17:53:56    

++Taz a écrit :

alors je me casse le cul à faire une bonne fonction de hashage, j'en trouve une optimale pour mes données (c'est à dire dans le cas de mon traitement, j'ai des clefs uniques et d'autres données faciles, donc j'ai presque quelque chose de parfait). je commence mes tests et vlan, y a 30% de collisions alors que j'avais prévu qu'il n'y en aurait presque pas (de l'ordre de 1 pour 1000).  
 
et puis je tombe la dessus
 

Code :
  1. /**
  2.      * Returns a hash value for the specified object.  In addition to  
  3.      * the object's own hashCode, this method applies a "supplemental
  4.      * hash function," which defends against poor quality hash functions.
  5.      * This is critical because HashMap uses power-of two length  
  6.      * hash tables.<p>
  7.      *
  8.      * The shift distances in this function were chosen as the result
  9.      * of an automated search over the entire four-dimensional search space.
  10.      */
  11.     static int hash(Object x) {
  12.         int h = x.hashCode();
  14.         h += ~(h << 9);
  15.         h ^=  (h >>> 14);
  16.         h +=  (h << 4);
  17.         h ^=  (h >>> 10);
  18.         return h;
  19.     }


 
ils sont pas bien ou quoi? ça me fout tout en l'air!


Bon alors là j dois avouer mon inculture, mais je comprends rien à cette fonction. En fait je ne suis pas très familire des opérateurs utilisés. Quelqu'un aurit-il la bonté de m'expliquer ce qui se passe ? (genre les opérateurs ~ et >>>, je connaissais pas).

Reply

Marsh Posté le 21-02-2003 à 17:53:56   

Reply

Marsh Posté le 21-02-2003 à 17:58:13    

ce sont des opérations bit à bit
~ complément
>>>, >> et << sont des décalages
& et binaire
| ou binaire
^ ou binaire exclusif
 
à toi de tester

Reply

Marsh Posté le 21-02-2003 à 18:00:00    

A oui le complement, j'y pensais plus. Sinon pour les décalages de bit je connaissais, mais alors quelle est la différence entre >> et >>> ?

Reply

Marsh Posté le 21-02-2003 à 18:05:47    

Remise à zéro des bits qui apparaissent lors du décalage dans un cas, et décalage circulaire dans l'autre cas, si ma mémoire est bonne.

Reply

Marsh Posté le 21-02-2003 à 18:08:26    

Ah ok d'accord. Merci beaucoup :jap:

Reply

Marsh Posté le 21-02-2003 à 18:14:26    

presque
 
>> est un décalage à droite signé qui insère des 0 ou des 1 selon le signe (conservation)
>>> décalage à droite avec entrée de 0 à gauche
<< décalage à gauche avec injection de 0

Reply

Marsh Posté le 21-02-2003 à 18:15:39    

C'est effectivement plus logique que ce que j'ai dit.  :jap:

Reply

Marsh Posté le 21-02-2003 à 18:16:46    

++Taz a écrit :

à ton aise. t'en veux d'autres?
 
edit: l'implémentation de Stack est très discutable. héritage, :non:, c'est clair que c'etait vraiment trop compliqué de faire un adaptateur. si les mecs avaient pas ecrit 2 fois la meme chose, ils auraient peut etre eu le temps de réfléchir un peu plus.


je suis d'accord avec toi. Mais je crois que concernant la stack, ils ont préferrer permettre au développeur d'accéder aux méthodes de Vector avec une stack pour une raison de praticité.
 
Mais je suis d'accord avec toi : ce n'est aps logique que Stack hérite de Vector !
 
 
sinon, concernant la HashMap, je crois pas qu'elle soit le résulta d'un stagiaire qui a écrit ca vite fait un vendredi soir ...
 
Ce genre de classe est utilisée partout => la performance de java est très dépendante de l'implémentation de ces classes.
 
D'ailleurs, les changements d'implémentation de la HashMap (et autre HashTable) ont été revu plusieurs fois au fur et à mesure des versions du JDK

Reply

Marsh Posté le 21-02-2003 à 18:19:05    

ben pour la stack, l'encapsulation est pulvérisée :( . on dit que java est sure, quand je vois comment c'est facile de bousiller une pile  :sweat:

Reply

Marsh Posté le 21-02-2003 à 18:22:06    

c'est un choix bordel ! t'as le droit de pas le partager (comme je le fais) mais juger la "sécurité" de java en fonction de ça c'est carément ridicule !  [:benou]


Message édité par benou le 21-02-2003 à 18:22:21
Reply

Marsh Posté le 21-02-2003 à 18:22:25    

Autre commentaire concernant Stack : elle est synchronisée (puisque Vector l'est), et son équivalent non synchronisé n'existe pas dans le JDK.
Or on a souvent besoin, quand on écrit ses propres classes, d'une pile qui ne soit pas synchronisée, et autant il est facile de rendre synchronisée une collection qui ne l'est pas (avec la méthode statique appropriée de la classe Collections) autant le contraire est, il me semble totalement impossible.
 
Pour HashMap, d'accord et pas d'accord benou. Certes cette classe-là a peut-être être revu par Sun, et, à leur décharge, la plupart des programmeurs ne savent pas écrire une fonction de hachage correcte. L'inconvénient, c'est que du coup, on se retrouve dans le cas de Taz quand on connaît bien ses données à hacher. Quitte à rajouter un tel code dans HashMap, il aurait été préférable de pouvoir le déconnecter simplement, même si par défaut, il est activé.


Message édité par BifaceMcLeOD le 21-02-2003 à 18:23:13
Reply

Marsh Posté le 21-02-2003 à 18:24:34    

et ben j'ai donné la manip pour que ca fonctionne comme il veut !
 
ca prend 5 lignes à écrire à tout casser !!!! :o
 

Reply

Marsh Posté le 21-02-2003 à 18:25:34    

++Taz a écrit :

ben pour la stack, l'encapsulation est pulvérisée :( . on dit que java est sure, quand je vois comment c'est facile de bousiller une pile  :sweat:  


Si tu veux une pile propre, tu te fais une interface nickel, et tu pourras en plus disposer plusieurs implémentations différentes (basée sur un ArrayList, un LinkedList, voire une implémentation plus délire).

Reply

Marsh Posté le 21-02-2003 à 18:27:59    

si vous voulez des infos sur les méandre de l'implémentation et l'optimisation de cette classe, lisez ca : http://www.javaspecialists.co.za/archive/Issue054.html

Reply

Marsh Posté le 21-02-2003 à 18:28:06    

le principale reproche, c'est que je n'ai vu le hashage supplémentaire mentionné nulle part dans la doc.

Reply

Marsh Posté le 21-02-2003 à 18:29:08    

++Taz a écrit :

le principale reproche, c'est que je n'ai vu le hashage supplémentaire mentionné nulle part dans la doc.


ouep ! un point pour toi !

Reply

Marsh Posté le 21-02-2003 à 18:38:54    

benou a écrit :

si vous voulez des infos sur les méandre de l'implémentation et l'optimisation de cette classe, lisez ca : http://www.javaspecialists.co.za/archive/Issue054.html

ça me fais froid dans le dos. justifier l'emploi de  de taille 2**n parce que c'est "plus rapide" de faire un mask qu'un modulo et ainsi introduire des problèmes de collisions et donc devoir rehasher pour pallier à cet effet secondaire, c'est de la science fiction  :heink:  
 
je comprends vraiment rien à la philosphie des programmeurs de l'API

Reply

Marsh Posté le 21-02-2003 à 18:42:53    

je pense qu'ils ont du bencher cette classe et l'optimiser pour le meilleur résultat moyen, en se disant qu'en cas d'extrème importance des perfs, les développeurs ne serait pas à ca près de redévelopper l'algo de répartition.
 
ca se défend !

Reply

Marsh Posté le 21-02-2003 à 18:52:00    

benou a écrit :

facile de t'en sortir :
 
Tu étends HashMap et tu surcharges la méthode static hash( je crois qu'on peut) en ca :  
 

Code :
  1. static int hash(Object x) {
  2.        return x.hashCode();
  3. }


 
et voilou !


 
Je ne crois pas qu'on puisse surcharger une méthode statique ...
http://forum.java.sun.com/thread.j [...] ead=289648

Reply

Marsh Posté le 21-02-2003 à 18:52:52    

le problème: l'utilisateur pas tres averti avec une fonction de hashage moyenne, de toutes façons, ne fera pas un usage tres aggresif, alors les perfs entre un % et un &, c'est surréaliste de considérer ça: certes çette optimsiation est effective, mais n'aura aucun impact sur son applciation. apres, y a le programmeur qui travaille sa fonction de hashage, veut une utilisation mémoire serrée et a besoin de performance: cette optimisation le dessert. apres si on part du principe qu'on est pété de RAM, qu'on aime bien offuscé son code avec des trucs binaires, qu'on a qu'une vague idée de ce qu'est une fonction de hash et qu'on veut un truc qui tourne à fond pour faire celui qui à la plus grosse.
sur ce, ben je vais faire ma hash_map perso

Reply

Marsh Posté le 21-02-2003 à 19:03:47    

ouais, je crois que c'est ce qu'il te reste à faire...
 
si tu veux, prend le source de la HashMap de la jdk 1.3 ;) :D

Reply

Marsh Posté le 21-02-2003 à 19:12:32    

je vais faire ma sauce maison mais je jetterai un oeil, merci  ;)

Reply

Marsh Posté le 22-02-2003 à 00:14:09    

++Taz a écrit :

ben pour la stack, l'encapsulation est pulvérisée :( . on dit que java est sure, quand je vois comment c'est facile de bousiller une pile  :sweat:  


 
Je suis pas sûr que se soit réellement une connerie, j'ai pas encore tout capté, mais Meyer dans Eiffel fait aussi des (certaines) piles accessibles par index.
 
Mais j'ai pas compris en quoi ça ne serait pas crade.
 

Reply

Marsh Posté le 22-02-2003 à 00:21:01    

c'est crade ! ca peut juste être pratique dans certains cas ...

Reply

Marsh Posté le 22-02-2003 à 00:59:32    

nraynaud a écrit :


 
Je suis pas sûr que se soit réellement une connerie, j'ai pas encore tout capté, mais Meyer dans Eiffel fait aussi des (certaines) piles accessibles par index.
 
Mais j'ai pas compris en quoi ça ne serait pas crade.
 
 

ben ça n'a rien à voir avec une pile un vecteur. si on veut un vecteur, on utilise un vecteur et si on veut une pile, on utilise une pile. pourquoi permettre des opérations non-permises? c'est une régression. Utiliser l'héritage à la place de la compisition (ou d'un adaptateur dans le cas d'une pile),c 'est exposé inutilement des détails de l'implémentation. On peut alors corrompre les données de la pile puisque l'acces directe est permis. En plus l'héritage propage tous les problèmes de la super classe alors que la composition permet de les masquer.


Message édité par Taz le 22-02-2003 à 01:10:40
Reply

Marsh Posté le 22-02-2003 à 01:12:58    

benou a écrit :

c'est crade ! ca peut juste être pratique dans certains cas ...

si tu veux utiliser un vecteur comme une pile, tu economiseras ton clacier puisque push est plus long a taper que add. Apres si vous etes pas d'accord sur ce qu'est une pile et que l'encapsulation vous semble etre une barriere injustifiée... j'y peux rien :sweat:  :whistle:

Reply

Marsh Posté le 22-02-2003 à 02:01:07    

C'est expliqué ici:
http://www.javaspecialists.co.za/archive/Issue054.html
 
Apparemment y a eu une grosse baisse de perfs sur la division euclidienne ce qui les a obligé à adopter des puissances de 2 pour le hachage.  
Mais cette puissance de 2 peut s'avérer catastrophique si la fonction de hachage utilisateur est pas mal foutue. Ils utilisent donc une petite bidouille, avec des décalages de bits pour, rédistribuer un peu les valeurs.


Message édité par verdoux le 22-02-2003 à 02:02:26
Reply

Marsh Posté le 22-02-2003 à 21:31:58    

verdoux a écrit :

C'est expliqué ici:
http://www.javaspecialists.co.za/archive/Issue054.html


 
benou a déjà donné ce lien :o


---------------
Just because you feel good does not make you right
Reply

Marsh Posté le 22-02-2003 à 21:44:17    

DarkLord a écrit :


 
benou a déjà donné ce lien :o


J'avais pas vu  :whistle:

Reply

Marsh Posté le 22-02-2003 à 22:08:12    

verdoux a écrit :


J'avais pas vu  :whistle:  


 
;)


---------------
Just because you feel good does not make you right
Reply

Marsh Posté le 22-02-2003 à 22:14:51    

++Taz a écrit :

ben ça n'a rien à voir avec une pile un vecteur. si on veut un vecteur, on utilise un vecteur et si on veut une pile, on utilise une pile. pourquoi permettre des opérations non-permises? c'est une régression. Utiliser l'héritage à la place de la compisition (ou d'un adaptateur dans le cas d'une pile),c 'est exposé inutilement des détails de l'implémentation. On peut alors corrompre les données de la pile puisque l'acces directe est permis. En plus l'héritage propage tous les problèmes de la super classe alors que la composition permet de les masquer.


 
Merci, j'étais au courrant. Je crois que tu as répondu à côté.

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed