列表包含快速包含

Question

我想知道是否有List允许快速的实现contains.我工作了很长时间List,Set因为我需要通过索引访问,所以无法切换.我可以忽略现在可接受的性能,将来可能会或可能不会被接受.我可以HashSet在两者上创建并执行所有修改操作,但手动执行操作非常无聊且容易出错.

我知道这是不可能有一流的工作既像List和Set(因为不同的equals语义),但我不知道是否有List实施RandomAccess和采用的HashSet加快contains.

Answer 1

我知道这是不可能有一流的工作既像List和Set

你试过LinkedHashSet吗？从技术上讲,它是一个集合,但它保留了可能对您而言足够的顺序.但是,索引访问是线性的而不是内置的.

其他方法是List使用自定义装饰器进行包装,该装饰器委托List并维护内部Set更快contains.

Answer 2

你可以包装一个列表和哈希集，结合两全其美

public class FastContainsList<T> extends AbstractSequentialList<T> implements RandomAccess{
//extending sequential because it bases itself of the ListIterator(int) and size() implementation

    private List<T> list=new ArrayList<T>();
    private Set<T> set=new HashSet<T>();


    public int size(){
        return list.size();
    }

    public boolean contains(Object o){//what it's about
        return set.contains(o);
    }

    public ListIterator<T> listIterator(int i){
        return new ConIterator(list.listIterator(i));
    }

    /*for iterator()*/
    private ConIterator implements ListIterator<T>{

        T obj;
        ListIterator<T> it;

        private ConIterator(ListIterator<T> it){
        this.it = it
        }

        public T next(){
        return obj=it.next();
        }

        public T previous(){
        return obj=it.previous();
        }

        public void remove(){
        it.remove();//remove from both
        set.remove(obj);
        }

        public void set(T t){
            it.set(t);
            set.remove(obj);
            set.add(obj=t);
        }

         public void add(T t){
             it.add(t);
             set.add(t);
         }

        //hasNext and hasPrevious + indexes still to be forwarded to it
    }

}