Utilisation d'une hashtable java avec une clé partielle

Le 29/10/2009 13:30, isabe a écrit :

Bonjour,
Je souhaite établir une correspondance entre le début d

Bonjour,
C'est facile, il suffit de f

"Patrick" <peuimporte@quelquepart.fr> a écrit dans le message de
news:4ae97d9e$0$9955$426a34cc@news.free.fr...

Le 29/10/2009 13:30, isabe a écrit :

Bonjour,
Je souhaite établir une correspondance entre le début d

Bonjour,
C'est facile, il suffit de f

:-))))

--
Cordialement, Thierry ;-)

Cenekemoi a écrit le 29/10/2009 à 14h03 :

"Patrick" a écrit dans le
message de
news:4ae97d9e$0$9955$

Le 29/10/2009 13:30, isabe a écrit :

Bonjour,
Je souhaite établir une correspondance entre le début d

Bonjour,
C'est facile, il suffit de f

:-))))

--
Cordialement, Thierry ;-)

Il suffit de f... quoi?

Le Thu, 29 Oct 2009 11:04:11 -0500
isabe <isabe@domain-xyz.in> a écrit :

Cenekemoi a écrit le 29/10/2009 à 14h03 :
> "Patrick" a écrit dans le
> message de
> news:4ae97d9e$0$9955$
>> Le 29/10/2009 13:30, isabe a écrit :
>>> Bonjour,
>>> Je souhaite établir une correspondance entre le début d
>>>
>>
>> Bonjour,
>> C'est facile, il suffit de f
>>
>
>
> :-))))
>
> --
> Cordialement, Thierry ;-)
Il suffit de f... quoi?

Le message d'origine était tronqué ;)

>>> Bonjour,
>>> Je souhaite établir une correspondance entre le début d

Ca ne suffit pas à fournir une meilleure réponse que

>> C'est facile, il suffit de f

:)

Quel est votre problème exactement ?

Yliur a écrit le 29/10/2009 à 17h44 :

Le Thu, 29 Oct 2009 11:04:11 -0500
isabe a écrit :

Cenekemoi a écrit le 29/10/2009 à 14h03 :
> "Patrick" a écrit dans le
> message de
> news:4ae97d9e$0$9955$
>> Le 29/10/2009 13:30, isabe a écrit :
>>> Bonjour,
>>> Je souhaite établir une correspondance entre le
début d
>>>
>>
>> Bonjour,
>> C'est facile, il suffit de f
>>
>
>
> :-))))
>
> --
> Cordialement, Thierry ;-)
Il suffit de f... quoi?

Le message d'origine était tronqué ;)

>>> Bonjour,
>>> Je souhaite établir une correspondance entre le
début d

Ca ne suffit pas à fournir une meilleure réponse que

>> C'est facile, il suffit de f

:)

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

Le Thu, 29 Oct 2009 12:46:00 -0500
isabe <isabe@domain-xyz.in> a écrit :

Yliur a écrit le 29/10/2009 à 17h44 :
> Le Thu, 29 Oct 2009 11:04:11 -0500
> isabe a écrit :
>
>> Cenekemoi a écrit le 29/10/2009 à 14h03 :
>> > "Patrick" a écrit dans le
>> > message de
>> > news:4ae97d9e$0$9955$
>> >> Le 29/10/2009 13:30, isabe a écrit :
>> >>> Bonjour,
>> >>> Je souhaite établir une correspondance entre le
>> début d
>> >>>
>> >>
>> >> Bonjour,
>> >> C'est facile, il suffit de f
>> >>
>> >
>> >
>> > :-))))
>> >
>> > --
>> > Cordialement, Thierry ;-)
>> Il suffit de f... quoi?
>>
>
>
> Le message d'origine était tronqué ;)
>
>> >>> Bonjour,
>> >>> Je souhaite établir une correspondance entre le
>> début d
>>
>
> Ca ne suffit pas à fournir une meilleure réponse que
>
>> >> C'est facile, il suffit de f
>>
>
> :)
>
> 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

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 ?

Yliur a écrit le 29/10/2009 à 21h21 :

Le Thu, 29 Oct 2009 12:46:00 -0500
isabe a écrit :

Yliur a écrit le 29/10/2009 à 17h44 :
> Le Thu, 29 Oct 2009 11:04:11 -0500
> isabe a écrit :
>
>> Cenekemoi a écrit le 29/10/2009 à 14h03 :
>> > "Patrick" a écrit dans le
>> > message de
>> > news:4ae97d9e$0$9955$
>> >> Le 29/10/2009 13:30, isabe a écrit :
>> >>> Bonjour,
>> >>> Je souhaite établir une correspondance entre le
>> début d
>> >>>
>> >>
>> >> Bonjour,
>> >> C'est facile, il suffit de f
>> >>
>> >
>> >
>> > :-))))
>> >
>> > --
>> > Cordialement, Thierry ;-)
>> Il suffit de f... quoi?
>>
>
>
> Le message d'origine était tronqué ;)
>
>> >>> Bonjour,
>> >>> Je souhaite établir une correspondance entre le
>> début d
>>
>
> Ca ne suffit pas à fournir une meilleure réponse que
>
>> >> C'est facile, il suffit de f
>>
>
> :)
>
> 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

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 ?

> 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 :) .

Le Wed, 02 Dec 2009 17:54:07 +0100
Valdo TSCHANTRÉ <PRENOM.NOM@GMAIL-NOSPAM.COM> a écrit :

Yliur a écrit :
> 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 pl us
> proche de celle fournie en paramètre (clé inférieure ou égale à la
> clé fournie en paramètre).

Attention, il faut utiliser floorEntry et non ceilingEntry.

Valdo.

Ah ouais, zut... j'ai été un peu vite

isabe wrote:

Yliur a écrit le 29/10/2009 à 17h44 :

Le Thu, 29 Oct 2009 11:04:11 -0500
isabe a écrit :

Cenekemoi a écrit le 29/10/2009 à 14h03 :

"Patrick" a écrit dans le
message de
news:4ae97d9e$0$9955$

Le 29/10/2009 13:30, isabe a écrit :

Bonjour,
Je souhaite établir une correspondance entre le

début d

Bonjour,
C'est facile, il suffit de f

:-))))

--
Cordialement, Thierry ;-)

Il suffit de f... quoi?

Le message d'origine était tronqué ;)

Bonjour,
Je souhaite établir une correspondance entre le

début d

Ca ne suffit pas à fournir une meilleure réponse que

C'est facile, il suffit de f

:)

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

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 ?