Discussion :

[Zangdaarr]

Bonjour,

Dans le cadre d'un exercice, je dois définir un hash_set contenant des entiers implémenté de deux façons différentes:

- en utilisant des buckets
- en utilisant la technique de la case vide à droite.

Si je comprends bien sur le principe, je ne vois absolument pas comment le réaliser, car j'ai compris que les buckets étaient une mécanique interne.

Voici mon code pour le premier point:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
 
#include <iostream>
#include <ext/hash_set>
 
using namespace __gnu_cxx;
using namespace std;
 
struct egaliteInt
{
    bool operator()(const int x,const int y) const
    {
        return x == y;
    }
 
};
 
struct hashInt
{
    size_t operator()(const int i) const
    {
        return i%11;
    }
};
 
void Cherche(const hash_set<int, hashInt, egaliteInt>& Set,const int &val)
{
    //ITERATEUR
    hash_set<int, hashInt,egaliteInt>::iterator it = Set.find(val);
    cout << val << ": " << (it != Set.end() ? "present" : "n’est pas present") << endl;
};
 
int main()
{
    int tab[11] = {18, 17, -18, 51, 34, 73, 50, 22, 79, 45, 66};
    hash_set<int, hashInt, egaliteInt> Set;
 
 
    for(int i = 0; i<11;i++)
    {
        Set.insert(*(tab+i));
    }
 
    Cherche(Set, 18); // mangue : present
    Cherche(Set, -18); // mangue : present
    Cherche(Set, 50); // pomme : present
    Cherche(Set, 53); // salade : n’est pas present*/
    return 0;
}

La fonction de hash est donc bien h(x) = x%11, 11 étant la taille de la table d'entiers de départ.

La technique de la case vide à droite est décrite de la façon suivante dans mon cours:



Dans ce cas on a une table de 10 entiers et la fonction de hash est h(x) = x%10.

Le premier tableau est la technique des buckets, la seconde de la case vide à droite. Il n'y a rien d'autre dans le cours. Il n'y a rien dans mes livres de c++, il n'y a rien sur google...

Nous n'avons aucun exemple d'implémentation, à vrai dire, le seul exemple du cours utilise la fonction de hash par défaut, et j'ai bien ramé avant d'avoir la signature correcte à utiliser pour ma fonction de hash !

Je vous remercie du coup de main car je suis largué pour le coup

[bertry]

Salut,
Après une recherche rapide sur google, je suis tombé sur ça.Ca ressemble étrangement à ton problème.
Si tu veux de l'aide, ça aide beaucoup de donner tout l'énoncé!!! Par exemple préciser qu'avant l'extrait de cours que tu as donné, il y a :Extrait de Chapitre 9: Fonctions de Hachage 3/3 © Mohamed N. Lokbani v 1.3 Programmation II

Soit l’ensemble des éléments entiers strictement positifs Z = {11, 59, 32, 44, 31, 26, 19} et un tableau de taille 10. Nous allons donc ranger les éléments de Z dans un tableau dont l’index varie entre 0 et 9 (<10).

La fonction de hachage pour l’élément zi de l’ensemble Z est déterminée par :
h(zi) = zi modulo [10].
zi h(zi)
11 1
59 9
32 2
44 4
31 1
26 6
19 9

On constate dans cet exemple une duplication d’indices : 1 pour 11 et 31 ; 9 pour 59 et 19.

Plusieurs solutions sont possibles pour des éléments ayant le même indice :
soit utiliser un des indices libres disponible dans la table moyennant certaines regèles à définir ; sinon utiliser des listes (chaînées) d’objets (buckets) à cet indice.

Dans le cas de l’utilisation de buckets l’algorithme de recherche d’un élément dans la table se résume ainsi :

*****· Obtenir l’index i dans la table
**********¨ Calculer le hash code.
**********¨ Réduire le hash code modulo la taille de la table pour obtenir l’index i.
*****· Itérer dans le bucket à l’adresse i.
*****· Pour chaque élément dans le bucket vérifier s’il est égal à x, l’élément recherché.
*****· Si on trouve un élément égal à x alors x est dans l’ensemble.
*****· Autrement, x n’est pas dans l’ensemble.

