在TreeMap中搜索（Java）

Question

我需要在地圖映射中進行搜索並返回此元素所屬的鍵。 我覺得這個實現很慢，你能幫我優化嗎？ 我需要使用TreeSet，我不能使用contains，因爲它們使用compareTo，而equals/compareTo pair是以不兼容的方式實現的，我不能改變它。 （對不起我的英文不好）

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

這裏的問題是鍵和值是落後的。

地圖允許人們有效地找到與鍵（Element，在此示例中）相關聯的值（將爲Key和SubKey）。

向後走很慢。

有雙向映射實現，如Google Collections BiMap,，支持雙向快速訪問—，但這意味着將替換TreeMap。否則，保持兩個地圖，每個方向一個。

Answer 2

，如果你不能使用contains，和您使用的地圖地圖的卡，那麼你唯一的選擇是迭代，因爲你在做什麼。

或者，您可以在單獨的地圖中保留一個反向地圖Element到Key/SubKey，這將使反向查找更快。

另外，如果你不知道給定Element只能在一個地方存在，你可能想存儲和檢索List<Element>，而不僅僅是一個Element

Answer 3

使用TreeMap和TreeSet正常工作時compareTo和equals以這樣的方式實現，即它們彼此兼容。此外，在Map中搜索時，只有搜索關鍵字纔是有效的（對於TreeMap O（log n））。在Map中搜索值時，複雜度將變爲線性。

雖然在爲元素類型實現您自己的Comparator時，有一種方法可以優化內部TreeSet中的搜索。這樣你就可以實現你自己的compareTo方法而不用改變Element對象本身。

Answer 4

這是一個雙向TreeMap（或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; 
    } 
}