Поиск в TreeMap (Java)

Question

Мне нужно выполнить поиск на карте карт и вернуть ключи, которым принадлежит этот элемент. Я думаю, что эта реализация очень медленная, можете ли вы помочь мне ее оптимизировать? Мне нужно использовать TreeSet, и я не могу использовать его, потому что они используют compareTo, а пара equals/compareTo реализована несовместимо, и я не могу это изменить. (извините мой плохой английский)

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

Проблема в том, что ключи и значения обратные.

Карты позволяют эффективно находить значение (которое должно быть Key и SubKey), связанное с ключом (Element, в этом примере).

Возвращение назад медленно.

Существуют двунаправленные реализации карты, такие как Google Collections BiMap,, которые поддерживают быстрый доступ в обоих направлениях —, но это означало бы замену TreeMap. В противном случае поддерживайте две карты, по одной для каждого направления.

Answer 2

, если вы не можете использовать contains, и вы застряли с использованием карты Карт, то ваш единственный реальный вариант для перебора, как вы делаете.

В качестве альтернативы, вы можете сохранить обратную карту от Element до Key/SubKey на отдельной карте, что бы ускорить обратный поиск.

также, если вы не уверены, что данный Element может существовать только в одном месте, вы можете хранить и извлекать List<Element> вместо простого Element

Answer 3

Использование TreeMap и TreeSet работать должным образом, когда compareTo и equals реализованы таким образом, что они совместимы друг с другом. Кроме того, при поиске на Карте будет эффективен только поиск ключа (для TreeMap O (log n)). При поиске значения на карте сложность станет линейной.

Существует способ оптимизации поиска во внутреннем TreeSet, хотя при реализации вашего собственного Comparator для типа Элемент. Таким образом, вы можете реализовать свой собственный метод compareTo без изменения самого элемента Element.

Answer 4

Вот двунаправленная TreeMap (или Bijection over TreeMap).

Он связывает две перегруженные TreeMaps, которые связаны друг с другом.

Каждое «обратное» постоянное поле указывает на другую TreeMap. Любое изменение на одном TreeMap автоматически отражается на его обратном.

В результате каждое значение уникально.

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; 
    } 
}