[Collections] map ordonnée + accès par indice

Version imprimable

22/04/2005, 13h45
jedimind

[Collections] map ordonnée + accès par indice

bonjour,

je cherche à mettre en place une structure de données qui aurait les fonctionnalités suivantes :

- type clé/valeur pour un accès direct via get(key)
- la structure doit être ordonnée (et l'ordre ne doit pas changer avec le temps) :
clé1 -> valeur1
clé2 -> valeur2
clé3 -> vlaeur3
- accès également par indice via get(i)

je travaille dans un envirronnement restreint et j'ai accès à :
- interfaces: Collection, List, Map, Set
- classes: AbstractCollection, AbstractList, AbstractMap, AbstractSet, ArrayList, Dictionary, HashMap, HashSet, Hashtable, Vector

bien sur aucune classe ne répond à tous ces besoins, il faut donc que j'implémente ma propre structure en étendant/implémentant quelque chose d'existant : à votre avis quelle est la meilleure façon de faire ?

Pour l'instant j'utilise des Hashtable et j'ai implémenté des methodes next et previous en me basant sur la clé de l'élément courant mais c'est assez lourd.
Pour la méthode next par exemple, à chaque fois je dois reparcourir ma hashtable jusqu'à positionner mon Enumeration (keys) sur l'élt courant et ensuite je fais un nextKey = nextElement() puis un maHashtable.get(nextKey) pour récupérer l'élt recherché ... ouf!

Pour mon souci d'ordre, je n'ai pas encore cherché mais je me suis rendu compte que lorsque l'on fait des put sur une hashtable, les éléments sont rangés à la façon d'une pile lifo, c'est à dire que mon 1er élt sera en fait le dernier élé ajouté.
Ensuite l'ordre ne bouge pas donc je pourrai me contenter d'inverser ma hashtable une fois remplie pour avoir les éléments dans le bon ordre mais je trouve ça un peu crade et en plus ça ne fonctionnera pas si j'ajoute des éléments après l'inversion ...

je pensais créer une classe qui implémenterait AbstractMap et rajouter une méthode get(int) (en m'aidant de AbstractMap.entrySet().toArray()) ... reste ce pb d'ordre ....

qu'en pensez vous ?
d'avance merci!

vincent
22/04/2005, 14h24
adiGuba

Re: [Structure données] map ordonnée + accès par indice

Citation:

Envoyé par jedimind

je pensais créer une classe qui implémenterait AbstractMap et rajouter une méthode get(int) (en m'aidant de AbstractMap.entrySet().toArray()) ... reste ce pb d'ordre ....

Salut,

Regarde si tu peux utiliser LinkedHashMap qui te permet de créer des map en conservant l'ordre d'ajout des éléments...

Ensuite su peux très bien utiliser entrySet().toArray() si ce n'est pas trop pénalisant en temps d'accès...

a++
22/04/2005, 14h28
jedimind

non, je n'ai pas accès à LinkedHashMap ...
en fait je travaille sur décodeur et l'api est assez limitée

en terme de conteneurs je n'ai accès qu'aux éléments du package util cités plus haut

Salut,

Pour cela il faut que tu travaille avec deux hashtables

La premiere contient tes données, la seconde est une table qui associe à un indice (ordre d'entré de tes éléments) la valeur de la clé correspondante dans la premiere table.

Je sais pas si je suis tres clair ?

Un petit exemple pour comprendre :
Code:

1 2 3 4 5 6 7 8 9 10 11 HashTable table1 = new HashTable(); HashTable table2 = new HashTable(); for (int i = 0 ; i < NombreElements ; i++){ table1.put(cle,valeur); table2.put(new Integer(i),cle); } String valeur1 = table1.get( table2.get(new Integer(0)));
Je pense que ca repond à ton probleme ?

PS : Le code n'est suremement pas syntaxiquement bon , c'est le principe qui compte.

22/04/2005, 14h44
jedimind

oui effectivement, c'est une solution
merci :)

n'hesitez pas qd même à continuer à vous creuser la tête :lol:
22/04/2005, 17h04
rootel77
pourquoi pas simplement deux List's? une pour les cles et l'autre pour les valeurs
pour get(Key) on peut traduire
Code:

1 2 3 4 5 try { return listValeurs.get(listCles.indexOf(Key); } catch(ArrayOutOfBoundsException e) { return null; }

effectivement, c'est aussi une solution ... qui m'a l'air plus optimisée d'ailleurs puisqu'on ne stocke pas 2 fois la clé et que les objets List doivent être plus "légers" que des Hashtable ...

Perso, j'avais commencé sur l'idée de chicorico :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
public class EnhancedHashtable {
 
	private Hashtable original;
	private Hashtable orderMapping;
 
	public EnhancedHashtable() {
		original = new Hashtable();
		orderMapping = new Hashtable();
	}
 
	public void put(Object key, Object value) {
		orderMapping.put(new Integer(original.size()), key);
		original.put(key, value);
	}
 
	public Object get(Object key) {
		return original.get(key);
	}
 
	public Object get(int i) {
		Object key = orderMapping.get(new Integer(i));
		Object value = null;
		try {
			value = original.get(key);
		} catch(NullPointerException npex) {}
 
		return value;
	}
 
	public void clear() {
		orderMapping.clear();
		original.clear();
	}
 
	public Object getFirstElement() {
		return this.get(0);
	}
 
	public Object getLastElement() {
		return this.get(original.size()-1);
	}
}

c'est simple et ça fonctionne :)

22/04/2005, 19h07
chicorico

:salut:

Merci d'avoir choisi ma piste :wink:

Citation:

Envoyé par jedimind

effectivement, c'est aussi une solution ... qui m'a l'air plus optimisée d'ailleurs puisqu'on ne stocke pas 2 fois la clé et que les objets List doivent être plus "légers" que des Hashtable ...

Quelques petites precisions,

La clé n'est pas stocké deux fois en mémoire (il n'y a pas ne new() ou de clone() ).
Il ne faut pas oublier quand java le passage des paramètres d'une fonction se fait par référence et non par valeur (notion de pointeur et d'adresse mémoire). Par consequent la valeur de l'objet clé n'est pas dupliqué :wink: .

L'acces est dans le pire des cas (c'est à dire recuperer le dernier element) linéaire avec une list, il est constant avec une HashTable...
Si t'as beaucoup de données, utilise une HashTable sinon la list.

Tu as probablement raison sur le fait qu'une HashTable prend plus de place en mémoire qu'une list, à cause du "new Integer(i)".

J'espere t'avoir apporter quelques precisions. Sinon , ta classe est tres bien :ccool:

A+.

LinkedHashMap

Bonjour,

Même ce sujet est bien résolu, mais je voudrai ajouter une solution propre et rapide :

Vous pouvez utiliser LinkedHashMap .
par exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Map<String, Integer> myMap = new LinkedHashMap<String, Integer>(); //insertion while (....) { myMap .put("blabla"+i, 1); } //affichage for(Entry<String, Integer> entry : myMap.entrySet()) { System.out.println("key: " + entry.getKey() + " -> value : " + entry.getValue()); }
Merci.