为通用集合编写 contains()

Question

我正在用java编写一个skiplist类作为练习。我编写了一个名为 SkipListInternal 的类，其中包含实际的跳过列表。我还创建了一个名为 SkipListSet 的包装类，它实现 SortedSet 接口并包含 SkipListInternal 的实例>。

除此之外，SkipListInternal 包含一个方法 E find(E e)，该方法返回等于 e 的元素（如果存在），否则返回 null。

在编写 boolean contains(Object o) （通过 SortedSet 从 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")));

并且只是为了澄清：此行为是预期，并且是原因contains() 采用 Object 而不是 E。顺便说一句，remove() 也是如此。

Answer 2

由于 contains() 来自 java.util.Collection，我们应该遵循 Collection.contains() contract< /强>。由于抛出 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);

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

   ...

}

顺便说一句：Java 有一个内置的线程安全 ConcurrentSkipListSet 和 ConcurrentSkipListMap 您可能会发现阅读其源代码很有趣。 ;)

Answer 4

为了使排序集实现正常工作，集合中的元素必须具有顺序。这可以是“自然的”（即元素实现Comparable）或“强加的”（通过在集合构造期间使用显式的Comparator）。

因此，第一件事是，您可能更愿意使用为 set 元素定义的顺序（毕竟，您正在实现 SortedSet！）而不是 equals contains 以提高效率。我假设您已经在内部 SkipListInternal 中使用排序 - 您如何在给定的 SortedSet 中维护 Sorted只有等于吗？

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;

即，强制转换，假设使用您的集合的客户端应用程序行为正常。