Utilisation d'une hashtable java avec une clé partielle
Le
isabe
Bonjour,
Je souhaite établir une correspondance entre le début dune chaine est une autre chaine.
Exemple :
Si la chaine commence par « 12345 » elle fait partie du GROUPE1, si elle commence par « 542 » elle fait partir du GROUPE2
Jai créé une hashtable avec comme clé 12345*, 245*,542*, et les valeurs de GROUPE correspondantes.
Par contre je ne sais pas comment faire quand je reçois ma String sur 16 caractères pour trouver son groupe dappartenance ?
Merci de votre aide
Je souhaite établir une correspondance entre le début dune chaine est une autre chaine.
Exemple :
Si la chaine commence par « 12345 » elle fait partie du GROUPE1, si elle commence par « 542 » elle fait partir du GROUPE2
Jai créé une hashtable avec comme clé 12345*, 245*,542*, et les valeurs de GROUPE correspondantes.
Par contre je ne sais pas comment faire quand je reçois ma String sur 16 caractères pour trouver son groupe dappartenance ?
Merci de votre aide
Bonjour,
C'est facile, il suffit de f
:-))))
--
Cordialement, Thierry ;-)
Il suffit de f... quoi?
isabe
Le message d'origine était tronqué ;)
Ca ne suffit pas à fournir une meilleure réponse que
:)
Quel est votre problème exactement ?
Je souhaite établir une correspondance entre le début d'une chaine est une autre chaine.
Exemple :
Si la chaine commence par « 12345 » elle fait partie du GROUPE1, si elle commence par « 542 » elle fait partir du GROUPE2 ...
J'ai créé une hashtable avec comme clé 12345*, 245*,542*, ... et les valeurs de GROUPE correspondantes.
Par contre je ne sais pas comment faire quand je reçois ma String sur 16 caractères pour trouver son groupe d'appartenance ?
Merci de votre aide
isabe
Je ne suis pas sûr de comprendre.
Vous voulez faire l'association chaîne complète -> nom du groupe
(GROUPE1, GROUPE2, ...), c'est ça ?
Je suppose que vous ne voulez pas lister les débuts de chaîne dans le
code mais les retrouver dans la table de hachage. Dans ce cas vous
pouvez la parcourir, par exemple avec quelque chose comme ça (de
mémoire) :
String laChaineATester = "12349090786" ;
for (Entry<String,Groupe> entree : tableHachage.entrySet())
{
if (laChaineATester.startsWith (entree.getKey()))
System.out.println ("Groupe : " + entree.getValue()) ;
}
(note : pour ça il ne faut pas mettre les étoiles dans les clés)
Ca permet de faire les associations, mais ce n'est pas très efficace
évidemment.
Ah tiens, TreeMap semble faire ce que vous cherchez : en utilisant
ceilingEntry() vous devriez y arriver : ceilingEntry renvoie l'entrée
dans la table d'association correspondant à la clé la plus proche de
celle fournie en paramètre (clé inférieure ou égale à la clé fournie
en paramètre).
Donc en appelant tableHachage.ceilingEntry (laChaineATester) on
récupère la valeur dont la clé est la plus proche de la chaîne à
tester, sans la dépasser (les comparaisons sur les chaînes se font
sur l'ordre alphabétique). Il faut ensuite vérifier que la clé
renvoyée est bien un préfixe de la chaîne (le nom complet de la
classe Entry est Map.Entry) :
Entry<String,Groupe> entree = tableHachage.ceilingEntry
(laChaineATester) ;
if (laChaineATester.startsWith (entree.getKey()))
System.out.println ("Groupe : " + entree.getValue()) ;
else
System.out.println ("Groupe non trouvé") ;
(note : il ne faut toujours pas mettre les étoiles dans les clés pour
que ça marche)
Bien sûr je parle toujours de table de hachage alors qu'il s'agit d'un
arbre, c'est un peu abusif, mais c'était pour suivre votre question.
Et la classe TreeMap implémente bien sûr Map, comme HashMap.
Est-ce que ça vous convient ?
Bonne idée, merci beaucoup.
Par contre le fait d’utiliser TreeMap plutôt que HashMap ne risque-t-il pas d’être pénalisant au niveau performance ?
Ca dépend de ce que vous en faites.
Malheureusement je ne me souviens plus très bien des cas où les arbres
sont plus (ou moins) efficaces que les tables de hachage :( .
Pour la consultation je crois qu'ils sont en principe un peu plus lent,
mais il n'y a pas de problème de code de hachage (pas besoin de code
de hachage en théorie [mais la spécification de Map indique que
n'importe quelle implémentation peut se servir du code de hachage] et
pas de risque d'avoir de nombreuses clés ayant le même code de
hachage si la fonction de hachage est mal choisie).
Par contre pour l'insertion je crois que c'est plus souple parce qu'ils
peuvent croître régulièrement, alors qu'une table de hachage doit
être dimensionnée correctement au début ou réorganisée au fur et à
mesure qu'elle croît pour ne pas être trop remplie (si elle est
pleine, elle perd tout son intérêt).
Ce sont souvent des arbres qui sont utilisés pour les index des bases
de données, ce n'est quand même pas si lent :) .
Valdo TSCHANTRÉ
Ah ouais, zut... j'ai été un peu vite
La solution avec les sorted map est plutôt élégante car elle utilise
l'API de la JDK.
Par contre, elle cache un algo un peu plus simple IMHO: la recherche
dychotomique.
Je ne sais pas combien il existe de groupes mais les clés sont connues
d'avance.
Donc le but est connaître le numéro de groupe dans lequel tu dois
"ranger" ta valeur.
Je propose donc d'utiliser l'implémentation de la recherche dychotomique
qui est faîte dans java.util.Collections au travers de la méthode
binarySerach(liste, key) pour rechercher ce numéro puis d'insérer la
valeur dans le groupe correspondant.
Je ferais qqch du genre:
<code>
final int p = ...;
List<String> keys = new ArrayList<String>(p);
keys.add(key1);
...
keys.add(keyp);
List<String>[] groups = (List<String>[])
Array.newInstance(LinkedList.class, p);
for (int i = 0; i < groups.length; i++)
{
// je choisi linkedlist car les insertions sont moins coûteuses à priori
groups[i] = new LinkedList<String>();
}
for (String value : sample)
{
int binarySearch= Collections.binarySearch(keys, value);
int key= binarySearch >= 0 ? binarySearch : (-binarySearch-1-1);
groups[key].add(value);
}
</code>
Est-ce que cela répond à ton besoin ?