Algorithme de recherche Résolu

Question

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.

cs_DARKSIDIOUS · Accepted Answer

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

cs_DARKSIDIOUS · Answer

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

cs_Taz1984 · Answer

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

cs_DARKSIDIOUS · Answer

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 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],tabledeNomChampXSD[i]); } ______________________________________ AVANT de poster votre message, veuillez lire, comprendre, et appliquer notre réglement

cs_Taz1984 · Answer

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 ?

Algorithme de recherche

5 réponses

Votre réponse

Discussions similaires