Trouver une bonne formule de HashCode

Recherche :

Dernière réponse

Sujet : Trouver une bonne formule de HashCode

darklord

matafan a écrit a écrit :

Et qu'est-ce qui l'empêche de regarder comment la méthode hashCode() est implémenté au niveau d'un String ? J'imagine que c'est ce que DarkLord voulait dire : regarder le source de String par exemple. En regardant en plus celui de HashMap par exemple, on peut sûrement en tirer des choses.

Matafan, merci de rectifier mon post qui était assez vague. Mes excuses. Et oui c'est bien cela que j'ai voulu dire.

A+

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

darklord

Matafan, merci de rectifier mon post qui était assez vague. Mes excuses. Et oui c'est bien cela que j'ai voulu dire.

A+

gilou

Si tu connais a l'avance la liste de tes cles, tu peux essayer d'utiliser gperf: http://www.delorie.com/gnu/docs/cperf/gperf_3.html

sinon, une fonction de hash assez courante est la suivante:

Code :

/*
** Hashes a string to produce an unsigned short, which should be
** sufficient for most purposes.
*/
static unsigned hash(char *string)
{
unsigned ret_val = 0;
int i;
while (*string)
{
i = *( int *)string;
ret_val ^= i;
ret_val <<= 1;
string ++;
}
return ret_val;
}

A+,

[jfdsdjhfuetppo]--Message édité par gilou--[/jfdsdjhfuetppo]

BENB

benou a écrit a écrit :

c'est quoi l'intérêt du modulo ??? c'est automatiquement fait par les classes HashMap, etc ...
et pkoi ne pas renvoyer directement la cle ??

Je ne connais pas la classe HashMap... cela ne fait pas parti du standard de la STL...

DaWa demande un hash code entre 1 et 1000 donc size permet de borner la valeur de Hash.
dans sont cas on peut lui proposer par exemple
(cle mod 999) +1 (entre 1 et 1000)
Dans le cas ou K est grand un probleme peut se poser de depassement de capacite attention.

benou

BENB a écrit a écrit :

une methode courrante est (K*cle) mod size

c'est quoi l'intérêt du modulo ??? c'est automatiquement fait par les classes HashMap, etc ...
et pkoi ne pas renvoyer directement la cle ??

benou

Verdoux a écrit a écrit :

Ben justement celles statiques ou finales :D

les méthodes statiques c'est surchargeables !

mais bon, ca se voit pas beaucoup et ca sert pas à grand chose ... :)
mais bon, on peut trouver des cas où c'est utile. Je me souviens m'être posé la question un jour ...

matafan

*genre* :D

verdoux

matafan a écrit a écrit :

Sinon quelle méthode (non statique, non finale, évidemment) ne peut pas être surchargée ?

Ben justement celles statiques ou finales :D

matafan

Et qu'est-ce qui l'empêche de regarder comment la méthode hashCode() est implémenté au niveau d'un String ? J'imagine que c'est ce que DarkLord voulait dire : regarder le source de String par exemple. En regardant en plus celui de HashMap par exemple, on peut sûrement en tirer des choses. Je ne vois pas trop ce que le hashcode « au sens de la VM » viens faire là dedans, d'autant que ce qui se passe dans JVM de sun n'est pas vraiment publique...

Sinon quelle méthode (non statique, non finale, évidemment) ne peut pas être surchargée ?

Kahyman

matafan a écrit a écrit :

Faux : Comme n'importe quelle méthode, hashCode() peut être surchargée... Elle l'est dans les objets String par exemple. Deux String identiques (au sens comparaison de chaines de caractères) ont le même hash code, même si ce sont deux objets différents.

Je n'ai JAMAIS dis le contraire (au sujet de la surcharge)... Je lui ai uniquement explique comment le hashcode des objets en java est realise et ceci en reponse au post de DarkLord qui lui proposait d'aller voir la facon dont etait calcule le hashcode en Java (par la VM donc)...

