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