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 ?
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 ?
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 ?
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) ?
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) ?
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) ?
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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à ?)
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à ?)
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à ?)
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) ?
Bonjour,
le 21/08/2013 à 09:50, Marc Boyer a écrit dans le message
<kv1rgd$kjm$1@news.cict.fr> :
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) ?
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) ?
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.
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.
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.
int hashX(X* x){
return hashmapHash( &(x->c) , 1 ) + hashmapHash( &(x->i), sizeof( x->i ) );
}
int hashX(X* x){
return hashmapHash( &(x->c) , 1 ) + hashmapHash( &(x->i), sizeof( x->i ) );
}
int hashX(X* x){
return hashmapHash( &(x->c) , 1 ) + hashmapHash( &(x->i), sizeof( x->i ) );
}
Le 22/08/2013 10:56, Marc Boyer a écrit :int hashX(X* x){
return hashmapHash( &(x->c) , 1 ) + hashmapHash( &(x->i), sizeof( x->i ) );
}
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
Le 22/08/2013 10:56, Marc Boyer a écrit :
int hashX(X* x){
return hashmapHash( &(x->c) , 1 ) + hashmapHash( &(x->i), sizeof( x->i ) );
}
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
Le 22/08/2013 10:56, Marc Boyer a écrit :int hashX(X* x){
return hashmapHash( &(x->c) , 1 ) + hashmapHash( &(x->i), sizeof( x->i ) );
}
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
Le 22-08-2013, candide a écrit :Le 22/08/2013 10:56, Marc Boyer a écrit :int hashX(X* x){
return hashmapHash(&(x->c) , 1 ) + hashmapHash(&(x->i), sizeof( x->i ) );
}
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Oui, tout à fait. Mais lever ce risque compliquerais un peu
le code.Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
C'est je pense assez courant, mais je ne sais pas si c'est une bonne
pratique en fait.Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
La somme des 3 entiers ou la somme des trois fonctions de hashages.
La somme des 3 entiers n'est surement pas une bonne idée: c'est
surement pas bien repartit.
Le 22-08-2013, candide<candide@free.invalid> a écrit :
Le 22/08/2013 10:56, Marc Boyer a écrit :
int hashX(X* x){
return hashmapHash(&(x->c) , 1 ) + hashmapHash(&(x->i), sizeof( x->i ) );
}
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Oui, tout à fait. Mais lever ce risque compliquerais un peu
le code.
Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
C'est je pense assez courant, mais je ne sais pas si c'est une bonne
pratique en fait.
Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
La somme des 3 entiers ou la somme des trois fonctions de hashages.
La somme des 3 entiers n'est surement pas une bonne idée: c'est
surement pas bien repartit.
Le 22-08-2013, candide a écrit :Le 22/08/2013 10:56, Marc Boyer a écrit :int hashX(X* x){
return hashmapHash(&(x->c) , 1 ) + hashmapHash(&(x->i), sizeof( x->i ) );
}
[Je reviens à ma petite obsession, mais nous sommes bien d'accord que
l'usage de hasmapHash pour hacher un int présente un petit risque,
n'est-ce pas ?]
Oui, tout à fait. Mais lever ce risque compliquerais un peu
le code.Juste pour info, c'est une pratique courante que de faire la somme de
hashes pour obtenir un nouveau hash ?
C'est je pense assez courant, mais je ne sais pas si c'est une bonne
pratique en fait.Quelqu'un connaît l'usage pour hacher un point en 3D à coordonnées
entières (tableau de trois int) ? Pareil, on fait la somme ?
La somme des 3 entiers ou la somme des trois fonctions de hashages.
La somme des 3 entiers n'est surement pas une bonne idée: c'est
surement pas bien repartit.