Algorithme de recherche [Résolu]

cs_Taz1984 47 Messages postés lundi 20 juillet 2009Date d'inscription 13 mars 2013 Dernière intervention - 20 avril 2010 à 17:09 - Dernière réponse : cs_DARKSIDIOUS 15838 Messages postés jeudi 8 août 2002Date d'inscription 4 mars 2013 Dernière intervention
- 21 avril 2010 à 11:29
Bonjour,

j'ai un tableau qui contient 10000 cases de chaines de caractères.

Lorsque je recherche un élément dans ce tableau, je suis obligé de parcourir 10000 cases.

Et plus le tableau contiendra de cases et plus l'algorithme de recherche sera long.

Mon but est d'optimiser la recherche.

Au lieu d'utiliser un tableau , je peux utiliser un ArrayList mais bon la recherche sera longue de la même façon.

Je pensais créer une HashMap ou HashTable . Mais le fait de créer une HasMap ou HashTable que vais je mettre comme clé ??

Je pensais que la clé était calculé via la méthode hashcode() !!

Je suis un peu perdu , merci pour votre aide.
Afficher la suite 

5 réponses

Répondre au sujet
cs_DARKSIDIOUS 15838 Messages postés jeudi 8 août 2002Date d'inscription 4 mars 2013 Dernière intervention - 21 avril 2010 à 11:29
+3
Utile
Salut,

Je n'ai pas fait de test particulier, mais je pense qu'entre une clé de type String et une clé de type Integer, le temps d'accès à un object contenu dans le HashMap doit être sensiblement le même (si ce n'est le même temps).

Après, niveau comparaison entre une HashMap et une HashTable :
http://forums.sun.com/thread.jspa?trange=15&threadID=536477&forumID=24&tstart=0

Mais déjà, si tu utilises un HashMap ou HashTable (par rapport à l'utilisation d'un tableau non trié ou d'une simple Collection) le temps d'accès sera déjà largement suffisant même si tu as 10 000 entrées ou plus.

______________________________________

AVANT de poster votre message, veuillez lire, comprendre, et appliquer notre réglement
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_DARKSIDIOUS
cs_DARKSIDIOUS 15838 Messages postés jeudi 8 août 2002Date d'inscription 4 mars 2013 Dernière intervention - 20 avril 2010 à 17:44
0
Utile
Salut,

Est-ce que tu veux cherche un seul élément en particulier ?

A ce moment là, un HashTable sera bien plus rapide en accès.

Tu peut mettre une clé de type String, entier, pas de problème. Le hashCode permet de calculer le HASH de l'objet si la clé est de type Object.
______________________________________

AVANT de poster votre message, veuillez lire, comprendre, et appliquer notre réglement
Commenter la réponse de cs_DARKSIDIOUS
cs_Taz1984 47 Messages postés lundi 20 juillet 2009Date d'inscription 13 mars 2013 Dernière intervention - 21 avril 2010 à 10:27
0
Utile
Salut, merci pour ta réponse , j'ai pris un petit exemple :
Hashtable tab = new Hashtable();
   
String[] tabledeNomChampXSD = new String[12];
tabledeNomChampXSD[0] = "defanationBn";
tabledeNomChampXSD[6] = "ronCode1";
tabledeNomChampXSD[1] = "rejectCode"; 
tabledeNomChampXSD[7] = "Code2";
tabledeNomChampXSD[2] = "strDestBin";
tabledeNomChampXSD[8] = "Code3";
tabledeNomChampXSD[3] = "srcBin";
tabledeNomChampXSD[9] = "Code4";
tabledeNomChampXSD[4] = "Code";
tabledeNomChampXSD[10] = "onCode5";
tabledeNomChampXSD[5] = "rrency";
tabledeNomChampXSD[11] = "Number";

  for (int i = 0; i < tabledeNomChampXSD.length; i++) {
  tab.put(tabledeNomChampXSD[i].hashCode(),tabledeNomChampXSD[i]);
  
}

Enumeration valeurs = tab.elements();
Enumeration cles = tab.keys();

 while(valeurs.hasMoreElements() && cles.hasMoreElements()){
      System.out.println(" Entrée : " + valeurs.nextElement() + " Clés " + cles.nextElement());
      
 }
 
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    System.out.print("Enter le nom rechercher: ");
    String strTitle = null;
try {
strTitle = in.readLine();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

boolean arret = tab.contains(strTitle);

//= true;

if (arret == true ){
System.out.println("le nom "+strTitle+" a bien été trouvé :-)" );
}	else 
{
System.out.println("le nom "+strTitle+" n'a pas  été trouvé  :-(" );
}


Normalement , comme ca c'est plus rapide au niveau de la recherche, mais est ce que je peux définir par moi même la clé, je veux dire redéfinir la fonction hashcode().

Car j'ai vu que pour les String, le hashcode a une règle de calcul , est ce que je peux définir cette régle par mes propres moyens ?


Merci d'avance
Commenter la réponse de cs_Taz1984
cs_DARKSIDIOUS 15838 Messages postés jeudi 8 août 2002Date d'inscription 4 mars 2013 Dernière intervention - 21 avril 2010 à 10:32
0
Utile
Salut,

Je ne comprends toujours pas pourquoi tu veut surcharger le HashCode si tu ne mets que des String dans ton HashTable...

Ton hashTable peut recevoir ce que tu veux comme clé, tu n'es pas limité à un entier :
Hashtable<String, String> tab = new Hashtable<String, String>();
   
String[] tabledeNomChampXSD = new String[12];
tabledeNomChampXSD[0] = "defanationBn";
tabledeNomChampXSD[6] = "ronCode1";
tabledeNomChampXSD[1] = "rejectCode"; 
tabledeNomChampXSD[7] = "Code2";
tabledeNomChampXSD[2] = "strDestBin";
tabledeNomChampXSD[8] = "Code3";
tabledeNomChampXSD[3] = "srcBin";
tabledeNomChampXSD[9] = "Code4";
tabledeNomChampXSD[4] = "Code";
tabledeNomChampXSD[10] = "onCode5";
tabledeNomChampXSD[5] = "rrency";
tabledeNomChampXSD[11] = "Number";

  for (int i = 0; i < tabledeNomChampXSD.length; i++) {
  tab.put(tabledeNomChampXSD[i],tabledeNomChampXSD[i]);
  
}


______________________________________

AVANT de poster votre message, veuillez lire, comprendre, et appliquer notre réglement
Commenter la réponse de cs_DARKSIDIOUS
cs_Taz1984 47 Messages postés lundi 20 juillet 2009Date d'inscription 13 mars 2013 Dernière intervention - 21 avril 2010 à 10:51
0
Utile
Je voudrai optimiser la rechercher, enfin trouver la meilleur clé qui me permet d'optimiser la recherche dans mon hachage !! c'est pour ca que cette histoire de clé j'ai du mal à l'assimiler !! au lieu de hashtable j'aurai pu utiliser hastmap ?
Commenter la réponse de cs_Taz1984

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.