Valeur vs représentation d'un objet

Marc Boyer

20/08/2013 à 16:44

Le 18-08-2013, candide a écrit :

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.

Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1. Il n'existe que deux encodages possibles en C,
et Android se limite peut être au plus classique (complément à deux).

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. Mais bon, s'il est théoriquement possible
de le faire, c'est rare, et peut-être exclu par d'autres hypothèses
parties du code.

En flottant aussi, on doit avoir un +0.0 et -0.0 je crois (mais je
suis suis pas très compétent sur les flotants).

Le vrai souci à mon sens, ce sont les structures. Là, les bits inutilisés
sont monnaie courante.

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.

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.

Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet

Le 18-08-2013, candide <candide@free.invalid> a écrit :

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.

Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1. Il n'existe que deux encodages possibles en C,
et Android se limite peut être au plus classique (complément à deux).

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. Mais bon, s'il est théoriquement possible
de le faire, c'est rare, et peut-être exclu par d'autres hypothèses
parties du code.

En flottant aussi, on doit avoir un +0.0 et -0.0 je crois (mais je
suis suis pas très compétent sur les flotants).

Le vrai souci à mon sens, ce sont les structures. Là, les bits inutilisés
sont monnaie courante.

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.

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.

Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet

Vous avez filtré cet utilisateur ! Consultez son message

Le 18-08-2013, candide a écrit :

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.

Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1. Il n'existe que deux encodages possibles en C,
et Android se limite peut être au plus classique (complément à deux).

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. Mais bon, s'il est théoriquement possible
de le faire, c'est rare, et peut-être exclu par d'autres hypothèses
parties du code.

En flottant aussi, on doit avoir un +0.0 et -0.0 je crois (mais je
suis suis pas très compétent sur les flotants).

Le vrai souci à mon sens, ce sont les structures. Là, les bits inutilisés
sont monnaie courante.

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.

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.

Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet

Alexandre Bacquart

20/08/2013 à 16:47

On 08/18/2013 12:05 PM, candide wrote:

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.

Question d'efficacité et de versatilité.

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.

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

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.

Il faut interprêter ceci en comparant les représentations sur des
environnements différents. Autrement dit, pas sur la même
machine/système/compilateur/configuration car le moindre changement peut
faire que la représentation sera différente, et donc le résultat du hash.

Plus généralement, j'utilise une fonction de hash sans me soucier des
représentations uniquement dans le contexte d'une instance du programme
(calculs au lancement et utilisation ensuite). S'il faut stocker pour
une utilisation par d'autres instances, alors la question de la
représentation doit toujours être considérée.

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.

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.

Il faut donc hasher le résultat de l'expression (supposant que c'est
vraiment ton critère de comparaison). Ceci dit, même pour les entiers la
représentation peut être différente simplement parce-que tu as changé
d'architecture. Mais de par leur nature de types fondamentaux, un
changement d'OS ou de compilateur ne devrait en principe pas poser de
problème.

On pourraît en discuter pendant des heures (thread potentiellement
interminable), mais pour résumer, je dirais que l'utilisation d'une
fonction de hash, aussi magique que cela puisse paraître, est soumise à
certaines restrictions et que tu en soulèves une fondamentale : la
représentation des valeurs en mémoire. Du moment qu'elle est la même
partout, aucun problème.

Une règle que j'applique généralement pour ces dépendances :

entier/flottant : architecture
chaîne : encodage
structure : compilateur (y compris sa version et les paramètres
qu'on lui donne), mais ce n'est que le plus petit
dénominateur commun, en supposant que la structure ne
contient pas de pointeurs auquel cas ils changeront même
avec l'instance du programme. C'est toujours très délicat
les structures...

Je te laisse méditer sur l'utilisation des hash avec des bases de
données ou autres phénomènes nécessitant une certaine
interopérabilité... généralement, cela se résume à ne pas tenter de
réinventer la roue et à utiliser, autant que faire se peut, les
mécanismes offerts par la BDD.

--
Alexandre

On 08/18/2013 12:05 PM, candide wrote:

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.

Question d'efficacité et de versatilité.

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.

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

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.

Il faut interprêter ceci en comparant les représentations sur des
environnements différents. Autrement dit, pas sur la même
machine/système/compilateur/configuration car le moindre changement peut
faire que la représentation sera différente, et donc le résultat du hash.

Plus généralement, j'utilise une fonction de hash sans me soucier des
représentations uniquement dans le contexte d'une instance du programme
(calculs au lancement et utilisation ensuite). S'il faut stocker pour
une utilisation par d'autres instances, alors la question de la
représentation doit toujours être considérée.

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.

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.

Il faut donc hasher le résultat de l'expression (supposant que c'est
vraiment ton critère de comparaison). Ceci dit, même pour les entiers la
représentation peut être différente simplement parce-que tu as changé
d'architecture. Mais de par leur nature de types fondamentaux, un
changement d'OS ou de compilateur ne devrait en principe pas poser de
problème.

