Recherche dans un TreeMap (Java)

Question

Je dois faire une recherche dans une carte de cartes et retourner les clés cet élément appartient. Je pense que cette implémentation est très lente, pouvez-vous m'aider à l'optimiser? Je dois utiliser TreeSet et je ne peux pas utiliser contains car ils utilisent compareTo, et equals/compareTo pair sont implémentés de manière incompatible et je ne peux pas changer ça. (désolé mon mauvais anglais)

Map<Key, Map<SubKey, Set<Element>>> m = new TreeSet(); 

public String getKeys(Element element) { 
for(Entry<Key, Map<SubKey, Set<Element>>> e : m.entrySet()) { 
    mapSubKey = e.getValue(); 
    for(Entry<SubKey, Set<Element>> e2 : mapSubKey.entrySet()) { 
    setElements = e2.getValue(); 
    for(Element elem : setElements) 
    if(elem.equals(element)) return "Key: " + e.getKey() + " SubKey: " + e2.getKey(); 
    } 
} 
} 

Answer 1

Le problème ici est que les clés et les valeurs sont en arrière.

Les cartes permettent de trouver efficacement une valeur (Key et SubKey) associée à une clé (Element, dans cet exemple).

La marche arrière est lente.

Il existe des implémentations de cartes bidirectionnelles, telles que Google Collections BiMap, qui prennent en charge un accès plus rapide dans les deux directions — mais qui impliquent le remplacement de TreeMap. Sinon, conservez deux cartes, une pour chaque direction.

Answer 2

si vous ne pouvez pas utiliser contains, et vous êtes coincé à l'aide d'une carte de cartes, alors votre seule option est d'itérer, comme vous le faites.

Vous pouvez également conserver une carte inversée de Element à Key/SubKey dans une carte distincte, ce qui accélèrerait les recherches inversées.

aussi, si vous n'êtes pas sûr qu'une donnée Element peut exister dans un seul endroit, vous pouvez stocker et récupérer un List<Element> au lieu d'un Element

Answer 3

En utilisant TreeMap et TreeSet fonctionnent correctement lorsque compareTo et equals sont implémentés de telle sorte qu'ils sont compatibles les uns avec les autres. De plus, lors d'une recherche dans une carte, seule la recherche de la clé sera efficace (pour un TreeMap O (log n)). Lorsque vous recherchez une valeur dans une carte, la complexité devient linéaire.

Il existe cependant un moyen d'optimiser la recherche dans la partie interne TreeSet, lors de l'implémentation de votre propre Comparator pour le type d'élément. De cette façon, vous pouvez implémenter votre propre méthode compareTo sans changer l'objet Element lui-même.

Answer 4

Voici une TreeMap bidirectionnelle (ou Bijection over TreeMap).

Il associe deux TreeMaps surchargés qui sont liés ensemble.

Chaque champ constant "inverse" pointe vers l'autre TreeMap. Toute modification sur un TreeMap est automatiquement répercutée sur son inverse. Par conséquent, chaque valeur est unique. Par conséquent, chaque valeur est unique.

public class BiTreeMap<K, V> extends TreeMap<K, V> { 
    public final BiTreeMap<V, K> inverse; 

    private BiTreeMap(BiTreeMap inverse) { 
     this.inverse = inverse; 
    } 

    public BiTreeMap() { 
     inverse = new BiTreeMap<V, K>(this); 
    } 

    public BiTreeMap(Map<? extends K, ? extends V> m) { 
     inverse = new BiTreeMap<V, K>(this); 
     putAll(m); 
    } 

    public BiTreeMap(Comparator<? super K> comparator) { 
     super(comparator); 
     inverse = new BiTreeMap<V, K>(this); 
    } 

    public BiTreeMap(Comparator<? super K> comparatorK, Comparator<? super V> comparatorV) { 
     super(comparatorK); 
     inverse = new BiTreeMap<V, K>(this, comparatorV); 
    } 

    private BiTreeMap(BiTreeMap<V, K> inverse, Comparator<? super K> comparatorK) { 
     super(comparatorK); 
     this.inverse = inverse; 
    } 

    @Override 
    public V put(K key, V value) { 
     if(key == null || value == null) { 
      throw new NullPointerException(); 
     } 
     V oldValue = super.put(key, value); 
     if (oldValue != null && inverse._compareKeys(value, oldValue) != 0) { 
      inverse._remove(oldValue); 
     } 
     K inverseOldKey = inverse._put(value, key); 
     if (inverseOldKey != null && _compareKeys(key, inverseOldKey) != 0) { 
      super.remove(inverseOldKey); 
     } 
     return oldValue; 
    } 

    private int _compareKeys(K k1, K k2) { 
     Comparator<? super K> c = comparator(); 
     if (c == null) { 
      Comparable<? super K> ck1 = (Comparable<? super K>) k1; 
      return ck1.compareTo(k2); 
     } else { 
      return c.compare(k1, k2); 
     } 
    } 

    private V _put(K key, V value) { 
     return super.put(key, value); 
    } 

    @Override 
    public V remove(Object key) { 
     V value = super.remove(key); 
     inverse._remove(value); 
     return value; 
    } 

    private V _remove(Object key) { 
     return super.remove(key); 
    } 

    @Override 
    public void putAll(Map<? extends K, ? extends V> map) { 
     for (Map.Entry<? extends K, ? extends V> e : map.entrySet()) { 
      K key = e.getKey(); 
      V value = e.getValue(); 
      put(key, value); 
     } 
    } 

    @Override 
    public void clear() { 
     super.clear(); 
     inverse._clear(); 
    } 

    private void _clear() { 
     super.clear(); 
    } 

    public boolean containsValue(Object value) { 
     return inverse.containsKey(value); 
    } 

    @Override 
    public Map.Entry<K, V> pollFirstEntry() { 
     Map.Entry<K, V> entry = super.pollFirstEntry(); 
     inverse._remove(entry.getValue()); 
     return entry; 
    } 

    @Override 
    public Map.Entry<K, V> pollLastEntry() { 
     Map.Entry<K, V> entry = super.pollLastEntry(); 
     inverse._remove(entry.getValue()); 
     return entry; 
    } 
}