编写包含（）的通用集合
我正在用java编写一个skiplist类作为练习。 我编写了一个名为SkipListInternal的类，其中包含实际的skiplist。 我还创建了一个名为SkipListSet的包装类，它实现了SortedSet接口，并包含一个SkipListInternal的实例。
除此之外， SkipListInternal包含一个方法E find(E e) ，如果它存在则返回等于e的元素，否则返回null。
当写boolean contains(Object o) （inheritance自Collection via SortedSet ）方法时，我注意到它的参数是一个Object而不是E.我打算做这样的事情，但由于类型擦除：
public class SkipListSet implements SortedSet{ private SkipListInternal skiplist; ... public boolean contains(Object o){ if (!(o instanceof E)) return false; return skiplist.find((E) o) != null; } ... }
既然不能这样做，我该怎么做呢？
严格来说，这样的实施是错误的。
这样做的原因是即使一个对象不是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 strings = Arrays.asList("foo", "bar", "baz"); System.out.println(strings.contains(new FakeString("bar")));
并且只是为了澄清：这种行为是有意的，并且是contains()采用Object而不是E 。 顺便说一下， remove()也是如此。
由于contains()来自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 true 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);
@Joaschim注释对于标准集合是正确的，但是如果你想要一个经过检查的集合，我建议你检查一下可以添加什么，而不是针对无效类型的查找进行优化（除非你想抛出exception）你可以做类似的事情。
public class SkipListSet implements SortedSet { private final Class eClass; private final SkipListInternal 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你可能会发现阅读源代码很有意思。 ;）
为了使有序集实现起作用，集合的元素必须具有排序。 这可能是“自然的”（即，元素实现Comparable ）或“强加”（通过在集合构造期间使用显式Comparator ）。
所以，首先，你可能宁愿使用为set元素定义的排序（毕竟，你实现了一个SortedSet ！）而不是equals in contains来提高效率。 我假设你已经在你的内部SkipListInternal使用了一个排序 – 你如何维持SortedSet的Sorted只给出equals ？
contains实际上在接口中声明为contains(Object key)的事实真的很不幸。 我会这样做， TreeMap实现做了什么（这是TreeSet的底层容器，来自集合框架的标准SortedSet ）：
if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); Comparable k = (Comparable) key;
即，cast，假设使用您的集合的客户端应用程序表现得很好。