On pourraît en discuter pendant des heures (thread potentiellement
interminable), mais pour résumer, je dirais que l'utilisation d'une
fonction de hash, aussi magique que cela puisse paraître, est soumise à
certaines restrictions et que tu en soulèves une fondamentale : la
représentation des valeurs en mémoire. Du moment qu'elle est la même
partout, aucun problème.

Une règle que j'applique généralement pour ces dépendances :

entier/flottant : architecture
chaîne : encodage
structure : compilateur (y compris sa version et les paramètres
qu'on lui donne), mais ce n'est que le plus petit
dénominateur commun, en supposant que la structure ne
contient pas de pointeurs auquel cas ils changeront même
avec l'instance du programme. C'est toujours très délicat
les structures...

Je te laisse méditer sur l'utilisation des hash avec des bases de
données ou autres phénomènes nécessitant une certaine
interopérabilité... généralement, cela se résume à ne pas tenter de
réinventer la roue et à utiliser, autant que faire se peut, les
mécanismes offerts par la BDD.

--
Alexandre

Vous avez filtré cet utilisateur ! Consultez son message

On 08/18/2013 12:05 PM, candide wrote:

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.

Question d'efficacité et de versatilité.

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.

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

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.

Il faut interprêter ceci en comparant les représentations sur des
environnements différents. Autrement dit, pas sur la même
machine/système/compilateur/configuration car le moindre changement peut
faire que la représentation sera différente, et donc le résultat du hash.

Plus généralement, j'utilise une fonction de hash sans me soucier des
représentations uniquement dans le contexte d'une instance du programme
(calculs au lancement et utilisation ensuite). S'il faut stocker pour
une utilisation par d'autres instances, alors la question de la
représentation doit toujours être considérée.

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.

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.

Il faut donc hasher le résultat de l'expression (supposant que c'est
vraiment ton critère de comparaison). Ceci dit, même pour les entiers la
représentation peut être différente simplement parce-que tu as changé
d'architecture. Mais de par leur nature de types fondamentaux, un
changement d'OS ou de compilateur ne devrait en principe pas poser de
problème.

On pourraît en discuter pendant des heures (thread potentiellement
interminable), mais pour résumer, je dirais que l'utilisation d'une
fonction de hash, aussi magique que cela puisse paraître, est soumise à
certaines restrictions et que tu en soulèves une fondamentale : la
représentation des valeurs en mémoire. Du moment qu'elle est la même
partout, aucun problème.

Une règle que j'applique généralement pour ces dépendances :

