Discussion :

[Graffity]

Bonjour à tous !
Je n'arrive pas à trouver la bonne structure de donnée pour parcourir une table de hachage dans les deux sens en java, j'ai essayé de regarder dans la FAQ, les cours et le forums sans succès.

Voila mon problème :
Je voudrai trouver la structure de donnée qui permet de stocker comme une table de hachage des couples Clé - Clé alors qu'une HashMap classique est de type Clé - Valeur.

Je m'explique en prenant un exemple :
une table de hachage ou la clé vaut une "String" et la valeur un objet de type "Personne"

{"Nicolas" - "Objets instancié personne de nicolas",
"Jean" - "...",
"Pierre", "..."}

Dans une HashMap classique, la recherche de l'objet Personne de Nicolas est facile puisque une méthode permet de récupérer un élément à partir de sa clé (get(Object key)), mais comment faire l'inverse, si l'on connait l'objet de Nicolas et que l'on veut connaitre sa clé associé, comment pouvons nous faire.

J'ai pensé à 2 table de hachages, ou a une recherche classique en testant toutes les valeurs, existe t'il un autre moyen ?

[Elmilouse]

Tu peux peut-être utiliser l'API Commons du projet Apache Jakarta.
Dans les commons Collections, il y a les BidiMap qui pourraient te convenir.
http://jakarta.apache.org/commons/collections/

un article de Developpez.com qui explique cette collection BidiMap :

http://beuss.developpez.com/tutoriel...llections/#LVI

[Graffity]

Merci pour ta réponse super rapide, je vais donc essayer de regarder de plus près les classes du projet Jakarta comme BidiMap.

[jcarre]

a priori ta clé est issue de ton objet valeur (une methode getKey peut être). si tu as l'objet tu n'as qu'a appelé cette méthode. si ce n'est pas le cas, ne peux tu pas la stocker ds l'objet ?

[bouye]

Outre les API de Jakarta, ne serait'il pas tout simplement possible de faire qq chose dans ce style (rien de testé concrètement) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
public class MyMap<K,V> extends HashMap<K, V> {
 
  ...
 
  /** Gets a list iterator (bi-directionnal iterator) on all cells/pairs within the map.
   * @return A list iterator.
   */
  public ListIterator<Map.Entry<K, V>> entryListIterator() {
    List<Map.Entry<K,V>> entryList = new ArrayList<Map.Entry<K,V>>(entrySet());
    return entryList.listIterator();
  }
 
  /** Gets a list iterator (bi-directionnal iterator) on all values within the map.
   * @return A list iterator.
   */
  public ListIterator<V> valuesListIterator() {
    List<V> valueList = new ArrayList<V>(values());
    return valueList.listIterator();
  }
 
  /** Gets a list iterator (bi-directionnal iterator) on all keys within the map.
   * @return A list iterator.
   */
  public ListIterator<K> keysListIterator() {
    List<K> keyList = new ArrayList<K>(keySet());
    return keyList.listIterator();
  }
}

Si jamais ca marche (...), ca peut être bon dans une utilisation très simple où on est sur que le contenu de la Map ne change pas entre 2 appels sur un même Iterator. En effet la creation de la List à partir du Set fait une copie du contenu du Set dans la List. Les changements ultérieurs dans la Map ne sont donc pas répercutés dans la List.

Après on peut aussi imaginer une classe plus complète/complexe étendant HashMap<K, V> mais contenant en cache une List<K> des clés (qui est mis à jour à chaque ajout et retrait ; besoin de surcharger [i]remove(), put(), clear(), ...) et ayant un type d'Iterator customisé (pas si difficile à faire que ca). Dans ce cas tout changement sur la map serait automatiquement répercuté sur les Iterator utilisés.

EDIT - oups en relisant les posts j'ai vu que j'etais parti sur une mauvaise hypothese. Completement a cote de la plaque, desole.

Voici quelque chose qui devrait etre plus correct au vu de ce qui est demande (pas teste mais ca compile). A noter que quand on fait une requete sur la valeur la Map retourne une List<K> car on peut en effet avoir plusieurs cles pour la meme valeur. Si on veut une bijection cle <-> valeur, cela demande un peu plus de boulot mais c'est faisable.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
package test;
 