Il semble que tout est dit dans l'énnoncé!

-Soit on utilise une listes (chaînées) d’objets (buckets) à chaques indices 'i' du tableau dans lequelle on stock touts les éléments ayant le même indice donné par h(zi) = zi%10 : donc chaque 'case' t[i]' contient une liste des nombres finissant par 'i' dans cet exemple. On a donc un tableau de listes d'entiers.

-Soit on utilise la technique de la première case vide à droite. On a ici un tableau d'entiers.

Il n'y a plus qu'a implémenter...

Attention : tu te plante complètement en disant :

La fonction de hash est donc bien h(x) = x%11, 11 étant la taille de la table d'entiers de départ.

C'est totalement faux!!! ici : h(x) = x%10 ( je ne sais pas d'ou sort ce 11 : la table à une taille de 10 et on y place 7 entiers ) En tout cas tu l'as mis dans ton code ligne 22 :

return i%11;

[Zangdaarr]

Parce que toi et moi ne parlons pas de la même chose,

Les screens que j'ai postés sont extraits du cours que tu viens de citer, et que je suis en train de prendre présentement (quand je dis que je n'ai rien trouvé sur google, c'est donc rien sauf cela ) )

L'exercice, lui, qui est simplement extrait d'un final que tu trouveras sur le même site, stipule d'utiliser h(x)= x%11, la question que je pose c'était comment on implémente cette fonction. En fait je pourrais tout aussi bien utiliser 7,12,25 que cela fonctionnerait pareil, de façon plus ou moins performante.

Je peux même faire x%10000 et tout mettre dans le même bucket au passage. Ça marchera, ça n'a juste aucun intérêt.

Il n'y a plus qu'a implémenter...

Merci pour cette évidence mais c'est précisément ce que je n'arrive pas à faire.

La technique des buckets est visiblement faite "en arrière plan", par le programme. Il suffit de définir h(x) = x%11 et ça marche. Sauf qu'en lisant le cours, l'algo que tu cites je pensais que je devais l'implémenter moi même vois tu, et ce n'est pas le cas.

Pour l'autre, le cours stipule: il faudra utiliser une fonction h adaptée.

C'est tout sauf évident. Et jusqu'à présent même le professeur n'a pas su me répondre.
Donc si tu sais m'aider sur ce Il n'y a plus qu'a implémenter..., c'est vraiment bienvenu.

[JolyLoic]

Ça n'a pas l'air très compliqué... La fonction h sert visiblement à dterminer dans quelle case placer l'élément. Dans le premier cas, elle ne dépend que de l'élément, et il a choisi une fonction hyper simple, le modulo (qui ne serait probablement pas un très bon choix en tant que tel). Dans le second cas, il faut que si l'on tombe sur une case non vide, on prenne la première case vide à droite. Il faut donc que cette fonction h adaptée ait connaissant du tableau de stockage, ou du moins de quelles cases sont pleines et quelles cases sont vides dans le tableau.

On peut donc envisager pour l'insertion une fonction h qui ressemble à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
index = calcul_de_numéro_de_case_par_hash_classique();
tant que (!tableau.est_case_vide(index))
{
    incrémenter_en_bouclant(index)
}
retourner index

[Blustuff]

Je peux même faire x%10000 et tout mettre dans le même bucket au passage.

Si c'est ce que tu veux dire, utiliser 10000 ne mettra pas tout dans le même bucket. Il mettra tous les nombres dont la différence est exactement un multiple de 10 000 : ça ne fait pas tant de nombres que ça dans le même bucket.

Il n'y a pas de difficulté apparente dans le sujet que tu donnes. Si tu ne précises pas ton problème, personne ne pourra t'aider. Note qu'il serait préférable d'aller demander de l'aide auprès de ton enseignant : ce sont des gens qui malgré leur apparence ne sont pas si méchants.

[bertry]

[Zangdaarr]

Si c'est ce que tu veux dire, utiliser 10000 ne mettra pas tout dans le même bucket. Il mettra tous les nombres dont la différence est exactement un multiple de 10 000 : ça ne fait pas tant de nombres que ça dans le même bucket.

Tu as raison, c'est 1 qui mettrait tout dans le même bucket

