寫作包含（）通用集合

Question

我正在寫一個作爲excercise在java中的skiplist類。我寫了一個名爲SkipListInternal<E>的課程，其中包含實際的跳過列表。我還製作了一個名爲SkipListSet<E>的包裝類，它實現了SortedSet<E>接口幷包含SkipListInternal<E>的一個實例。

除其他事項外，SkipListInternal<E>包含方法E find(E e)如果其存在，其返回元素等於e，否則返回null。

當寫boolean contains(Object o)方法我注意到，它的參數是一個對象，而不是一個E.我打算做這樣的事情，但是是不可能的，因爲類型擦除（通過SortedSet<E>從Collection<E>繼承）：

public class SkipListSet<E> implements SortedSet<E>{ 
    private SkipListInternal<E> skiplist; 

    ... 

    public boolean contains(Object o){ 
     if (!(o instanceof E)) return false; 
     return skiplist.find((E) o) != null; 
    } 

    ... 

} 

既然不能這樣做，我該怎麼做呢？

Answer 1

嚴格來說，這樣的實施是錯誤的。

原因是，即使對象不是E類型，它仍然可以在調用equals()時返回true。

承擔第二，你遇到這樣一類：

public class FakeString { 
    private final String value; 

    public FakeString(String value) { 
    if (value == null) { 
     throw new IllegalArgumentException(); 
    } 
    this.value = value; 
    } 

    public int hashCode() { 
    return value.hashCode(); 
    } 

    public boolean equals(Object o) { 
    return value.equals(o); 
    } 
} 

那麼這個代碼將打印true：

List<String> strings = Arrays.asList("foo", "bar", "baz"); 
System.out.println(strings.contains(new FakeString("bar"))); 

而只是爲了澄清：此行爲是意，並且是取代E的原因。順便說一下，remove()也是如此。

Answer 2

爲了讓排序集實現起作用，集合中的元素必須有排序。這可以是「自然的」（即，元素實施Comparable）或「施加的」（在設置施工期間通過使用明確的Comparator）。

所以，第一件事情是，你可能寧願在contains使用的元素集合定義的排序（畢竟，要實現一個SortedSet！），而不是equals效率。我假設，您已經在您的內部SkipListInternal<E>中使用了訂購 - 您如何維護SortedSortedSet只給出equals？

事實上，contains實際上在界面中聲明爲contains(Object key)真的很不幸。我會做的TreeMap實施做什麼（這是TreeSet底層的容器，標準SortedSet從集合框架）：

if (comparator != null) 
    return getEntryUsingComparator(key); 
if (key == null) 
    throw new NullPointerException(); 
Comparable<? super K> k = (Comparable<? super K>) key; 

即投，假設使用收集的客戶端應用程序的行爲三立。

Answer 3

@Joaschim對標準集合的評論是正確的，但是如果你想要一個選中集合，我建議你檢查一下可以添加什麼，而不是針對無效類型的查找進行優化（除非你想拋出一個異常）你可以做就像是。

public class SkipListSet<E> implements SortedSet<E>{ 
    private final Class<E> eClass; 
    private final SkipListInternal<E> skiplist; 

    ... 
    public boolean add(Object o) { 
     if(!eClass.isInstanceOf(o)) 
    // OR 
     if(eClass != o.getClass()) 
      throw new IllegalArgumentException("Type "+o.getClass()+" is not a "+eClass); 
     skiplist.add(o); 
    } 

    public boolean contains(Object o){ 
     // if (!(o instanceof E)) return false; // don't need to optmise for this. 
     return skiplist.find((E) o) != null; 
    } 

    ... 

} 

BTW：Java有一個內置的線程安全ConcurrentSkipListSet和ConcurrentSkipListMap你會覺得很有趣閱讀此源。 ;）

Answer 4

由於是java.util.Collection，我們應該按照合同的Collection.contains()。因爲投擲ClassCastException是可選行爲，所以在投射失敗時在代碼中返回false是正確的。所以我認爲你的實施符合合同。

 /** 
     * Returns true if this collection contains the specified element. 
     * More formally, returns true if and only if this collection 
     * contains at least one element e such that 
     * (o==null ? e==null : o.equals(e)). 
     * 
     * @param o element whose presence in this collection is to be tested 
     * @return <tt>true</tt> if this collection contains the specified 
     *   element 
     * @throws ClassCastException if the type of the specified element 
     *   is incompatible with this collection (optional) 
     * @throws NullPointerException if the specified element is null and this 
     *   collection does not permit null elements (optional) 
     */ 
     boolean contains(Object o);