import java.util.*;
 
/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2006</p>
 * <p>Company: </p>
 * @author Fabrice Bouyé (fabriceb@spc.int)
 * @version 1.0
 */
public class BidiMap<K, V> implements Map<K, V> {
 
  /** Sub-container type for this map.
   * <p>Title: </p>
   * <p>Description: </p>
   * <p>Copyright: Copyright (c) 2006</p>
   * <p>Company: </p>
   * @author Fabrice Bouyé (fabriceb@spc.int)
   * @version 1.0
   */
  public enum Flavor {
    HASH_MAP, HASH_TABLE, TREE_MAP;
  }
 
 
  /** Main delegated map.
   * Has a 1 -> 1 relationship between key and value.
   */
  private Map<K, V> delegated;
 
  /** The reverse delegated map.
   * Has a 1 -> * relationship between the value and the key.
   */
  private Map<V, List<K>> reverseDelegated;
 
  /** Creates a new instance with hashmaps.
   */
  public BidiMap() {
    this(Flavor.HASH_MAP);
  }
 
  /** Creates a new instance with given flavor containers.
   * @param flavor The container type.
   * @see #Flavor
   */
  public BidiMap(Flavor flavor) {
    switch (flavor) {
      case HASH_TABLE: {
        delegated = new Hashtable<K, V>();
        reverseDelegated = new Hashtable<V, List<K>>();
      }
      break;
      //
      case TREE_MAP: {
        delegated = new TreeMap<K, V>();
        reverseDelegated = new TreeMap<V, List<K>>();
      }
      break;
      //
      case HASH_MAP:
      default: {
        delegated = new HashMap<K, V>();
        reverseDelegated = new HashMap<V, List<K>>();
      }
    }
  }
 
  /** {@inheritDoc}
   */
  public void clear() {
    delegated.clear();
    reverseDelegated.clear();
  }
 
  /** {@inheritDoc}
   */
  public boolean containsKey(Object key) {
    return delegated.containsKey(key);
  }
 
  /** {@inheritDoc}
   */
  public boolean containsValue(Object value) {
    // Should be faster this way.
    return reverseDelegated.containsKey(value);
  }
 
  /** {@inheritDoc}
   */
  public Set<Map.Entry<K, V>> entrySet() {
    return delegated.entrySet();
  }
 
  /** {@inheritDoc}
   */
  public V get(Object key) {
    return delegated.get(key);
  }
 
  /** {@inheritDoc}
   */
  public boolean isEmpty() {
    return delegated.isEmpty();
  }
 
  /** {@inheritDoc}
   */
  public Set<K> keySet() {
    return delegated.keySet();
  }
 
  /** {@inheritDoc}
   */
  public V put(K key, V value) {
    V oldValue = delegated.put(key, value);
    if (oldValue != null) {
      List<K> keyList = reverseDelegated.get(oldValue);
      if (keyList != null) {
        keyList.remove(key);
      }
    }
    if (value != null) {
      List<K> keyList = reverseDelegated.get(value);
      if (keyList == null) {
        keyList = new LinkedList<K>();
        reverseDelegated.put(value, keyList);
      }
      if (!keyList.contains(key)) {
        keyList.add(key);
      }
    }
    return oldValue;
  }
 
  /** {@inheritDoc}
   */
  public void putAll(Map<? extends K, ? extends V> t) {
    for (K key : t.keySet()) {
      V value = t.get(key);
      put(key, value);
    }
  }
 
  /** {@inheritDoc}
   */
  public V remove(Object key) {
    V value = delegated.remove(key);
    if (value != null) {
      reverseDelegated.remove(value);
    }
    return value;
  }
 
  /** {@inheritDoc}
   */
  public int size() {
    return delegated.size();
  }
 
  /** {@inheritDoc}
   */
  public Collection<V> values() {
    return delegated.values();
  }
 
  /** Gets all keys for a given value.
   * @param value The queried value.
   * @return A non-modifiable list of keys, maybe <code>null</code>.
   */
  public List<K> keysForValue(V value) {
    List<K> result = reverseDelegated.get(value);
    if (result != null) {
      result = Collections.unmodifiableList(result);
    }
    return result;
  }
}