當「Set」不合適時，NavigableSet是否有其他替代方法？

NavigableSet接口提供了許多有用的方法，正常的Set沒有（特別是我正在考慮諸如headSet和tailSet等方法）。但是，作爲Set，它不支持重複的元素。此外，作爲SortedSet，訂購必須符合equals和hashCode以避免違反Set界面的合同。當「Set」不合適時，NavigableSet是否有其他替代方法？

根據equals方法，根據自然順序或比較符而不是「相等」時，是否有任何好的替代數據結構用於何時可能有重複元素或多個元素「相等」？作爲一種激勵的例子，考慮下面的代碼顯示爲什麼NavigableSet是不恰當的：

public class Foo implements Comparable<Foo>{ 
    double x; 
    double y; 

    @Override 
    public int compareTo(Foo o) { 
    return Double.compare(x, o.x); // only x matters for sort order 
    } 

    public static void main(String...args){ 
    Foo a = new Foo(); 
    a.x = 1; 
    a.y = 2; 

    Foo b = new Foo(); 
    b.x = 1; 
    b.y = 42; 

    Foo c = new Foo(); 
    c.x = 2; 
    c.y = 12.34; 

    NavigableSet<Foo> set = new TreeSet<Foo>(); 
    set.add(a); 
    set.add(a); 
    set.add(b); 
    set.add(c); 

    System.out.println(set.size()); 
    } 
}

注意元素a只被添加一次（當然，因爲這是一個Set）。另外，請注意，b不會被添加，因爲已經有一個元素的比較返回0.

我覺得這可能是一個相當普遍的事情，所以我希望找到一個現有的實現，而不是滾動我的擁有。我的目的是否有一個很好的，廣泛使用的數據結構？

我會補充一點，在寫這個問題的時候我碰到過Biscotti Project，但是a）我不相信它解決了比較/等於問題，b）FAQ明確表示它不是真的安全使用。

來源

2012-09-18 Michael McGowan

列表？我覺得我錯過了你的問題。只是在添加時想要自動重新排序？您不必將自己的整個集合滾動到包含在添加後對其進行排序的實用程序方法中的列表中。 – Affe

是的，這將完成我想要的一部分，但接下來還有其他的實用方法，我提到像'headSet'等。我也可以實現所有這些，或者我可以儘量避免重新發明輪子。 –

@MichaelMcGowan如果你按x排序然後按y排序，那麼這是一個問題（即只有在x相同的情況下按y排序）？這將解決您的問題... – assylias

讓我重新闡述你的問題，以確保我理解得很好。需要headSet和tailSet意味着集合必須被排序。這與根據compareTo允許重複成員的需要相沖突。

衝突來自這種收集的有效使用。向排序後的集合中添加成員是利用O（log n）中的compareTo方法完成的 - 類型二分搜索，然後添加。 TreeSet使用TreeMap實施，根據compareTo不能有兩個相同的成員。

你在找什麼不會有效。

您可以嘗試使用簡單ArrayList和Collections.sort排序，然後使用sublist方法。問題在於它根本不處理重複。
您也可以使用LinkedHashSet處理重複項（根據equals()，它是免疫到compareTo()），但它沒有排序。當然，您可以通過在構造函數中傳遞其實例來將LinkedHashSet實例轉換爲SortedSet。

來源

2012-09-18 23:53:10

'LinkedHashSet'不允許重複。 –

這就是我所知道的，根據equals（）不允許兩個相同的條目，但根據compareTo（）（entry1.compareTo（entry2）== 0），兩個條目可以是「相同的」。 LinkedHashSet的重要性，以及我忘記添加的是保留排序。 –

當「Set」不合適時，NavigableSet是否有其他替代方法？

回答

相關問題