Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Valeur vs représentation d'un objet

62 réponses
Avatar
candide
Bonjour,

Je suis en train d'examiner le code source de différentes tables de
hachage _génériques_ [ie pouvant hacher n'importe quel type de données
(entiers, structures, etc) et pas seulement des chaînes de caractères].

Je suis surpris que les fonctions de hachage de la clé (qui se présenter
typiquement en void *key) se basent sur la seule représentation de
l'objet à hacher plutôt que sur sa valeur.

Voici un cas typique, cf.
https://github.com/cgjones/android-system-core/blob/master/libcutils/hashmap.c
:


int hashmapHash(void* key, size_t keySize) {
int h = keySize;
char* data = (char*) key;
size_t i;
for (i = 0; i < keySize; i++) {
h = h * 31 + *data;
data++;
}
return h;
}

Si la fonction de hachage ci-dessus est appliquée à une chaîne de
caractères, il me semble qu'elle ne pose aucun problème. En revanche si
la clé est d'un autre type comme int ou même unsigned int, il pourrait
en aller autrement. En effet, la norme du langage C n'assure pas du tout
que deux objets ayant même valeur aient nécessairement même
représentation. Si, par exemple, l'entier disons 421, est susceptible
d'avoir deux représentations différentes (autrement dit memcmp ne
renverrait pas 0) deux clés de même valeur, par exemple, 420+1 et 422-1,
pourraient renvoyer des hash différents : catastrophe.


Merci pour vos réponses.

2 réponses

3 4 5 6 7
Avatar
candide
Le 30/08/2013 18:13, Jean-Marc Bourguet a écrit :


Pire, tu mets une mauvaise valeur et ca crashe.



On peut générer une "trap représentation" ?
Avatar
Antoine Leca
candide écrivit :
Le 30/08/2013 18:13, Jean-Marc Bourguet a écrit :
Pire, tu mets une mauvaise valeur et ca crashe.



On peut générer une "trap représentation" ?



Si tu écris du code avec un comportement indéfini (comme ce serait le
cas ici), la norme ne garantit rien sur le résultat ; donc il est
parfaitement possible que par malchance, pour un compilateur donné et
une machine donné, le résultat soit une telle représentation.

Un certain Murphy a d'ailleurs émis la conjecture selon laquelle, si
c'est effectivement possible, dans le cas qui te préoccupes et si les
conséquences sont graves, alors cela arrivera.


Mais peut-être pourrait-on retourner au sujet de ce sujet de ce forum
plutôt que de faire des élucubrations putatives sur l'indéfini ?


Antoine
3 4 5 6 7