Java

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

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : HashMap.hash() ils ont pété un plomb ou quoi?

Taz

bisounours-codeur

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 :

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

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

Publicité

BifaceMcLeOD

The HighGlandeur

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 ?

Taz

bisounours-codeur

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 :

public Object get(Object key) {
Object k = maskNull(key);
// la spa mon hash qui est utilisé
int hash = hash(k);
// Grrrrrrrrr
int i = indexFor(hash, table.length);
Entry e = table[i];
while (true) {
if (e == null)
return e;
if (e.hash == hash && eq(k, e.key))
return e.value;
e = e.next;
}
}

benou

facile de t'en sortir :

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

Code :

static int hash(Object x) {
return x.hashCode();
}

et voilou !

Taz

bisounours-codeur

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!

Taz

bisounours-codeur

exemple en image

Code :

Entry getEntry(Object key) {
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry e = table[i];
while (e != null && !(e.hash == hash && eq(k, e.key)))
e = e.next;
return e;
}
public Object get(Object key) {
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry e = table[i];
while (true) {
if (e == null)
return e;
if (e.hash == hash && eq(k, e.key))
return e.value;
e = e.next;
}
}

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

benou

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

Taz

bisounours-codeur

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

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

BifaceMcLeOD

The HighGlandeur

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.

R3g

fonctionnaire certifié ITIL

++Taz a écrit :

Code :

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

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).

Publicité

Taz

bisounours-codeur

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

à toi de tester

R3g

fonctionnaire certifié ITIL

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 >>> ?

BifaceMcLeOD

The HighGlandeur

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.

R3g

fonctionnaire certifié ITIL

Ah ok d'accord. Merci beaucoup :jap:

Taz

bisounours-codeur

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

BifaceMcLeOD

The HighGlandeur

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

benou

++Taz a écrit :

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

Taz

bisounours-codeur

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:

benou

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

BifaceMcLeOD

The HighGlandeur

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

benou

et ben j'ai donné la manip pour que ca fonctionne comme il veut !

ca prend 5 lignes à écrire à tout casser !!!!

BifaceMcLeOD

The HighGlandeur

++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).

benou

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

Taz

bisounours-codeur

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

benou

++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 !

Taz

bisounours-codeur

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

benou

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 !

dsls

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 :

static int hash(Object x) {
return x.hashCode();
}

et voilou !

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

Taz

bisounours-codeur

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

benou

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

Taz

bisounours-codeur

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

nraynaud

lol

++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.

benou

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

Taz

bisounours-codeur

nraynaud 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.

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

Taz

bisounours-codeur

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:

verdoux

And I'm still waiting

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

darklord

You're welcome

verdoux a écrit :

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

benou a déjà donné ce lien

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

verdoux

And I'm still waiting

DarkLord a écrit :

benou a déjà donné ce lien

J'avais pas vu :whistle:

darklord

You're welcome

verdoux a écrit :

J'avais pas vu :whistle:

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

nraynaud

lol

++Taz a écrit :

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

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

Java

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

Sujets relatifs
[crypto] En quoi ça consiste exactement la technique du hash ?	Passer des HASH TABLE de scripts CGI en scripts CGI
[Perl] itérer sur les valeurs d'un tableau de hash de hash...	[C] pété de rire et vieux gcc
ahhh, je pete un plomb !!!!! :-(	Applet et HashMap : pb
je pète un plombs avec l'installation de postgreSQL sous winxp	ComboBoxModel + HashMap
[java] design... hashmap à 2 clés !?
Plus de sujets relatifs à : HashMap.hash() ils ont pété un plomb ou quoi?

Page générée en 0.119 secondes