entier/flottant : architecture
chaîne : encodage
structure : compilateur (y compris sa version et les paramètres
qu'on lui donne), mais ce n'est que le plus petit
dénominateur commun, en supposant que la structure ne
contient pas de pointeurs auquel cas ils changeront même
avec l'instance du programme. C'est toujours très délicat
les structures...

Je te laisse méditer sur l'utilisation des hash avec des bases de
données ou autres phénomènes nécessitant une certaine
interopérabilité... généralement, cela se résume à ne pas tenter de
réinventer la roue et à utiliser, autant que faire se peut, les
mécanismes offerts par la BDD.

--
Alexandre

Alexandre Bacquart

20/08/2013 à 16:56

On 08/20/2013 04:47 PM, Alexandre Bacquart wrote:

On 08/18/2013 12:05 PM, candide wrote:
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.

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.

Juste pour préciser mon propos : si tu utilises cette expression telle
quelle dans le code C, c'est son résultat qui sera utilisé,
bien-entendu. Un compilateur sain de corps et d'esprit fera toujours que
c'est la valeur 421 qui sera placée dans le code objet.

--
Alexandre

Tonton Th

20/08/2013 à 20:06

On 2013-08-20, Alexandre Bacquart wrote:

structure : compilateur (y compris sa version et les paramètres
qu'on lui donne), mais ce n'est que le plus petit
dénominateur commun, en supposant que la structure ne
contient pas de pointeurs auquel cas ils changeront même
avec l'instance du programme. C'est toujours très délicat
les structures...

Pour les structures, il ne faut surtout pas oublier les
éventuels octets de remplissage dont les valeurs sont
totalement imprévisibles (voir le théorème de Murphy)

--
http://weblog.mixart-myrys.org/?post/2013/07/Saucisse-de-geek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Alexandre Bacquart

20/08/2013 à 20:17

On 08/20/2013 08:06 PM, Tonton Th wrote:

On 2013-08-20, Alexandre Bacquart wrote:

structure : compilateur (y compris sa version et les paramètres
qu'on lui donne), mais ce n'est que le plus petit
dénominateur commun, en supposant que la structure ne
contient pas de pointeurs auquel cas ils changeront même
avec l'instance du programme. C'est toujours très délicat
les structures...

Pour les structures, il ne faut surtout pas oublier les
éventuels octets de remplissage dont les valeurs sont
totalement imprévisibles (voir le théorème de Murphy)

Tout à fait. Et d'ailleurs, cela fait même que créer 2 structures
identiques (sans copie de mémoire avec memcpy() par exemple) fera que
leur représentation en mémoire ne sera pas nécessairement la même, bien
qu'elle soient identiques et que les différences de représentation
concernent des blocs inutilisés. De toutes façons, hacher une structure
est rarement une bonne idée... c'est dans le même ordre d'idée que de
les sauvegarder sur un support physique : il vaut mieux traiter chaque
élément indépendament (et on a plus de chances de détecter les éventuels
problèmes liés au padding et aux pointeurs pendant l'écriture du code).

--
Alexandre

candide

20/08/2013 à 22:04

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

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 ?

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.

candide

20/08/2013 à 22:08

Le 20/08/2013 20:06, Tonton Th a écrit :

Pour les structures, il ne faut surtout pas oublier les
éventuels octets de remplissage dont les valeurs sont
totalement imprévisibles (voir le théorème de Murphy)

La parade classique étant alors de zéroïfier la structure via memset.
Mais d'après certains sur clc, cela ne garantit pas de la
non-réapparition de bits de padding aléatoires lors de l'affectation
ultérieure d'un membre de la structure. Donc hacher des structures de
façon standard semble être assez acrobatique : après chaque affectation
de membre, il faudrait zéroïfier entre les différents membres de la
dite-structure.

Erwan David

20/08/2013 à 22:10

candide écrivait :

Le 20/08/2013 20:06, Tonton Th a écrit :

Pour les structures, il ne faut surtout pas oublier les
éventuels octets de remplissage dont les valeurs sont
totalement imprévisibles (voir le théorème de Murphy)

La parade classique étant alors de zéroïfier la structure via
memset. Mais d'après certains sur clc, cela ne garantit pas de la
non-réapparition de bits de padding aléatoires lors de l'affectation
ultérieure d'un membre de la structure. Donc hacher des structures de
façon standard semble être assez acrobatique : après chaque
affectation de membre, il faudrait zéroïfier entre les différents
membres de la dite-structure.

Ou fournir une fonction de hash qui ne tient pas compte de ce padding.

--
Les simplifications c'est trop compliqué

candide

20/08/2013 à 22:24

Le 20/08/2013 16:44, Marc Boyer a écrit :

Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1.

Visiblement, je n'ai pas été clair sur ce point mais la suite me montre
que tu vois où je veux en venir.

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

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

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 !

candide

21/08/2013 à 01:20

Le 20/08/2013 22:10, Erwan David a écrit :

Ou fournir une fonction de hash qui ne tient pas compte de ce padding.

En effet, c'est bien plus simple ainsi, merci de la remarque.

Valeur vs représentation d'un objet

10 réponses

Veuillez sélectionner un problème