Utilisation d'une hashtable java avec une clé partielle

isabe

unread,

Oct 29, 2009, 7:30:30 AM10/29/09

to

Bonjour,
Je souhaite ï¿½tablir une correspondance entre le dï¿½but d

Patrick

unread,

Oct 29, 2009, 7:33:50 AM10/29/09

to

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

Cenekemoi

unread,

Oct 29, 2009, 9:03:49 AM10/29/09

to

"Patrick" <peuim...@quelquepart.fr> a ï¿½crit dans le message de
news:4ae97d9e$0$9955$426a...@news.free.fr...

:-))))

--
Cordialement, Thierry ;-)

isabe

unread,

Oct 29, 2009, 12:04:11 PM10/29/09

to

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?

Yliur

unread,

Oct 29, 2009, 12:44:20 PM10/29/09

to

Le Thu, 29 Oct 2009 11:04:11 -0500
isabe <is...@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 ?

isabe

unread,

Oct 29, 2009, 1:46:00 PM10/29/09

to

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

Yliur

unread,

Oct 29, 2009, 4:21:10 PM10/29/09

to

Le Thu, 29 Oct 2009 12:46:00 -0500
isabe <is...@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 ?

isabe

unread,

Oct 30, 2009, 3:20:15 AM10/30/09

to

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 ?

Yliur

unread,

Oct 30, 2009, 11:03:33 AM10/30/09

to

> 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É

unread,

Dec 2, 2009, 11:54:07 AM12/2/09

to

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 plus 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.

Yliur

unread,

Dec 9, 2009, 5:21:34 PM12/9/09

to

Le Wed, 02 Dec 2009 17:54:07 +0100
Valdo TSCHANTRÉ <PRENO...@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 plus
> > 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

steph

unread,

Jan 5, 2010, 6:11:37 PM1/5/10

to

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 ?