Discussion :

[masoum]

Bonjour à tous,
Voilà pour les besoins d'un TP , j'ai eu a faire une simulation de hachage , c'est un code facile mais je n'arrive pas à comprendre pourquoi à l’exécution mon tableau qui devrait recevoir des entiers (les index d'un tableau en entrée) ne se rempli par au fur et a mesure de la boucle !!!
voilà le code

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
50
51
package TP8;
 
public class HashLinearProbing {
 
	public static char Keys[] = new char[11];
	public static int Values[] = new int[11];
 
	// Fonction de hachage par modulo sur le code ascii d'un caractère en entrée 
	public static int hash(char key, int M){
	int hash;
	int ascii;
	ascii=(int) (key); // récupère le code ASCII d'un caractère
	hash=ascii % M;	// hachage par modulo
	return hash;
	}
	public static void put(char key,int value){
		int M = 11;
		int index;
		index = hash (key,M);
		while (Keys[index] != '\0') {
				index = (index + 1);
				}
				Keys[index] = key;
				Values[index] = value;
	}
 
	public static void main(String[] args) {
		//Déclaration de ma table d'entrée R (Exemple du cours "Hash Table Linear Probing exemple")
		char R[]= new char[10];
		R[0]='B';
		R[1]='O';
		R[2]='E';
		R[3]='P';
		R[4]='C';
		R[5]='L';
		R[6]='X';
		R[7]='N';
		R[8]='D';
		R[9]='M';
		System.out.println("La table de données en entrée est la suivante :");
		System.out.println(R);
		System.out.println("***************************************************");
		int i;
		for (i=0; i<R.length; i++) {
			put(R[i],i);	
		}
		System.out.println(Keys);
		System.out.println(Values);
	}
 
	}

voilà j'ai l'impression que cette instruction ne s’exécute pas : Values[index] = value; à la compilation je retrouve ce résultat:
[I@4cf2f585
Alors que le premier tableau (Keys) se rempli normalement !!!

s'il vous plait je vais devenir folle

[kolodz]

La déclaration de tes tableaux ne corresponds pas à ce que tu veux en faire.

Si je lis ton algorithme on a :

1. Je déclare deux tableaux A et B d'index 0 à 9
2. Pour le tableau

Code :

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

char R[] ={'B','O','E','P','C','L','C','X','N','D','M'};

2.1 Je trouve le hash
2.2a Si le tableau n'a plus la valeur par défaut, je place la valeur à l'index du hash dans A et l'index de R à l'index du hash.
2.2b Sinon j'ajoute 1 au hash et je refait 2.2a

Le problème est le suivant :
Tu n'as aucune chance que ton hash se trouve systématiquement entre 0 et 9 !

Deux problèmes à cela !
Ton M est trop grand :

Code :

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

int M = 11;

Devrait être à 9 !
Et à la place de :

Code :

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

1
2
3
4
 
while (Keys[index] != '\0') {
index = (index + 1);
}

tu devrait avoir :

Code :

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

1
2
3
4
5
6
while (Keys[index] != '\0') {
if(index >=M){
index = 0;
}
index = (index + 1);
}

Sinon tu peux faire :

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
50
51
package TP8;
 
public class HashLinearProbing {
 
	public static char Keys[] = new char[11];
	public static int Values[] = new int[11];
 
	// Fonction de hachage par modulo sur le code ascii d'un caractère en entrée
	public static int hash(char key, int M) {
		int hash;
		int ascii;
		ascii = (int) (key); // récupère le code ASCII d'un caractère
		hash = ascii % M; // hachage par modulo
		return hash;
	}
 
	public static void put(char key, int value) {
		int M = 9;
		int index;
		index = hash(key, M);
		Keys[value] = key;
		Values[value] = index;
	}
 
	public static void main(String[] args) {
		// Déclaration de ma table d'entrée R (Exemple du cours
		// "Hash Table Linear Probing exemple")
		char R[] ={'B','O','E','P','C','L','C','X','N','D','M'};
		System.out.println("La table de données en entrée est la suivante :");
		System.out.println(R);
		System.out
				.println("***************************************************");
		int i;
		for (i = 0; i < R.length; i++) {
			put(R[i], i);
		}
		System.out.println(Keys);
		for (int j = 0; j < Values.length; j++) {
			System.out.print(Values[j]+";");
		}
		System.out.println();
		for (int j = 0; j < Values.length; j++) {
			for (int k = 0; k < Values.length; k++) {
				if(j== Values [k]){
					System.out.print(Keys[k]+"-");
				}
			}
		}
	}
 
}

Cordialement,
Patrick Kolodziejczyk.

[masoum]

Oui mais pourquoi alors le tableau Keys se rempli normalement, avec les valeurs théoriques !!! c'est à dire:
BCOEPXNDM L
Le hachage a bien eu lieu, ceci se fait en parcourant chaque caractère du tableau d'entrée R, en calculant le résultat de la fonction de hachage ; c'est à dire le code ascii du caractère modulo 11, le résultat sera l'index (la position) sur lequel placé le caractère en question dans le tableau Keys , et la valeur de son index d'origine dans le tableau values
exemple
Si B est le premier caractère du tableau R
le hashage de B donne : code ascii de B( = 66 ) modulo 11 donne : 0 donc l'index est 0 , c'est a dire que Keys[0]=B et values[0]=0, pourquoi 0? parc que 0 est la position de B dans son tableau d'origine R

voilà l'idée mais j'y arrive pas !!!! avec le tableau Values !!!!

[tchize_]

à la compilation je retrouve ce résultat:
[I@4cf2f585
Alors que le premier tableau (Keys) se rempli normalement !!!

D'abord ce n'est pas à la compilation mais à l'exécution que tu as cela.
Ensuite ton algorithme va t'exploser à la figure dans les cas plus complexes (plus de 11 lettres, ou quand les 2 premières lettre ont un hash de 10, ou ... etc)
Et finalement, pour ton problème, ce n'est pas comme ça qu'on affiche le contenu d'un tableau. Ce qu'il t'affiche juste c'est que "Values" est un tableau d'entiers. Pour afficher son contenu

Code :

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

1
2
3
 
		System.out.println(Arrays.toString(Keys));
		System.out.println(Arrays.toString(Values));

[masoum]

D'abord ce n'est pas à la compilation mais à l'exécution que tu as cela.
Ensuite ton algorithme va t'exploser à la figure dans les cas plus complexes (plus de 11 lettres, ou quand les 2 premières lettre ont un hash de 10, ou ... etc)
Et finalement, pour ton problème, ce n'est pas comme ça qu'on affiche le contenu d'un tableau. Ce qu'il t'affiche juste c'est que "Values" est un tableau d'entiers. Pour afficher son contenu

Code :

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

1
2
3
 
		System.out.println(Arrays.toString(Keys));
		System.out.println(Arrays.toString(Values));

oUI OUI C'est exactement ça, voilà le problème est résolu Merci beaucoup