Поиск в 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

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

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

Answer 3

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

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

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

Answer 4

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

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

Каждое «обратное» константное поле указывает на другой 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;
    }
}