-5

我有一个包含 100000 个对象的列表。及其独特的清单。我想向它添加一个新对象。但是添加的条件是它应该是唯一的含义，如果新元素已经在列表中，不应该添加到列表中并且应该抛出异常。请让我知道是否有想法。

4

6 回答 6

1

如果您有充分的理由使用 a List，例如，因为顺序对您很重要，只需使用contains来检查您要添加的元素是否已经在列表中：

public void addUnique(Object element) throws NotUniqueException {
    if (list.contains(element)) {
        throw new NotUniqueException(list, element);
    } else {
        list.add(element);
    }
}

但是，对于 100,000 个对象，contains会很慢，因为它必须执行线性搜索。

另一种选择是，如果您的列表以某种自然顺序存储您的对象，例如，可以用java.util.Comparator. contains在这种情况下，您可以使用二进制搜索来代替使用，将搜索从 O(n) 减少到 O(log(n))：

public void addUnique(Object element) throws NotUniqueException {
    int index = Collections.binarySearch(list, element, comparator);
    if (index >= 0) {
        throw new NotUniqueException(list, element);
    } else {
        list.add(index, element);
    }
}

但是，缺点是add现在变得更加昂贵，因为为了保持列表排序，必须移动一些元素以为新元素腾出空间。这使您add的操作成为线性操作。

为您提供顺序和快速contains和快速的数据结构add是排序树，因此您可能需要评估这是否适合您。

最后，您可以将 aSet与 a结合使用List，即，将每个元素都存储在两者中：集合让您快速contains，而列表保留元素的顺序。使用这种方法，您不仅限于 a 定义的特定顺序，Comparator还可以简单地使用插入顺序：

public void addUnique(Object element) throws NotUniqueException {
    if (set.contains(element)) {
        throw new NotUniqueException(list, element);
    } else {
        list.add(element);
        set.add(element);
    }
}

这基本上LinkedHashSet对你有用 - 另见彼得沃尔瑟的回答。

于 2013-08-23T09:18:01.460 回答
0

使用Set而不是List. 如果您真的想要一个列表，请考虑以下示例。

   List<String> myList=new ArrayList<>();
    myList.add("asd");
    myList.add("asf");
    myList.add("asf");
    Set<String> set=new HashSet<>();
    set.addAll(myList);
    set.add("newString");
    myList.clear();
    myList.addAll(set);
于 2013-08-23T09:14:36.613 回答
0

您可以使用一个集合，它只包含唯一的结果http://docs.oracle.com/javase/7/docs/api/java/util/Set.html。

谢谢

于 2013-08-23T09:02:24.977 回答
0

你应该使用Set相当List。

但尽管你能得到它——

List<Object> list =...;
public boolean add(Object obj){
    Set<Object> set = new HashSet<>(list);
    return set.add(obj);
}
于 2013-08-23T09:02:58.303 回答
0

您需要使用Set数据结构来满足您的要求。但是如果您尝试添加新的副本，它不会抛出异常。

如果您已经有了列表，那么您可以Set使用

Set<YourType> foo = new HashSet<YourType>(yourList);
于 2013-08-23T09:03:16.813 回答
0

如果插入顺序很重要，请改用LinkedHashSet它，它基本上是一个集合，但也跟踪列表中的元素，以允许以与插入元素相同的顺序迭代元素（与列表一样）。

至于尝试添加重复元素时的异常，您可以通过验证add(..)方法是否返回true并抛出异常来检查是否添加了元素Exception，或者通过创建一个专门的子类来执行此检查：

public class UniqueItemList <E> extends LinkedHashSet<E> {

    @Override
    public boolean add (E e) {
        checkContains(e);
        return super.add(e);
    };

    @Override
    public boolean addAll (Collection<? extends E> collection) {
        for (E e : collection) {
            add(e);
        }
        return !collection.isEmpty();
    }

    private void checkContains (E e) {
        if (contains(e)) {
            throw new IllegalArgumentException("Element was already added");
        }
    }
}
于 2013-08-23T09:16:56.647 回答