Hash fonction technique "case vide à droite"
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:
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:
http://img862.imageshack.us/img862/9056/sanstitrees.jpg
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
