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 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 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.
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.
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.
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.
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.
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.
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.
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...
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...
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...
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)
On 2013-08-20, Alexandre Bacquart<tek512DELETEME@free.fr> 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)
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)
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é.
Ha bon ? Et si l'encodage des chaînes change ? ASCII, EBCDIC,
UTF-machin, tout ça...
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.
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é.
Ha bon ? Et si l'encodage des chaînes change ? ASCII, EBCDIC,
UTF-machin, tout ça...
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.
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é.
Ha bon ? Et si l'encodage des chaînes change ? ASCII, EBCDIC,
UTF-machin, tout ça...
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.
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)
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)
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)
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.
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.
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.
Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1.
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.
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.
Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1.
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.
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.
Je ne vois pas vraiment comment 421 pourrait être représenté en mémoire
par 420+1 ou 422-1.
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.
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.
Ou fournir une fonction de hash qui ne tient pas compte de ce padding.
Ou fournir une fonction de hash qui ne tient pas compte de ce padding.
Ou fournir une fonction de hash qui ne tient pas compte de ce padding.