Logo GNT
Actualités Tests & Guides Bons Plans
Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11
Entraide Développement Développement Langage C Valeur vs représentation d'un objet

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.
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2 3 4 5
Avatar
Alexandre Bacquart
On 08/20/2013 10:04 PM, candide wrote:
Le 20/08/2013 16:47, Alexandre Bacquart a écrit :

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.



Question d'efficacité et de versatilité.



Mais, surtout, comment peut-on faire autrement (tout en restant
générique) ?



Faire un hash générique se basant sur la représentation des objet en
mémoire via un pointer void* (qui perd toute information sur la nature
de l'objet) est inconcevable.

Je comprend ta douleur, tu dois te dire qu'en Java (ou autres), il y a
un hash qui fonctionne très bien avec tout, mais en C on est pas sur des
machines virtuelles, du coup les représentations internes des objets
dépendent de l'âge du capitaine, si je puis dire.

Ha bon ? Et si l'encodage des chaînes change ? ASCII, EBCDIC,
UTF-machin, tout ça...



Le charset va changer en cours d'exécution du programme ?



Non, mais volontairement c'est possible et il n'est d'ailleurs pas exclu
d'avoir à utiliser plusieurs encodages... plus généralement si tu
travailles avec une bibliothèque qui va te refiler des chaînes en UTF-8
alors que ta représentation interne est UTF-16 (par exemple, et je ne
parle pas d'utiliser plusieurs bibliothèques).

420+1 et 422-1 ne sont pas des entiers, ce sont des expressions (peu
importe que la valeur après évaluation soit la même). Evidemment,
admettant que tu hash ces expressions (quelle que soit la manière dont
tu les représentes) et non pas le résultat de leur évaluation (l'entier
421), tu auras deux hash différents. Rien de plus normal.



Mais naturellement que je ne parle pas des chaînes "420+1" ou "422-1".
Il s'agit bien de hacher les _valeurs_ des expressions 420+1 ou 422-1.



Pardon, mais la manière dont tu l'as initialement présenté ne permet pas
nécessairement d'en conclure que tu parlais de la valeur, justement (et
après tout rien n'exclue non plus de hacher une expression).

Je te rappelle que ta fonction de hash prend un void*. Tu ne peux pas
lui donner directement l'expression 420+1 ou 422-1, tu devras passer par
un int auquel tu auras assigné cette expression. Une fois cela fait, le
int ne contient pas l'expression, mais bel et bien son évaluation.

Donc permet-moi de m'interroger sur le sens de ta question. On parle
bien de C ici, et en C les expressions 420+1 et 422-1 ont le même
résultat (l'entier 421), bien plus sûrement que des chaînes qui
dépendent de l'encodage pour lesquelles tu pensais ne pas avoir de problème.


--
Alexandre
Avatar
Marc Boyer
Le 20-08-2013, candide a écrit :
Par contre, on pourrait avoir des bits "inutilisés", ie sizeof(short)=4,
CHAR_BITS=8, et seulement 16 bits utilisés pour code la valeur, et 16 bits
inutilisés. Dans ce cas, la fonction de hash en effet pourrait renvoyer
des valeurs différentes.



Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas
de page de la Norme :

-------------------------------------------------------------------------
It is possible for objects x and y with the same effective type T to
have the same value when they are accessed as objects of type T, but to
have different values in other contexts. In particular, if == is defined
for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0.
-------------------------------------------------------------------------



Oui. Le cas doit être extrèmement rare avec des entiers, plus commun
avec les flottants.

Mais ce sont surtout les structures qui sont le cas courant, puisqu'on
peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.

Ceci dit, dans le code que tu présentes, la fonction hashmapCreate
prend en paramètre une fonction de hash et une fonction d'égalité. C'est
à l'utilisateur de passer en paramètre les fonctions adéquates.



Certes mais je ne vois pas en quoi ça change le problème.



Ca change le problème dans le sens où cette interface dit explictement
à l'utilisateur que c'est à lui de donner les fonctions de hash et
de comparaison des clés.

La fonction que tu citais en exemple dans le post initial ne fonctionne
en effet que pour des types vérifiant "égalité logique => égalité binaire".

Elle est présente dans la lib, mais personne n'est obligé de l'utiliser.
Après, je n'ais pas vu (pas beaucoup cherché non plus) la doc de cette
lib qui expliquerait ce qu'y fait cete fonction de hash.

J'imagine que
la fonction de comparaison de clés permet, par exemple si la clé est une
structure (ou un tableau), de comparer les membres.



C'est laissé à l'utilisateur dans le cas de cette lib visiblement.

Mais en effet, si l'utilisateur ne connait pas bien la représentation
mémoire de ses données, il risque de se planter. Mais c'est assez
difficile de programmer en C sans connaitre la représentation
mémoire des données.



Les tables de hachage sont une des fonctionnalités qui fait le plus
défaut à la lib standard du C, c'est presque un motif de divorce que de
ne pas en disposer !



Le C est un compromis en plusieurs objectifs. A titre personnel,
je ne suis pas marié au C. Je l'utilise parfois, quand je considère que
c'est la moins pire solution.

Quand à faire une liste des manques criants de la libc, je pense que
c'est un long débat.

Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
Avatar
candide
Faire un hash générique se basant sur la représentation des objet en
mémoire via un pointer void* (qui perd toute information sur la nature
de l'objet) est inconcevable.





C'est justement ma question ! J'ai donné un exemple de source (Android)
et en voici d'autres :

http://gcc.gnu.org/svn/gcc/trunk/libiberty/hashtab.c
http://troydhanson.github.io/uthash/
http://inn.eyrie.org/svn/trunk/lib/hashtab.c


La glib a bien des tables de hachage mais pas génériques, les fonctions
de hash dépendent de la nature de l'objet.


Faut-il passer au C++ pour disposer d'une table de hachage générique
insoupçonnable ?



Ha bon ? Et si l'encodage des chaînes change ? ASCII, EBCDIC,
UTF-machin, tout ça...



Le charset va changer en cours d'exécution du programme ?



Non, mais volontairement c'est possible



?


et il n'est d'ailleurs pas exclu
d'avoir à utiliser plusieurs encodages... plus généralement si tu
travailles avec une bibliothèque qui va te refiler des chaînes en UTF-8
alors que ta représentation interne est UTF-16 (par exemple, et je ne
parle pas d'utiliser plusieurs bibliothèques).



Ce n'est pas le problème. Si au départ (état A) je place "toto" comme
clé dans ma table de hachage (clé associée à une valeur, par exemple
2013) et que plus tard (état B) je cherche à nouveau "toto" dans ma
table de hachage pour récupérer 2013, la 2ème clé ("toto") sera
obligatoirement égale à la clé de l'état A (par définition d'une chaîne
et de l'égalité de deux chaînes) donc toute fonction de hachage, comme
celle que j'ai donnée dans mon exemple initial, se basant uniquement sur
la _valeur_ arithmétique de l'octet (et pas sa représentation interne)
sera valide. Par contre, si la fonction de hachage utilisait la
représentation interne d'un caractère en faisant par exemple des
décalages, je ne suis pas certain que la fonction serait encore valide
(des clé identiques pourraient avoir des hash différents) sauf peut
être si les caractères sont non signés car alors tous les bits sont des
bits de valeur.
Avatar
Marc Boyer
Le 21-08-2013, candide a écrit :

> Faire un hash générique se basant sur la représentation des objet en
> mémoire via un pointer void* (qui perd toute information sur la nature
> de l'objet) est inconcevable.

C'est justement ma question ! J'ai donné un exemple de source (Android)
et en voici d'autres :

http://gcc.gnu.org/svn/gcc/trunk/libiberty/hashtab.c



Dans celle là, j'ai bien trouvé une fonction de hash sur les chaines
de caractères, mais c'est tout. Sinon, c'est à l'utilisateur de
fournir la fonction de hashage associé à un type.

http://troydhanson.github.io/uthash/
http://inn.eyrie.org/svn/trunk/lib/hashtab.c

La glib a bien des tables de hachage mais pas génériques, les fonctions
de hash dépendent de la nature de l'objet.



De quoi parles-tu ? J'ai trouvé hsearch et ses copines, qui fonctionne
juste pour des zero-terminated strings.

Faut-il passer au C++ pour disposer d'une table de hachage générique
insoupçonnable ?



Qu'appelles-tu "insoupçonnable" ? Comme tous les conteneurs C++,
ça t'empèchera de faire une erreur (indétectable avec le void*
en usage en C).

Ensuite, ça te donne des fonctions de hash par défaut pour les
chaines de caractères et les "build-in integral type" (les entiers
pour faire simple). Mais pour les flottants et les structures,
c'est à l'utilisateur de fournir la fonction de hash.

Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
Avatar
Jean-Marc Bourguet
candide writes:

les fonctions de hash dépendent de la nature de l'objet.



C'est a ma connaissance le cas partout. C'est le cas en C++, c'est le
cas en Java, c'est le cas en Ada. Il peut t'etre fournis des fonctions
qui traitent une serie plus ou moins grande de cas particulier, tu peux
en avoir une par defaut qui utilise les capacites d'introspection du
langage pour fonctionner mieux dans plus de cas qu'en C, tu peux en
avoir une generee automatiquement qui va fonctionner sous certaines
hypotheses, mais par nature une fonction de hachage va dependre de la
notion d'egalite desiree et il te faudra pouvoir specifier cette notion
d'une maniere ou d'une autre (tu peux disposer d'annotations utilisees
par la fonction introspective ou par le generateur pour traiter de cas
simples comme simplement ignorer un champs).

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Avatar
candide
Le 21/08/2013 09:50, Marc Boyer a écrit :

Ceci dit, dans le code que tu présentes, la fonction hashmapCreate
prend en paramètre une fonction de hash et une fonction d'égalité. C'est
à l'utilisateur de passer en paramètre les fonctions adéquates.



Certes mais je ne vois pas en quoi ça change le problème.



Ca change le problème dans le sens où cette interface dit explictement
à l'utilisateur que c'est à lui de donner les fonctions de hash et
de comparaison des clés.




Ah oui tu as raison, je n'avais pas réalisé que la fonction de hachage
générique hashmapHash n'est jamais utilisée dans le code (mais alors
pourquoi l'ont-il placé là ?)




La fonction que tu citais en exemple dans le post initial ne fonctionne
en effet que pour des types vérifiant "égalité logique => égalité binaire".




Ça commence à se clarifier. Merci beaucoup de tes explications.
Avatar
candide
Le 21/08/2013 15:00, Marc Boyer a écrit :

Dans celle là, j'ai bien trouvé une fonction de hash sur les chaines
de caractères, mais c'est tout.




Moi je parle de htab_hash_string (const PTR p) ? Le commentaire dit :


Hash P _as_ a null-terminated string

(soulignement de moi) et PTR est une macro pour void *, donc il s'agit
d'une fonction de hachage générique. Idem pour iterative_hash. Mais
effectivement ces fonctions ne sont pas utilisées dans l'implémentation
de leur table de hachage.



La glib a bien des tables de hachage mais pas génériques, les fonctions
de hash dépendent de la nature de l'objet.



De quoi parles-tu ? J'ai trouvé hsearch et ses copines, qui fonctionne
juste pour des zero-terminated strings.



https://developer.gnome.org/glib/2.30/glib-Hash-Tables.html#GHashFunc

dit :

The functions g_direct_hash(), g_int_hash() and g_str_hash() provide
hash functions which can be used when the key is a gpointer, gint, and
gchar* respectively.





Faut-il passer au C++ pour disposer d'une table de hachage générique
insoupçonnable ?



Qu'appelles-tu "insoupçonnable" ? Comme tous les conteneurs C++,
ça t'empèchera de faire une erreur (indétectable avec le void*
en usage en C).

Ensuite, ça te donne des fonctions de hash par défaut pour les
chaines de caractères et les "build-in integral type" (les entiers
pour faire simple). > Mais pour les flottants et les structures,
c'est à l'utilisateur de fournir la fonction de hash.




Je ne savais pas, je pensais que la fonction de hachage était
transparente pour l'utilisateur (comme en Python).
Avatar
candide
Le 21/08/2013 15:41, Jean-Marc Bourguet a écrit :
candide writes:

les fonctions de hash dépendent de la nature de l'objet.



C'est a ma connaissance le cas partout. C'est le cas en C++, c'est le
cas en Java, c'est le cas en Ada. Il peut t'etre fournis des fonctions
qui traitent une serie plus ou moins grande de cas particulier,




Donc comme int ou char*.


tu peux
en avoir une par defaut qui utilise les capacites d'introspection du
langage pour fonctionner mieux dans plus de cas qu'en C, tu peux en
avoir une generee automatiquement qui va fonctionner sous certaines
hypotheses, mais par nature une fonction de hachage va dependre de la
notion d'egalite desiree et il te faudra pouvoir specifier cette notion
d'une maniere ou d'une autre (tu peux disposer d'annotations utilisees
par la fonction introspective ou par le generateur pour traiter de cas
simples comme simplement ignorer un champs).




OK, je commence à y voir plus clair, merci de tes explications.



Donc, pour résumer, si je fais une table de hachage "relativement"
générique en C, j'écris des fonctions de hachage pour les types de base
qui m'intéressent, disons les entiers et les strings ; pour des
conteneurs comme des tableaux ou des structures, j'écris des fonctions
de hachage ad hoc qui vont dépendre des fonctions de hachage pour les
types élémentaires entier ou string présents dans le conteneur. Et pour
écrire une fonction de hachage pour des entiers, je ne le découpe pas en
octets mais j'utilise la valeur de l'entier. C'est à peu près ça ?
Avatar
Benoit Izac
Bonjour,

le 21/08/2013 à 09:50, Marc Boyer a écrit dans le message
<kv1rgd$kjm$ :

Oui, c'est exactement mon souci. Ce qui me gêne, c'est cette note de bas
de page de la Norme :

-------------------------------------------------------------------------
It is possible for objects x and y with the same effective type T to
have the same value when they are accessed as objects of type T, but to
have different values in other contexts. In particular, if == is defined
for type T, then x == y does not imply that memcmp(&x, &y, sizeof (T)) == 0.
-------------------------------------------------------------------------



Oui. Le cas doit être extrèmement rare avec des entiers, plus commun
avec les flottants.

Mais ce sont surtout les structures qui sont le cas courant, puisqu'on
peut faire x= y et avoir ensuite memcmp(&x, &y, sizeof (T)) != 0.



Il y a un quelque chose qui m'échappe : memcmp() compare après avoir
converti en unsigned char, comment est-ce possible que ça diffère sur des
int ou float (pour une structure, je comprends bien qu'il peut y avoir
du padding) ?

--
Benoit Izac
Avatar
Alexandre Bacquart
On 08/21/2013 11:46 AM, candide wrote:

> Faire un hash générique se basant sur la représentation des objet en
> mémoire via un pointer void* (qui perd toute information sur la nature
> de l'objet) est inconcevable.



C'est justement ma question ! J'ai donné un exemple de source (Android)
et en voici d'autres :

http://gcc.gnu.org/svn/gcc/trunk/libiberty/hashtab.c
http://troydhanson.github.io/uthash/
http://inn.eyrie.org/svn/trunk/lib/hashtab.c


La glib a bien des tables de hachage mais pas génériques, les fonctions
de hash dépendent de la nature de l'objet.


Faut-il passer au C++ pour disposer d'une table de hachage générique
insoupçonnable ?



<HS>

En C++, le problème persiste en ce qui concerne la représentation des
objets en mémoire qui dépend toujours de l'implémentation (ie. pas de
machine virtuelle). Cependant on s'en sortira bien plus sûrement en
faisant usage des template (programmation générique) et de la
spécialisation.

On trouvera std::hash (C++11, mais pas requis) ou std::tr1::hash, ou
encore boost::hash. Tous sont déjà spécialisés pour les types
fondamentaux (int, short, ...) et les différents types de chaînes
(std::string...), donc oui, tu peux en principe y placer toute ta
confiance. Et au pire, tu peux spécialiser toi-même (de toutes façons,
il faudra bien si tu veux hacher tes propres structures/classes), mais
rien d'insurmontable là-dedans.

Quoiqu'il en soit, tu n'auras jamais le truc enfantin de Java
(Object.hashCode()) qui marche partout sans un minimum d'effort (sauf
pour les types fondamentaux pour lesquels il faut passer par l'objet
éponyme). Je ne connais pas les détails d'implémentation, mais étant
donné que Java tourne sur une machine virtuelle, une méthode générique
basée sur la représentation interne des objets ne me semble pas poser de
problème particulier pour être insoupçonnable.

</HS>

>
>>> Ha bon ? Et si l'encodage des chaînes change ? ASCII, EBCDIC,
>>> UTF-machin, tout ça...
>>
>> Le charset va changer en cours d'exécution du programme ?
>
> Non, mais volontairement c'est possible

?



char* setlocale(int category, const char* locale);

> et il n'est d'ailleurs pas exclu
> d'avoir à utiliser plusieurs encodages... plus généralement si tu
> travailles avec une bibliothèque qui va te refiler des chaînes en UTF-8
> alors que ta représentation interne est UTF-16 (par exemple, et je ne
> parle pas d'utiliser plusieurs bibliothèques).

Ce n'est pas le problème. Si au départ (état A) je place "toto" comme
clé dans ma table de hachage (clé associée à une valeur, par exemple
2013) et que plus tard (état B) je cherche à nouveau "toto" dans ma
table de hachage pour récupérer 2013, la 2ème clé ("toto") sera
obligatoirement égale à la clé de l'état A (par définition d'une chaîne
et de l'égalité de deux chaînes) donc toute fonction de hachage, comme
celle que j'ai donnée dans mon exemple initial, se basant uniquement sur
la _valeur_ arithmétique de l'octet (et pas sa représentation interne)
sera valide. Par contre, si la fonction de hachage utilisait la
représentation interne d'un caractère en faisant par exemple des
décalages, je ne suis pas certain que la fonction serait encore valide
(des clé identiques pourraient avoir des hash différents) sauf peut être
si les caractères sont non signés car alors tous les bits sont des bits
de valeur.



Il peut y avoir un problème uniquement pour un décalage à droite (>>)
des valeurs négatives. La norme dit "implementation-defined" (6.5.7),
mais de là à interprêter cela comme "toujours le même résultat pour une
implémentation donnée" (remplissage du signe avec 0 ou 1), ce serait
jouer avec le feu et tu fais bien de t'en méfier, même dans le cadre
d'une unique instance du programme. Cela dit, toutes les ALU auxquels
j'ai eu affaire font cela de manière déterministe, et il y a même
souvent deux types de décalage (arithmétique et logique) pour garder le
signe (ou pas). Après, c'est selon l'humeur du compilo on va dire.
Honnêtement, je ne ferais pas de paris là-dessus, et je n'ai pas non
plus la prétention de connaître toutes les ALU (pas sûr qu'il y en ait
qui font cela de manière non déterministe).

Sinon, je comprend mieux ton propos maintenant et en effet, du moment
que tu n'utilises le hachage (arithmétique) qu'avec des chaînes que tu
as créé toi-même et sans jamais changer de locale, je ne vois pas trop
où un problème pourrait survenir.


--
Alexandre
1 2 3 4 5