Il n'y a pas de difficulté apparente dans le sujet que tu donnes. Si tu ne précises pas ton problème, personne ne pourra t'aider. Note qu'il serait préférable d'aller demander de l'aide auprès de ton enseignant : ce sont des gens qui malgré leur apparence ne sont pas si méchants.

Je pense au contraire que c'est assez compliqué, j'ai déjà posé la question et n'ai pas obtenu de réponse. En fait, l'énoncé ne demande pas de coder, il demande de décrire le principe.

Mais moi je suis borné et têtu: je veux comprendre comment coder.

Si tu ne souhaites pas me donner directement le code que je suis absolument incapable d'écrire, dis moi au moins comment accéder au tableau "caché", pour choisir moi même ou y rentrer les valeurs ?

Ça n'a pas l'air très compliqué... La fonction h sert visiblement à dterminer dans quelle case placer l'élément. Dans le premier cas, elle ne dépend que de l'élément, et il a choisi une fonction hyper simple, le modulo (qui ne serait probablement pas un très bon choix en tant que tel). Dans le second cas, il faut que si l'on tombe sur une case non vide, on prenne la première case vide à droite. Il faut donc que cette fonction h adaptée ait connaissant du tableau de stockage, ou du moins de quelles cases sont pleines et quelles cases sont vides dans le tableau.

Il y a un point de détail que tu oublies et qui n'est pas décrit dans la méthode exposée:

- Doit-on attendre d'avoir fait une première passe sur tous les éléments, pour en placer le plus possible à leur place naturelle dans le tableau, puis on remplit les cases vides avec les autres ou,
- Doit-on placer l'élément dans la case vide à droite dès qu'on le rencontre ?

Dans l'image que j'ai fournie plus haut, 32 est à sa place naturelle, et il n'existe aucun autre nombre qui va aller occuper la case 2.
Si je rencontre 31 avant 32, mais après 11, 31 va t'il aller occuper la case 2, forçant 32 à occuper la case 3 ?
Ou bien 31 doit-il attendre patiemment que 32 ai trouvé sa place, pour en déduire que la sienne est 31 ?

Mon prof n'a pas eu de réponse à cette question

[JolyLoic]

L'idée est effectivement de les ajouter au fur et à mesure, tant pis si ça introduit des décalages qui auraient autrement pu être évités. Dans toute table de hash, suivant l'ordre dans lequel on insère les éléments, on aura des résultats différents (dans la solution à base de buckets, en pratique la table se redimensionne quant un facteur de remplissage des buckets devient trop important). Tout ce qui compte réellement, c'est qu'au final, chaque élément soit situé par trop loin de sa position naturelle, afin qu'une recherche puisse être rapide à partir de cette position.

Pour que ça ait une chance de ne pas être trop n'importe quoi, il faut bien sur que le nombre de cases disponibles dans la table soit significativement plus grand que le nombre d'éléments.

[Blustuff]

- Doit-on attendre d'avoir fait une première passe sur tous les éléments, pour en placer le plus possible à leur place naturelle dans le tableau, puis on remplit les cases vides avec les autres ou,
- Doit-on placer l'élément dans la case vide à droite dès qu'on le rencontre ?

La puissance d'une table de hash c'est qu'elle permet de gérer efficacement des données dont tu ne connais pas les clés a priori. Autrement dit, de pouvoir traiter l'ajout de clé les une après les autres sans savoir à l'avance quelles seront les autres clés.

Dans le cas où tu connaîtrais toutes les clés à l'avance, il serait possible d'optimiser ta table en changeant la fonction de hash. Le but serait alors de trouver une fonction h telle qu'il y ait un minimum de collisions. (c'est à dire h(y1) = h(y2)) On peut parfois prendre une fonction de hash parfaite, sans collision.

Or, ce n'est absolument pas la situation décrite par le sujet. Il faut donc que tu sois capable de placer les clés une par une dans la table, sans même connaître les clés suivantes. Tu l'as déjà compris, suivant l'ordre dans lequel on insère les clés, le résultat pourra être plus ou moins optimal. C'est un compromis qu'on accepte parce que souvent, on ne sait pas faire mieux. (on peut faire un peu mieux mais ça devient plus compliqué, c'est peut être dans ton cours)