Tu raisonnes en termes de fonctions, d'APIs, alors que je resonne en termes de representation interne...

Deux objets differents ont un hashcode java au (sens de la VM) different et ca ce n'est pas faux. Si tu vas chercher cette information directement dans la representation memoire des objets tu retrouveras bel et bien cet hashcode unique : il est fixe a la creation de l'objet et est definitif, le passage par surcharge de methode implique le recalcul du hashcode et ne modifie en rien la representation memoire de l'objet. Que tu puisse surcharger la methode ne signifie qu'une chose : tu evites la version interne du hashcode pour forcer une autre version, c'est tout.

Je parle bien entendu de VM non speciale : les VM J2ME (p.ex.)virent carrement cette information de la representation memoire pour gagner de la place... (d'ou le recalcul a chaque appel... d'ou l'obligation d'etre leger sur ce point)

Par contre ce qui est vraiment faux c'est de dire que n'importe quelle methode peut etre surchargee...

matafan

Faux : Comme n'importe quelle méthode, hashCode() peut être surchargée... Elle l'est dans les objets String par exemple. Deux String identiques (au sens comparaison de chaines de caractères) ont le même hash code, même si ce sont deux objets différents.

C'est un peu comme equals() : la méthode equals() de Object compare l'adresse en mémoire des objets, mais elle est surchargée dans des objets comme Integer ou String pour implémenter la relation « naturelle ».

[jfdsdjhfuetppo]--Message édité par matafan--[/jfdsdjhfuetppo]

Kahyman

Le hashcode java est unique... deux objets java n'auront jamais le meme hashcode (celui-ci est calcule lors de la creation de l'objet au sein meme de la VM par rapport a sa representation en memoire). Regarde comment c'est fait ne te servira a rien ou presque...

BenB te propose une bonne methode, prends un bouquin d'algorithmique pour plus d'infos.

Petite info supplementaire pour les utilisateurs de Java :

Ah oui voici un petit os sur lequel vous risquez de tomber en cherchant a utiliser le hashcode java a un moment ou un autre : certains hashcodes java generes sont negatifs...

On rigole un bon coup (lachez vous :lol: ), ca arrive tres rarement : lors d'un test realisant la suppression des redondances du constant pool java realise sur la jdk 1.3.1 dans son integralite (il nous fallait un gros test et la jdk s'est donc imposee) c'est arrive 2 a 5 fois parmis tous les objets en memoire... c'est suffisant pour creer un gros bug (crash) si on utilise des classes utilitaires faites maison et optimisees qui classent les objets dans des arrays selon leur hashcode (modifie) :)

Il y a de quoi peter un plomb car c'est le genre d'exception qui fache : "ArrayIndexOutOfBoundsException"... Donc attention :)

Dawa	merci beaucoup :jap:

BENB

Tu auras de toute maniere 90 pourcents de synonymes...

la vrai question est de savoir si toutes tes cles vont etre utilisees, et surtout lesquelles...

par exemple si tes cles vont etre consequtives (1 - 2 - 3 - 4 ...)

il te faut une formule qui separe les nombres consequtifs (modulo par ex) car un arrondi (cle/10) en ferait des synonymes...

une methode courrante est (K*cle) mod size ou k et size sont premier entre eux (K si possible > size) qui separe enormement les elements consecutifs (chaos)... reste a voir si pour toi k!=1 a un interet...

Dawa

huh ?

darklord

regarde comment hashCode() est implémenté en Java.

Dawa

vala je voudrais trouver une bonne formule qui me ferait le - de synonymes possibles, donc on entrerait jusqu'a 1000 clés entre 0 et 9999 pour trouver des adresses de 1 à 1000.

j'avais pensé a prendre celle de mon cours,

adr=(clé%1000)+1

mais alors faut que je prevoie 90% de synonymes [:jofission] µ

qqun aurait une idée pour moa ?